窃取工作的算法



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

这些有用吗?

.NET 4.0 中的工作窃取

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

我最近读了那篇论文,其中描述了一个Java Fork/Join框架,该框架具有在中找到的工作窃取算法

从那篇论文中,我们从以下内容开始:

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行)可以递归地自己创建更多的子任务,从而填充并行工作线程的工作队列。如果一个线程完成了,没有其他事情可做,他可以从另一个线程的队列中"窃取"工作。

简言之,关于所有的细节,我建议查阅一下这份文件。

您可以在以下Channel9视频中找到关于偷工作算法的非常好且易于理解的解释:"并行扩展:任务内部并行深入"Duffy、Huseyin Yildiz、Daan Leijen、Stephen Toub,请参阅00:44:00(由Daan Leijen提供)

您可以看看任务调度程序的英特尔TBB算法,它使用的是"偷工"模式。看见https://software.intel.com/fr-fr/node/468190

相关内容

  • 没有找到相关文章

最新更新