cilkのマルチスレッドプログラミングの貪欲なスケジューリングの完全なステップと不完全なステップを理解するのに問題があります。
参考までにパワーポイントのプレゼンテーションを示します。
私が理解している問題は、スライド＃32-37にあります。
誰かが特にどのように説明できますか
Complete step>=P threads ready to run
incomplete steps < p threads ready
お時間を割いていただきありがとうございます
1 に答える
2
まず、スライドで言及されている「スレッド」は、一般に考えられている OS スレッドとは異なることに注意してください。スレッドの定義は、スライド 10 に示されています"a maximal sequence of instructions not containing parallel control (spawn, sync, return)"。これ以上の混乱を避けるために、代わりにそれをタスクと呼びましょう。
スライド 32 ～ 35 では、円はタスク (「スレッド」) を表し、エッジはタスク間の依存関係を表します。そして、あなたが尋ねている文は実際には定義です: P 個以上のタスクが実行できる状態になっている場合 (したがって、すべての P 個のプロセッサが何らかの作業を行うためにビジー状態になる可能性がある場合)、その状況は完全なステップと呼ばれますが、P 個未満のタスクの準備ができている場合は、この状況は不完全なステップと呼ばれます。分析を単純化するために、すべてのタスクに (サイズ 1 の) 等しい作業が含まれていると (暗黙的に) 想定されています。
次に、スライド 35 の定理は、貪欲なスケジューラがプログラムを実行するのに必要な時間の上限を示します。すべての実行は一連の完了ステップと未完了ステップであるため、実行時間はすべてのステップの合計になります。完了した各ステップは正確に P 個の作業を実行するため、完了したステップの数は T1 (合計作業量) を P で割った値よりも大きくなることはありません。次に、不完全な各ステップは、クリティカル パスに属するタスクを実行する必要があります (各ステップで少なくとも 1 つのクリティカル パスがあるため)。パス タスクは準備ができている必要があり、不完全なステップはすべての準備ができているタスクを実行します)。そのため、不完全なステップの総数はスパン T_inf (クリティカル パスの長さ) を超えません。したがって、T1/P と T_inf の合計が実行時間の上限になります。
「スケジューリング理論」セクションの残りのスライドはかなり単純です。
于 2011-06-20T19:05:31.713 に答える