チャンクのサイズは、MPIを使用するマスターワーカーを使用して最高のパフォーマンスになるでしょうか？

Question

メトリックTSP問題を解決しようとしているプログラムを並列化するためにMPIを使用しています。私はPプロセッサーとN都市を渡す。

各スレッドはマスタからの作業を要求し、チャンクを受け取ります。これは、チェックする必要のある並べ替えの範囲であり、最小値を計算します。私は悪いルートを前もって剪定することによってこれを最適化しています。

合計（N-1）個あります。計算する経路。各作業者は、確認しなければならない最初のルートと最後のルートを示す番号のチャンクを取得します。さらに、マスターは知られている最新の最良の結果を彼に送ります。したがって、残っている部分の下限を事前に設定しておくと、簡単に悪いルートが発生する可能性があります。

労働者がグローバルよりも良い結果を見つけるたびに、彼はそれを他のすべての労働者とマスターに非同期的に送信します。

私はちょうどどのチャンクサイズが最適かを判断しようとしています。

これまでに見つかった最適なチャンクサイズは（n！）/（n/2）です！しかし、それは良い結果をもたらさない。

ここでどのチャンクサイズが最適か理解してください。計算量と通信量のバランスを取ろうとしています ありがとう

Answer 1

これは、MPIの実装、マシンの総負荷などに大きく依存します。どのくらいのワーカープロセスが多いかによって大きく左右されます。そのメモでは、MPIはスレッドではなくプロセスを生成することを理解しています。

結局のところ、ほとんどの最適化の質問でよくあるように、答えは単に「さまざまな設定をテストして、どれが最適かを確認する」ことです。これを手動で行うか、何らかのヒューリスティック（遺伝的アルゴリズムなど）を実装するテスターアプリを作成することができます。