Correct and Efficient Work-Stealing for Weak Memory Models

Nhat Minh Lê 1 Antoniu Pop 1 Albert Cohen 1 Francesco Zappa Nardelli 1
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
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 mem- ory models, which we exploit to improve performance but consider- ably 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 run- ning on top of relaxed memory models.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download
Contributor : Albert Cohen <>
Submitted on : Wednesday, March 20, 2013 - 3:35:20 PM
Last modification on : Thursday, February 7, 2019 - 4:56:42 PM
Document(s) archivé(s) le : Sunday, April 2, 2017 - 4:11:07 PM


Publisher files allowed on an open archive




Nhat Minh Lê, Antoniu Pop, Albert Cohen, Francesco Zappa Nardelli. Correct and Efficient Work-Stealing for Weak Memory Models. PPoPP '13 - Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming, Feb 2013, Shenzhen, China. pp.69-80, ⟨10.1145/2442516.2442524⟩. ⟨hal-00802885⟩



Record views


Files downloads