Non-blocking steal-half work queues
- 21 July 2002
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the twenty-first annual symposium on Principles of distributed computing - PODC '02
- p. 280-289
- https://doi.org/10.1145/571825.571876
Abstract
The non-blocking work-stealing algorithm of Arora et al. has been gaining popularity as the multiprocessor load balancing technology of choice in both Industry and Academia. At its core is an ingenious scheme for stealing a single item in a non-blocking manner from an array based deque. In recent years, several researchers have argued that stealing more than a single item at a time allows for increased stability, greater overall balance, and improved performance.This paper presents StealHalf, a new generalization of the Arora et al. algorithm, that allows processes, instead of stealing one, to steal up to half of the items in a given queue at a time. The new algorithm preserves the key properties of the Arora et al. algorithm: it is non-blocking, and it minimizes the number of CAS operations that the local process needs to perform. We provide analysis that proves that the new algorithm provides better load distribution: the expected load of any process throughout the execution is less than a constant away from the overall system average.Keywords
This publication has 10 references indexed in Scilit:
- Scheduling multithreaded computations by work stealingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The power of two choices in randomized load balancingIEEE Transactions on Parallel and Distributed Systems, 2001
- Thread Scheduling for Multiprogrammed MultiprocessorsTheory of Computing Systems, 2001
- The data locality of work stealingPublished by Association for Computing Machinery (ACM) ,2000
- Analyses of load stealing models based on differential equationsPublished by Association for Computing Machinery (ACM) ,1998
- Elimination Trees and the Construction of Pools and StacksTheory of Computing Systems, 1997
- Practical implementations of non-blocking synchronization primitivesPublished by Association for Computing Machinery (ACM) ,1997
- A dynamic distributed load balancing algorithm with provable good performancePublished by Association for Computing Machinery (ACM) ,1993
- A simple load balancing scheme for task allocation in parallel machinesPublished by Association for Computing Machinery (ACM) ,1991
- Wait-free synchronizationACM Transactions on Programming Languages and Systems, 1991