Oracle-Guided Scheduling for Controlling Granularity in Implicitly Parallel Languages

Umut Acar 1, 2 Arthur Charguéraud 3, 4 Mike Rainey 2
4 TOCCATA - Certified Programs, Certified Tools, Certified Floating-Point Computations
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : A classic problem in parallel computing is determining whether to execute a thread in parallel or sequentially. If small threads are executed in parallel, the overheads due to thread creation can overwhelm the benefits of parallelism, resulting in suboptimal efficiency and performance. If large threads are executed sequentially, processors may spin idle, resulting again in suboptimal efficiency and performance. This " granularity problem " is especially important in implicitly parallel languages, where the programmer expresses all potential for parallelism, leaving it to the system to exploit par-allelism by creating threads as necessary. Although this problem has been identified as an important problem, it is not well understood—broadly applicable solutions remain elusive. In this paper, we propose techniques for automatically controlling granularity in implicitly parallel programming languages to achieve parallel efficiency and performance. To this end, we first extend a classic result, Brent's theorem (a.k.a. the work-time principle) to include thread-creation overheads. Using a cost semantics for a general-purpose language in the style of lambda calculus with parallel tuples, we then present a precise accounting of thread-creation overheads and bound their impact on efficiency and performance. To reduce such overheads, we propose an oracle-guided semantics by using estimates of the sizes of parallel threads. We show that, if the oracle provides accurate estimates in constant time, then the oracle-guided semantics reduces the thread-creation overheads for a reasonably large class of parallel computations. We describe how to approximate the oracle-guided semantics in practice by combining static and dynamic techniques. We require the programmer to provide the asymptotic complexity cost for each parallel thread and use runtime profiling to determine hardware-specific constant factors. We present an implementation the proposed approach as an extension of the Manticore compiler for Parallel ML. Our empirical evaluation shows that our techniques can reduce thread-creation overheads, leading to good efficiency and performance.
Type de document :
Article dans une revue
Journal of Functional Programming, Cambridge University Press (CUP), 2016, 26, <10.1017/S0956796816000101>
Liste complète des métadonnées
Contributeur : Arthur Charguéraud <>
Soumis le : lundi 5 décembre 2016 - 16:18:52
Dernière modification le : vendredi 17 février 2017 - 16:10:57
Document(s) archivé(s) le : jeudi 23 mars 2017 - 00:41:06


Fichiers produits par l'(les) auteur(s)



Umut Acar, Arthur Charguéraud, Mike Rainey. Oracle-Guided Scheduling for Controlling Granularity in Implicitly Parallel Languages. Journal of Functional Programming, Cambridge University Press (CUP), 2016, 26, <10.1017/S0956796816000101>. <hal-01409069>



Consultations de
la notice


Téléchargements du document