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 aforementioned 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 multicore 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.
Mon 19 SepDisplayed time zone: Osaka, Sapporo, Tokyo change
10:45 - 12:25
|Farms, Pipes, Streams and Reforestation: Reasoning about Structured Parallel Processes using Types and Hylomorphisms
David Castro-Perez University of St. Andrews, UK, Kevin Hammond University of St. Andrews, UK, Susmit Sarkar University of St. Andrews, UKDOI
|Dag-Calculus: A Calculus for Parallel Computation
Umut A. Acar Carnegie Mellon University, Arthur Charguéraud Inria, France, Mike Rainey Inria, France, Filip Sieczkowski Inria, FranceDOI
|A Lambda-Calculus Foundation for Universal Probabilistic Programming
Johannes Borgström Uppsala University, Sweden, Ugo Dal Lago University of Bologna, France, Andrew D. Gordon Microsoft Research, UK, Marcin Szymczak University of Edinburgh, UKDOI
|Deriving a Probability Density Calculator (Functional Pearl)