Dag-calculus: a calculus for parallel computationReport as inadecuate

Dag-calculus: a calculus for parallel computation - Download this document for free, or read online. Document in PDF available to download.

1 CMU - Carnegie Mellon University Pittsburgh 2 GALLIUM - Programming languages, types, compilation and proofs Inria Paris-Rocquencourt 3 LRI - Laboratoire de Recherche en Informatique 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.

Keywords : Calculus Operational semantics Parallelism

Author: Umut Acar - Arthur Charguéraud - Mike Rainey - Filip Sieczkowski -

Source: https://hal.archives-ouvertes.fr/


Related documents