Disentanglement in nested-parallel programs
Disentanglement in nested-parallel programs
复制标题
嵌套并行程序中的解开
DOI：
10.1145/3371115
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Acar, U
中科院分区：
文献类型：
--
作者：
Westrick, S;Yadav, R;Fluet, M;Acar, U
事实证明，嵌套并行性是对快速扩展的多核计算机进行编程的一种流行方法。它允许程序员在高层次上表达并行性，并依赖运行时系统和调度程序来提供效率和可扩展性。因此，许多支持嵌套并行性的编程语言和扩展被开发出来，包括 C/C++、Java、Haskell 和 ML。然而，编写高效且可扩展的嵌套并行程序仍然具有挑战性，这主要是由于破坏性更新或影响引起的并发错误。几十年来，研究人员一直认为，函数式编程可以通过允许对效果进行更多控制来简化并行程序的编写，但与用较低级语言编写的并行程序相比，函数式程序的性能仍然不佳。函数式语言的根本困难在于它们对内存的需求很高，而且这种需求只会随着并行性的增加而增长。在本文中，我们确定了嵌套并行程序的内存属性，称为解缠结，并提出了内存管理技术以提高效率和可扩展性。只要并发执行的线程不了解彼此分配的内存对象，解缠就会产生（破坏性）效果。我们通过考虑具有可变引用的类似 ML 的高阶语言并为其提供动态语义来正式定义解缠结，从而能够对嵌套并行程序的计算图进行推理。基于这种图语义，我们形式化了一个经典的正确性属性——确定性种族自由——并证明它意味着解开。这表明解缠结适用于相对广泛的并行程序类别。然后，我们提出了嵌套并行程序的内存管理技术，利用解缠来提高效率和可扩展性。我们通过扩展标准 ML 的 MLton 编译器以支持这种形式的嵌套并行性，证明了这些技术的实用性。我们的实证评估表明，我们的技术高效且可扩展性良好。
Nested parallelism has proved to be a popular approach for programming the rapidly expanding range of multicore computers. It allows programmers to express parallelism at a high level and relies on a run-time system and a scheduler to deliver efficiency and scalability. As a result, many programming languages and extensions that support nested parallelism have been developed, including in C/C++, Java, Haskell, and ML. Yet, writing efficient and scalable nested parallel programs remains challenging, primarily due to difficult concurrency bugs arising from destructive updates or effects. For decades, researchers have argued that functional programming can simplify writing parallel programs by allowing more control over effects but functional programs continue to underperform in comparison to parallel programs written in lower-level languages. The fundamental difficulty with functional languages is that they have high demand for memory, and this demand only grows with parallelism.In this paper, we identify a memory property, called disentanglement, of nested-parallel programs, and propose memory management techniques for improved efficiency and scalability. Disentanglement allows for (destructive) effects as long as concurrently executing threads do not gain knowledge of the memory objects allocated by each other. We formally define disentanglement by considering an ML-like higher-order language with mutable references and presenting a dynamic semantics for it that enables reasoning about computation graphs of nested parallel programs. Based on this graph semantics, we formalize a classic correctness property---determinacy race freedom---and prove that it implies disentanglement. This establishes that disentanglement applies to a relatively broad class of parallel programs. We then propose memory management techniques for nested-parallel programs that take advantage of disentanglement for improved efficiency and scalability. We show that these techniques are practical by extending the MLton compiler for Standard ML to support this form of nested parallelism. Our empirical evaluation shows that our techniques are efficient and scale well.
登录
查看更多内容
已证明良好且实用高效的 Fork-Join 程序并行竞争检测
DOI：
10.1145/2935764.2935801
发表时间：
2016
期刊：
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Utterback, Robert;Agrawal, Kunal;Fineman, Jeremy T.;Lee, I-Ting Angelina
通讯作者：
Lee, I-Ting Angelina
响应式并行计算：桥接竞争线程和协作线程
DOI：
10.1145/3062341.3062370
发表时间：
2017
期刊：
Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Stefan K. Muller;Umut A. Acar;R. Harper
通讯作者：
R. Harper
耦合内存和计算以进行位置管理
DOI：
10.4230/lipics.snapl.2015.1
发表时间：
2015
期刊：
ACM Trans. Program. Lang. Syst.
影响因子：
--
作者：
Umut A. Acar;G. Blelloch;M. Fluet;Stefan K. Muller;R. Raghunathan
通讯作者：
R. Raghunathan
一种高效的并行无序深度优先搜索算法
DOI：
10.1145/2807591.2807651
发表时间：
2015
期刊：
SC15: International Conference for High Performance Computing, Networking, Storage and Analysis
影响因子：
--
作者：
Umut A. Acar;A. Charguéraud;Mike Rainey
通讯作者：
Mike Rainey
DOI：
10.7591/cornell/9781501738494.003.0044
发表时间：
2019
期刊：
Architects
影响因子：
--
作者：
Thomas Yarrow
通讯作者：
Thomas Yarrow