工作窃取和双端队列

Question

工作窃取和双端队列

parallel-processingtask-parallel-librarydequework-stealing

4

为什么我们需要使用双端队列来进行工作窃取？（例如在Cilk中）所有者从顶部执行任务，而窃贼从底部进行窃取。这有什么用处呢？

我们可能会有多个窃贼从底部进行窃取。那么，我们不是仍然需要锁定吗？我在某处读到过，较大的任务（例如在树中创建的任务）被添加到底部。因此从底部进行窃取更加有效率（通信成本更低，因为窃贼通过窃取它们变得更加忙碌）。是吗？

- towi_parallelism

3个回答

1

THE协议的详细内容在《Cilk-5多线程语言的实现》的第5节中进行了描述，该文可以从MIT获取: http://supertech.csail.mit.edu/papers/cilk5.pdf。

- Barry Tannenbaum - Intel

1

你不需要使用deque来进行工作窃取。可以使用并发数据结构来存储任务池（已有人这样做）。但问题在于，工作者的推入/弹出操作和窃贼的偷取请求都必须进行同步。

由于窃取事件预计是相对罕见的，因此可以设计一种数据结构，使同步主要在尝试窃取时进行，即在从数据结构中弹出一个项目可能存在冲突的情况下进行同步。这正是为什么Cilk中使用deque的原因-以最小化同步。工作者将自己的deque视为堆栈，从底部推入和弹出线程，但将另一个繁忙工作者的deque视为队列，仅在没有本地线程可执行时从顶部窃取线程。由于窃取操作是同步的，因此多个窃贼尝试从同一受害者那里窃取是可以的。

在分而治之的算法中，向底部添加更大的作业很常见，但并非所有情况都是如此。针对窃取期间要做的事情有各种各样的策略。窃取一个任务、几个任务、一半任务等。每种变体对某些应用程序效果很好，对其他应用程序效果不佳。

- shams

谢谢你的回答。我大部分都同意。只有这一部分“由于偷窃事件预计是相对罕见的”：在 fork-join 模型中并不是真的。整个模型都是基于偷窃的。主工作者创建工作，其他人几乎一直在偷窃。对吧？ - towi_parallelism

@TOWI_Parallelism，是的，有一些应用程序中偷取操作会更加频繁。但是，在许多应用程序中，在执行任务的工作线程完成偷取操作后，还会生成新的任务。这些任务会被添加到本地队列中。因此，工作线程不需要经常从主线程中进行偷取操作。 - shams

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- guilhermemtr · Accepted Answer

工作窃取实际上需要一个双端队列。在原始论文中，他们证明了在具有P个处理器的系统上使用的最大内存。极限由任何堆栈的最大大小乘以处理器数给出。这实际上只能通过遵循繁忙叶定理来实现。此外，工作窃取的另一个重要特点是：当一个工作者进行生成时，它立即将生成器保存到双端队列中并开始处理子代。有关其证明的更多信息，请阅读他们的原始论文，在其中他们解释了我所说的所有内容。 http://supertech.csail.mit.edu/papers/steal.pdf 工作窃取双端队列访问中的并发控制与工作窃取调度程序无关，并且实际上已经进行了许多研究，以从deque中删除锁（使用无锁结构）并尽可能减少内存障碍。例如，在这篇论文中（如果您无法访问，对于了解想法，您仍然可以阅读摘要）： http://dl.acm.org/citation.cfm?id=1073974，作者创建了一个新的deque以改善上述方面。

窃取是从工作者未工作的一侧进行的，可能有几个原因：由于deque对于每个工作者（deque的所有者）都充当堆栈，因此“更大”的作业应位于其顶部（通过阅读论文可以理解）。当我说更大时，我想表达的是那些可能需要更多计算的作业。此外，另一个重要方面是通过这样做（从deque所有者的相反工作侧面窃取），减少了争用，因为在某些新的deque中，受害者和窃贼可能同时在同一个deque上工作。