マルチスレッドプログラミングにおける貪欲スケジューリング

Question

マルチスレッドプログラミングでの貪欲スケジューリングの完全なステップと不完全なステップを理解できない問題があります。

これは参考用のパワーポイントのプレゼンテーションです。

Cilk ++ Multi-threaded Programming

私は理解している問題は、スライド＃から32です - 37

誰かがあなたの時間のための

Complete step>=P threads ready to run 
incomplete steps < p threads ready 

おかげで、

を助ける方法を特に説明していただけます

Answer 1

まず、スライドに記載されている「スレッド」は、考えられるようにOSスレッドに似ていないことに注意してください。それらのスレッドの定義は、スライド10："a maximal sequence of instructions not containing parallel control (spawn, sync, return)"にあります。さらなる混乱を避けるために、私はそれを代わりにタスクと呼ぶことにしましょう。

スライド32-35では、円はタスク（「スレッド」）を表し、エッジはタスク間の依存関係を表します。あなたが尋ねる文章は、実際には定義されています。P以上のタスクを実行する準備が整ったとき（そして、すべてのPプロセッサが何らかの作業をするのに忙しいことがある場合）、その状況は完全なステップと呼ばれ、その状況は不完全なステップと呼ばれます。分析を簡単にするために、すべてのタスクに等しい仕事（サイズ1）が含まれていることが（暗黙のうちに）仮定されています。

次に、スライド35の定理は、貪欲スケジューラがプログラムを実行するのに必要な時間の上限を提供する。すべての実行は完全な手順と不完全な手順のシーケンスなので、実行時間はすべての手順の合計です。各完全ステップが正確にP作業を実行するので、完全なステップの数はT1（総作業）をPで割ったものより大きくなることはできません。次に、各不完全ステップはクリティカルパスに属するタスクを実行する必要がありますパスタスクは準備ができていなければならず、不完全なステップはすべての準備タスクを実行する）。不完全なステップの総数はスパンT_inf（クリティカルパス長）を超えません。したがって、T1/PとT_infの合計は実行時間の上限を与えます。

「スケジューリング理論」セクションの残りのスライドはかなり単純です。