Cilk工作竊取性能

Question

我正在閱讀描述Cilk竊取調度性能的文件。

1）我的理解是，調度程序不知道關鍵路徑的任務，只是試圖通過竊取任務圖中不「深」的任務來維持其執行。那是對的嗎？

2）另外，Cilk工作竊取調度程序是否假設所有任務具有相似的複雜性？如果任務的複雜性不統一，是不是調度程序在實現最佳性能方面不夠靈活，即最佳的負載平衡？

Answer 1

也許回答（1）的最佳方式是Cilk調度在竊取任務時是廣度優先，否則是深度優先。

對（2）的回答是，Cilk任務調度程序忽略了任務的複雜性。

要理解的一個關鍵原則是「布倫特引理」（早先由格雷厄姆發現）。引理顯示（在PRAM假設下）給出了一個貪婪的調度器（如果有工作要做的話，從不讓工人空閒），那麼絕對可能的時間表比最壞的可能時間表快不超過2倍，無論如何這些任務的複雜性是什麼。

2x的直覺是限制是在執行過程中，如果沒有工作人員在關鍵路徑上工作（咀嚼關鍵路徑），那麼每個工作人員都很忙（咀嚼總工時）。關鍵路徑加總工作不能超過算法總工作的兩倍。

PRAM假設可能是真實機器的最薄弱環節，其中緩存未命中次數可能比緩存命中次數多100倍。所以擔心任務的複雜性不如緩存考慮重要。根據Cilk的使用方式，它可以很好地與緩存（遞歸程序）或不好的（背靠背cilk_for循環）配合使用。