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, ENS Paris - École normale supérieure - Paris, 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.
Type de document :
Communication dans un congrès
PPoPP '13 - Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming, Feb 2013, Shenzhen, China. pp.69-80, 2013, <10.1145/2442516.2442524>
Liste complète des métadonnées


https://hal.inria.fr/hal-00802885
Contributeur : Albert Cohen <>
Soumis le : mercredi 20 mars 2013 - 15:35:20
Dernière modification le : jeudi 29 septembre 2016 - 01:22:36
Document(s) archivé(s) le : dimanche 2 avril 2017 - 16:11:07

Fichiers

Identifiants

Collections

Citation

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, 2013, <10.1145/2442516.2442524>. <hal-00802885>

Partager

Métriques

Consultations de
la notice

484

Téléchargements du document

254