Intel MPI分散メモリ：q <Mプロセッサを使用してM * Nブロックから壁を構築する

Question

私はM個の独立したジョブを持っているとします。各ジョブにはN個のステップがあります。ジョブは互いに独立していますが、各ジョブのステップはシリアルでなければなりません。言い換えると、J（i、j）は、J（i、j-1）が終了した後にのみ開始されるべきである（iはジョブインデックスを示し、jはステップを示す）。これは、Mの幅とNの高さを持つ壁を構築することと同形です。

各ジョブブロックは1回だけ実行する必要があります。 1つのCPUを使用して1つのCPUを使用して（同じ順序でも）1ブロックの作業を行うのにかかる時間は、ブロックごとに異なり、事前には分かっていません。

MPIを使用してこれを行う簡単な方法は、作業ブロックをプロセッサに割り当て、すべてのプロセッサが次の割り当て前にブロックを終了するまで待機することです。このようにして、優先順位を強制することができますが、待ち時間が多くなります。

これを行うより効率的な方法はありますか？つまり、プロセッサが何らかの環境変数や共有メモリを使用して仕事を終え、他のプロセッサが仕事を終えて通信を使用して一括決定を待つことなく、次に行うべき仕事のブロックを決めることができます。

Answer 1

N個のステップがあるM個のジョブがあります。また、WとMの間のサイズWのワーカー・プロセスもあります。

WがMに近い場合は、1：1に割り当てることをお勧めします。一人の労働者が早期に終了すれば、それは問題ありません。 1つのステップのためのいくつかの平均や典型的な時間を完了するために

1. 見積り：WはMよりもはるかに小さく、Nもかなり大きい場合

   は、ここでの考え方です。これをTと呼んでください。最初に見積もり率が非常に低い場合に備えて、この見積もりを調整することができます。

2. M個のジョブをワーカーの数で均等に分割して開始します。 T * N/Kのように、タイムアウトの前にできるだけ多くの作業を割り当てられていることを労働者に伝えます。現在のジョブを終了するためにタイムアウトをわずかにオーバーランニングすることで、前進を確実にすることができます。
3. 作業員は、完了したステップを互いに連絡します。
4. 各ジョブの完了度を考慮してジョブを均等に分割します（例：2つの50％完了ジョブは1つの0％完了ジョブと同じです）。

アイデアは、すべての作業者に毎回約1/Kの作業を完了するのに十分な時間を与えることです。 K * T以上の仕事がない場合は、これは非常に効率的です。 1つの共有変数

は維持：n =最も遠いビハインドタスクの進捗

それは良いことだ場合は、合理的なK.はたぶんここアイデアだ10

Answer 2

を試す見つけるIDKするのはあなた次第です。すなわち、M個のタスクのいずれかが完了した最低のステップ番号である。すべてのタスクが最初のステップから開始するため、0から開始します。すべてのタスクが少なくとも1ステップずつ完了するまでは0のままです。

プロセッサがジョブのステップを完了したら、現在作業中のステップの進捗状況をnにチェックします。 n < current_job_step - 4の場合は、作業中のタスクが最も遠いタスクより先に進んでいるため、タスクを切り替えます。

私は4を選んで、あまりにも多くの切り替えと2つのタスクであまりにも多くのシリアル作業を行うことのバランスを取っています。必要に応じて調整し、最後に近づけるように適応させることもできます。

すべての決定を下すスケジューラスレッドを持っていない限り、2つのスレッドを持たない切り替えタスクで同じワークユニットを取得することは簡単です。これが単一の共有メモリマシン上にある場合、ロックを使用して優先順位キューを保護することができます。