Dag-calculus: a calculus for parallel computation
Dag-calculus: a calculus for parallel computation
复制标题
Dag-calculus：并行计算的微积分
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Filip Sieczkowski
中科院分区：
文献类型：
--
作者：
Umut A. Acar;A. Charguéraud;Mike Rainey;Filip Sieczkowski
随着多核系统可用性的提高，人们更加关注编写并行程序的语言的设计和实现。这类语言支持并行性的各种抽象，如fork-Join、Async-Finish、Futures。尽管它们可能看起来很相似，但这些抽象导致不同的语义、语言设计和实现决策，并可能显著影响最终用户应用程序的性能。在本文中，我们考虑了是否有可能统一并行计算的各种范例的问题。为此，我们提出了一种称为DAG演算的演算，它可以编码fork-Join、异步-Finish和Futures，可能还有其他代码。我们描述了DAG演算及其语义，建立了从上述范例到DAG演算的转换。这些翻译证明了DAG演算对于以主流并行范例编写的程序来说是足够强大的。我们给出了在多核硬件上实现DAG演算的并发算法和数据结构，并证明了所提出的技术与语义一致。最后，我们给出了一个演算的实现，并通过将其性能与先前工作中高度优化的代码进行比较，对其进行了经验评估。结果表明，微积分是有表现力的，它很好地与最先进的技术竞争，有时甚至超过了最先进的水平。
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.