parallel-processing - 工作窃取和双端队列

Question

为什么我们需要一个双端队列来窃取工作？（例如在 Cilk 中）所有者在顶部工作，而小偷从底部偷窃。为什么有用？

我们可能有多个窃贼从底部偷窃。那么，我们不需要锁吗？我在某处读到较大的作业（例如在树中创建）被添加到底部。因此，从底层偷窃效率更高（沟通更少，因为窃贼通过偷窃他们变得更加忙碌）。是这样吗？

Answer 1

THE 协议的细节在“Cilk-5 多线程语言的实现”的第 5 节中描述，可从 MIT 获得：http ://supertech.csail.mit.edu/papers/cilk5.pdf

Answer 2

你不需要一个双端队列来窃取工作。使用并发数据结构来存储任务池是可能的（人们已经这样做了）。但问题是工人的推送/弹出操作和小偷的窃取请求都必须同步。

由于预计窃取是相对罕见的事件，因此可以设计一种数据结构，以便在窃取尝试期间主要执行同步，即使在从数据结构中弹出项目可能存在冲突时也是如此。这正是 Cilk 中使用双端队列的原因 - 以最大限度地减少同步。Worker 将他们自己的 deques 视为堆栈，从底部推送和弹出线程，但将另一个忙碌的 worker 的 deque 视为队列，只要他们没有本地线程要执行，就只从顶部窃取线程。由于窃取操作是同步的，因此多个小偷试图从同一个受害者那里窃取是可以的。

在分而治之的算法中，添加到底部的较大工作很常见，但并非全部。有各种各样的策略可以在偷窃期间做什么。偷一个任务，几个任务，一半任务，等等。这些变体中的每一个都适用于某些应用程序，而在其他应用程序中则不太适用。

Answer 3

工作窃取实际上确实需要一个双端队列。在原始论文中，他们证明了在具有 P 个处理器的系统上使用的最大内存。该限制由任何堆栈的最大大小乘以处理器数量给出。这实际上只有通过遵循繁忙的叶子定理才有可能。此外，工作窃取的另一个重要特征是：当一个工人生成一个生成器时，它会立即将生成器保存在双端队列上并开始对子进程工作。有关他们的证明的更多信息，请阅读他们的原始论文，他们在其中解释了我所说的一切。http://supertech.csail.mit.edu/papers/steal.pdf

工作窃取双端队列访问中的并发控制与工作窃取调度程序无关，事实上，已经对从双端队列中删除锁（通过使用无锁结构）以及尽可能减少内存障碍进行了很多研究. 例如在这篇论文中（如果无法访问，我很抱歉，但你可以阅读摘要以了解这个想法）：http ://dl.acm.org/citation.cfm?id=1073974作者创建了一个新的deque 用于改进上述方面。

窃取是从工人没有工作的一侧进行的，可能有几个原因：由于双端队列充当每个工人（双端队列的所有者）的堆栈，因此“更大”的工作应该在它之上（因为你可以通过阅读论文来理解）。当我说更大时，我的意思是那些可能会有更多的计算要做。此外，另一个重要方面是这样做（从双端队列所有者的对面工作方窃取）减少了争用，因为在某些新双端队列中，受害者和窃贼可能同时在同一个双端队列上工作。