偷工减料

Question

为什么我们需要偷工减料？ （例如在Cilk）主人在顶端工作，小偷从底部偷窃。为什么它有用？

我们可能会有多个盗贼从底部偷窃。那么，我们不需要锁吗？ 我读过一些地方，大型作业（例如在树中创建）被添加到底部。所以，从底部偷窃更有效率（减少沟通，因为窃贼通过窃取他们变得更加忙碌）。是吗？

Answer 1

该协议的细节了“的Cilk-5多线程语言的实现”，这是从MIT第5节描述：http://supertech.csail.mit.edu/papers/cilk5.pdf

Answer 2

你并不需要为工作窃取一个deque。这是可能的（并且人们已经做到了）使用并发数据结构来存储任务池。但问题是，来自工人的推/拉操作和来自盗贼的窃取请求都必须同步。由于抢断预计会是相对罕见的事件，因此可以设计一个数据结构，以便在窃取尝试期间同时进行同步化，甚至在可能存在冲突的情况下弹出一个来自数据结构。这就是为什么在Cilk中使用deques的原因 - 尽量减少同步。工作人员将自己的deques视为堆栈，从底部推送和弹出线程，但将另一个繁忙工作人员的双端队列当作队列处理，只有在没有本地线程执行的情况下才从顶端窃取线程。由于窃取操作是同步的，所以多个盗贼试图从同一个受害者那里窃取是可以的。

在分而治之风格算法中添加较大的作业是常见的，但不是全部。有很多策略适用于在偷窃过程中做什么。偷一项任务，几项任务，一半任务等等。这些变体中的每一个都适用于某些应用程序，其他应用程序不太适合。

Answer 3

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

工作中的并发控制窃取deque访问与工作窃取调度程序无关，实际上，已经对从deque（通过使用无锁结构）中移除锁进行了大量研究，并且最小化为尽可能多的记忆障碍。例如在本文中（如果无法访问，我很抱歉，但是您可以阅读摘要以获得想法）：http://dl.acm.org/citation.cfm?id=1073974作者为改进上述方面创建了一个新的双端队列。

由于可能有以下几个原因，该工作人员没有在工作的一侧进行抢断： 由于每个工作人员（双侧工作人员）都是作为一个堆栈工作，所以“较大”的工作应该在最上面（你可以通过阅读文章了解）。当我说更大的时候，我想表示那些可能会有更多的计算要做。此外，另一个重要方面是通过这样做（偷取老板的对面工作方）可以减少争用，因为在一些新的双层舞者中，受害者和小偷可能同时在同一个双层舞台上工作。