1

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

1)我的理解是调度程序不知道关键路径的任务,但只是试图在任何情况下通过窃取任务图中不“深”的任务来维持其执行。那是对的吗?

2)此外,Cilk 窃取调度程序的工作是否假设所有任务都具有相似的复杂性?如果任务的复杂性不统一,是不是调度器在实现最佳性能(即最佳负载平衡)方面的灵活性会降低?

4

1 回答 1

1

回答 (1) 的最佳方法可能是 Cilk 调度在窃取任务时是广度优先的,否则是深度优先的。

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

要理解的一个关键原则是“布伦特引理”(格雷厄姆早些时候发现)。引理表明(在 PRAM 假设下)给定一个贪婪的调度程序(如果有工作要做,绝不让工作人员空闲),那么绝对最佳可能的调度不超过最差可能的调度的 2 倍,不管怎样任务的复杂性是什么。

2x 背后的直觉是限制是,在执行期间,如果没有工作人员在关键路径上处理任务(咀嚼关键路径),那么每个工作人员都很忙(咀嚼总工作)。关键路径加上总工作量不能超过算法总工作量的两倍。

PRAM 假设可能是与真实机器的最薄弱环节,其中缓存未命中的时间可能比缓存命中多 100 倍。因此,担心任务的复杂性不如考虑缓存重要。根据 Cilk 的使用方式,它可以很好地与缓存(递归程序)或不好(背靠背的 cilk_for 循环)一起使用。

于 2016-08-23T01:21:39.380 回答