Dag-calculus: a calculus for parallel computation

Umut Acar 1, 2 Arthur Charguéraud 3, 4 Mike Rainey 2 Filip Sieczkowski 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 : Increasing availability of multicore systems has led to greater focus on the design and implementation of languages for writing parallel programs. Such languages support various abstractions for parallelism, such as fork-join, async-finish, futures. While they may seem similar, these abstractions lead to different semantics, language design and implementation decisions, and can significantly impact the performance of end-user applications. In this paper, we consider the question of whether it would be possible to unify various paradigms of parallel computing. To this end, we propose a calculus, called dag calculus, that can encode fork-join, async-finish, and futures, and possibly others. We describe dag calculus and its semantics, establish translations from the afore-mentioned paradigms into dag calculus. These translations establish that dag calculus is sufficiently powerful for encoding programs written in prevailing paradigms of parallelism. We present concurrent algorithms and data structures for realizing dag calculus on multi-core hardware and prove that the proposed techniques are consistent with the semantics. Finally, we present an implementation of the calculus and evaluate it empirically by comparing its performance to highly optimized code from prior work. The results show that the calculus is expressive and that it competes well with, and sometimes outperforms, the state of the art.
Type de document :
Communication dans un congrès
Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP), Sep 2016, Nara, Japan. pp.18 - 32, 2016, <10.1145/2951913.2951946>
Liste complète des métadonnées

Contributeur : Arthur Charguéraud <>
Soumis le : lundi 5 décembre 2016 - 15:59:13
Dernière modification le : vendredi 17 février 2017 - 16:10:46
Document(s) archivé(s) le : mardi 21 mars 2017 - 10:26:23


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



Umut Acar, Arthur Charguéraud, Mike Rainey, Filip Sieczkowski. Dag-calculus: a calculus for parallel computation. Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP), Sep 2016, Nara, Japan. pp.18 - 32, 2016, <10.1145/2951913.2951946>. <hal-01409022>



Consultations de
la notice


Téléchargements du document