Correct and efficient work-stealing for weak memory models
Authors:
Open Access
- 23 February 2013
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 48 (8) , 69-80
Abstract
Chase and Lev's concurrent deque is a key data structure in shared-memory parallel programming and plays an essential role in work-stealing schedulers. We provide the first correctness proof of an optimized implementation of Chase and Lev's deque on top of the POWER and ARM architectures: these provide very relaxed memory models, which we exploit to improve performance but considerably complicate the reasoning. We also study an optimized x86 and a portable C11 implementation, conducting systematic experiments to evaluate the impact of memory barrier optimizations. Our results demonstrate the benefits of hand tuning the deque code when running on top of relaxed memory models.Keywords
This publication has 9 references indexed in Scilit:
- An Axiomatic Memory Model for POWER Multiprocessors2012
- Understanding POWER multiprocessors2011
- x86-TSOCommunications of the ACM, 2010
- Idempotent work stealing2009
- StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures2009
- KAAPI2007
- Dynamic circular work-stealing deque2005
- Scheduling multithreaded computations by work stealingJournal of the ACM, 1999
- The implementation of the Cilk-5 multithreaded language1998