新しいプロジェクト管理アルゴリズムが有限数の従業員に求められていました

Question

私はタスクベースの並列計算を研究していました。古いプロジェクト管理の問題のバリエーションに興味がありました。これは、アクティビティ・オン・バテックス（AOV）プロジェクトネットワークは、デッドロックサイクルがない場合にトポロジカルソートアルゴリズムを使用して計算できます。クリティカルパス上のアクティビティの合計時間は、プロジェクトの最小完了時間を示します。

しかし、これは、互いに依存しないで作業を同時に完了するのに十分な労働者が常にいることを前提としています。利用可能なワーカー（プロセッサ/コア）の数が有限である場合、特定のアクティビティは依存しているアクティビティがまだ完了していないために待たずに、ただ単にすべてのワーカーが他のアクティビティをやっているためです。これは、今日のマルチコア・パラレル・コンピューティングの簡略化されたモデルです。すべての活動を行う必要がある唯一の労働者がいる場合、プロジェクト完了時間はすべての活動の合計時間です。我々はそのようにシングルコアのシリアルコンピューティングに戻っています。

限られた数のワーカーが利用可能な場合、AOVネットワークの最小完了時間を与える効率的なアルゴリズムはありますか？どのような活動を行うべきかを賢明に選択しなければならないのは、後に労働者のアイドリング時間を最小限に抑えるために、最小時間は、クリティカルパス時間（無限の労働者）とすべての活動の合計時間（1人の労働者）の間のどこかにあるべきです。また、合計時間を労働者の数で割ったもの（アイドリングなし）よりも大きくなければなりません。その最小時間を取得するアルゴリズムはありますか？

Answer 1

私の質問にほぼ答える「work stealing」と呼ばれるC++会議ビデオが見つかりました。 18時40分に、アクティビティを休止したり、さらに分割したり、労働者から労働者に移したりすることができない場合、スライドはNP困難な問題と言われています。そのような制限は、どの職場がどの職務（活動）を終わらせるかを決定することをあまりにも困難にする。したがって、事前にそのような困難な決定をすることを避けるために、盗み見が導入されています。むしろ、ある種の貪欲なルールが続く限り、このような決定はもはや重要ではありません。限られた数の労働者のクリティカルパスまたは無アイドル時間の制約、またはその両方の制約の下で、プロジェクト全体が常に可能な限り早く終了します。次にビデオは、インプリメンテーションを分散させ、キャッシュフレンドリーにすることによって、異なるワーカー（プロセッサ）間の「作業窃盗」の手順をより効率的にする方法について話します。

ビデオによれば、メモリ並列コーディングは、ループベースではなくタスクベースである。問題を解決するために、プログラマは一連のタスクを定義し、それらの依存関係を尊重し、実行時に複数のコア上でタスクを柔軟にスケジューリングします。分散タスクキューイングシステムによって柔軟なコードを実装するこのような「イベントドリブン」のような方法は、並列コンピューティングで非常に役立ちます。

最適化問題がNP-hardの場合、解決する最も良い方法は、最適化問題を回避する方法を見つけることです。