Provably and Practically Efficient Granularity Control

Abstract : Over the past decade, many programming languages and systems for parallel-computing have been developed, e.g., Fork/Join and Habanero Java, Parallel Haskell, Parallel ML, and X10. Although these systems raise the level of abstraction for writing parallel codes, performance continues to require labor-intensive optimizations for coarsening the granularity of parallel executions. In this paper, we present provably and practically efficient techniques for controlling granularity within the run-time system of the language. Our starting point is "oracle-guided scheduling", a result from the functional-programming community that shows that granularity can be controlled by an "oracle" that can predict the execution time of parallel codes. We give an algorithm for implementing such an oracle and prove that it has the desired theoretical properties under the nested-parallel programming model. We implement the oracle in C++ by extending Cilk and evaluate its practical performance. The results show that our techniques can essentially eliminate hand tuning while closely matching the performance of hand tuned codes.
Type de document :
Communication dans un congrès
PPoPP 2019 - Principles and Practice of Parallel Programming, Feb 2019, Washington DC, United States. 〈10.1145/3293883.3295725〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01973285
Contributeur : Arthur Charguéraud <>
Soumis le : lundi 4 février 2019 - 16:40:20
Dernière modification le : jeudi 7 février 2019 - 17:52:12

Fichier

long_version.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Umut Acar, Vitaly Aksenov, Arthur Charguéraud, Mike Rainey. Provably and Practically Efficient Granularity Control. PPoPP 2019 - Principles and Practice of Parallel Programming, Feb 2019, Washington DC, United States. 〈10.1145/3293883.3295725〉. 〈hal-01973285v2〉

Partager

Métriques

Consultations de la notice

25

Téléchargements de fichiers

151