论文标题
充分读/编写多样性的无围栏工作偷窃
Fully Read/Write Fence-Free Work-Stealing with Multiplicity
论文作者
论文摘要
偷窃是一种以分布式方式实现动态负载平衡的流行技术。在这种方法中，每个过程都拥有一组必须执行的任务。该集合的所有者可以将任务放入其中，并可以从中删除任务以执行它们。当一个过程用完任务时，而不是闲置，而是从受害者那里窃取任务的小偷。因此，偷窃算法提供了三个高级操作：put and take，只能由所有者和偷窃来调用，这可以由小偷调用。设计偷窃算法时的主要目标之一是使PUT并尽可能简单和高效。不幸的是，已经表明，标准异步模型中的任何偷窃算法都必须使用昂贵的读取的读取 - 后写后同步模式或原子读取模式 - 修改 - 纸条指令，这在实践中可能是昂贵的。因此，先前的研究提出了努力窃取的努力，这是一种放松，其中有一些算法带有put和没有读取的 - 修改 - 定量 - - 定量原子指令，以及读取后写入的同步模式；但是，将写入说明中的围栏使用围栏，而窃取使用读取说明中的比较和交换和围栏。在TSO模型中，在该模型中无法重新排序（分别读取）指令，已经提出了完全无围栏的工作偷窃算法，其提案和采用具有相似的属性，但窃取使用了比较和交换或锁。
Work-stealing is a popular technique to implement dynamic load balancing in a distributed manner. In this approach, each process owns a set of tasks that have to be executed. The owner of the set can put tasks in it and can take tasks from it to execute them. When a process runs out of tasks, instead of being idle, it becomes a thief to steal tasks from a victim. Thus, a work-stealing algorithm provides three high-level operations: Put and Take, which can be invoked only by the owner, and Steal, which can be invoked by a thief. One of the main targets when designing work-stealing algorithms is to make Put and Take as simple and efficient as possible. Unfortunately, it has been shown that any work-stealing algorithm in the standard asynchronous model must use expensive Read- After-Write synchronization patterns or atomic Read-Modify-Write instructions, which may be costly in practice. Thus, prior research has proposed idempotent work-stealing, a relaxation for which there are algorithms with Put and Take devoid of Read-Modify-Write atomic instructions and Read-After-Write synchronization patterns; however, Put uses fences among Write instructions, and Steal uses Compare&Swap and fences among Read instructions. In the TSO model, in which Write (resp. Read) instructions cannot be reordered, there have been proposed fully fence-free work-stealing algorithms whose Put and Take have similar properties but Steal uses Compare&Swap or a lock.
