工作窃取算法

Question

我正在阅读一篇关于并发运行时的文章,本文中提到了算法work stealing.但我不知道这个算法是什么!所以我想要一些解释或一些好的链接,可以帮助我做一个关于这个算法的演示文稿.

Answer 1

这些都有帮助吗？

.NET 4.0中的工作窃取

通过工作窃取来调度多线程计算

Answer 2

最近,我读了文件,该文件描述了一个Java fork/join框架与工作窃取Algroithms发现这里

从那篇论文中我们开始:

Result solve(Problem problem) {
    if (problem is small)
       directly solve problem
    else {
       split problem into independent parts
       fork new subtasks to solve each part
       join all subtasks
       compose result from subresults
    }
}

那些分叉的子任务(else块中的第2行)可以递归地创建更多的子任务,从而填充并行工作线程的工作队列.如果一个线程完成并且没有其他任何操作,他可以​​从另一个线程的队列中"窃取"该工作.

简而言之,对于所有细节,我建议查看论文.

Answer 3

您可以在以下Channel9视频中找到工作窃取算法的相当不错且易于理解的解释: "并行扩展:在并行深入的任务中"Duffy,Huseyin Yildiz,Daan Leijen,Stephen Toub,来自00:44:00(由Daan看到)Leijen)