Cilk工作窃取性能

Question

我正在阅读描述Cilk的工作窃取调度性能的论文。

1)我的理解是，调度器不知道关键路径的任务，而只是试图通过窃取任务图中不“深入”的任务来保持其在任何情况下的执行。对吗？

2)另外，Cilk work窃取调度器是否假设所有任务都具有类似的复杂性？如果任务的复杂度不一致，那么调度器在实现最佳性能，即最佳负载平衡方面的灵活性不是很高吗？

Answer 1

也许回答(1)的最好方法是，当窃取任务时，Cilk调度是广度优先的，否则是深度优先的。

(2)的答案是Cilk任务调度器忽略了任务的复杂性。

要理解的一个关键原则是“布伦特引理”(由格雷厄姆早些时候发现)。引理表明(在PRAM假设下)给定一个贪婪的调度器(如果有工作要做，它永远不会让工人空闲)，那么无论任务的复杂性如何，绝对最好的可能调度都不会比最差的调度快2倍。

2倍限制背后的直觉是，在执行过程中，如果没有工人在关键路径上的任务上工作(在关键路径上大嚼大口)，那么每个工人都很忙(大口地吃着整个工作)。关键路径加上总工作量不能超过算法总工作量的两倍。

PRAM假设可能是与真实机器最弱的联系，在真实机器中，缓存未命中的时间可能是缓存命中的100倍。因此，担心任务的复杂性没有考虑缓存那么重要。取决于如何使用Cilk，它在缓存(递归程序)上表现得很好，或者很差(背靠背cilk_for循环)。