Heartbeat scheduling: provable efficiency for nested parallelism

Abstract : A classic problem in parallel computing is to take a high-level parallel program written, for example, in nested-parallel style with fork-join constructs and run it efficiently on a real machine. The problem could be considered solved in theory, but not in practice, because the overheads of creating and managing parallel threads can overwhelm their benefits. Developing efficient parallel codes therefore usually requires extensive tuning and optimizations to reduce parallelism just to a point where the overheads become acceptable. In this paper, we present a scheduling technique that delivers provably efficient results for arbitrary nested-parallel programs, without the tuning needed for controlling parallelism overheads. The basic idea behind our technique is to create threads only at a beat (which we refer to as the "heartbeat") and make sure to do useful work in between. We specify our heartbeat scheduler using an abstract-machine semantics and provide mechanized proofs that the scheduler guarantees low overheads for all nested parallel programs. We present a prototype C++ implementation and an evaluation that shows that Heartbeat competes well with manually optimized Cilk Plus codes, without requiring manual tuning.
Type de document :
Communication dans un congrès
PLDI’18 - 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun 2018, Philadelphia, United States. ACM Press, 〈10.1145/3192366.3192391〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01937946
Contributeur : Arthur Charguéraud <>
Soumis le : mercredi 28 novembre 2018 - 14:13:07
Dernière modification le : jeudi 7 février 2019 - 16:54:55

Identifiants

Citation

Umut Acar, Arthur Charguéraud, Adrien Guatto, Mike Rainey, Filip Sieczkowski. Heartbeat scheduling: provable efficiency for nested parallelism. PLDI’18 - 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun 2018, Philadelphia, United States. ACM Press, 〈10.1145/3192366.3192391〉. 〈hal-01937946〉

Partager

Métriques

Consultations de la notice

107

Téléchargements de fichiers

45