在cilk中的多線程編程中的貪婪調度

Question

我在理解cilk中的多線程編程中的貪婪調度中的完整步驟和不完整步驟的問題。

這裏是供參考的power-point演示文稿。

Cilk ++ Multi-threaded Programming

的問題我已經認識是從幻燈片＃32 - 37

能有人請解釋尤其是如何

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

感謝您的時間和幫助

Answer 1

首先，請注意幻燈片中提到的「線索」不像人們可能認爲的那樣是操作系統線程。他們的線程定義見幻燈片10："a maximal sequence of instructions not containing parallel control (spawn, sync, return)"。爲了避免進一步的混淆，我把它稱爲一個任務。

在幻燈片32-35上，圓圈表示任務（「線程」），邊表示任務之間的依賴關係。你所問的句子實際上就是定義：當P或更多的任務準備好運行時（並且所有的P處理器都可以忙於做一些工作），這種情況被稱爲完整的步驟，而如果P任務準備不足，這種情況被稱爲不完整的一步。爲了簡化分析，（隱含地）假定所有任務包含相同的工作（大小爲1）。

然後，幻燈片35上的定理提供了貪婪調度程序運行程序所需的時間上限。由於所有執行都是一系列完整且不完整的步驟，所以執行時間是所有步驟的總和。由於每個完整的步驟完成P工作，所以完整步驟的數量不能大於T1（總工時）除以P.然後，每個不完整步驟必須執行屬於關鍵路徑的任務（因爲在每一步至少有一個關鍵路徑任務必須準備好，並且不完整的步驟執行所有準備好的任務）;所以不完整步驟的總數不超過T_inf（關鍵路徑長度）範圍。因此，T1/P和T_inf的總和給出了執行時間的上限。

「調度理論」部分中的其他幻燈片相當簡單。