Skip to Main content Skip to Navigation
Journal articles

Oracle-Guided Scheduling for Controlling Granularity in Implicitly Parallel Languages

Umut Acar 1, 2 Arthur Charguéraud 3, 4, 5 Mike Rainey 2
4 TOCCATA - Formally Verified Programs, Certified Tools and Numerical Computations
LRI - Laboratoire de Recherche en Informatique, Inria Saclay - Ile de France
5 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [55 references]  Display  Hide  Download
Contributor : Arthur Charguéraud Connect in order to contact the contributor
Submitted on : Monday, December 5, 2016 - 4:18:52 PM
Last modification on : Tuesday, January 11, 2022 - 11:16:27 AM
Long-term archiving on: : Thursday, March 23, 2017 - 12:41:06 AM


Files produced by the author(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⟩



Les métriques sont temporairement indisponibles