Provably space-efficient parallel functional programming
Provably space-efficient parallel functional programming
复制标题
经证明节省空间的并行函数式编程
DOI：
10.1145/3434299
复制
发表时间：
2021
影响因子：
--
通讯作者：
Acar, Umut A.
中科院分区：
文献类型：
--
作者：
Arora, Jatin;Westrick, Sam;Acar, Umut A.
由于函数式编程具有许多理想的特性，例如控制效果以及潜在的灾难性竞争条件的能力，因此函数式编程为现代多核计算机编程提供了一种可行的方法。在过去的十年中，已经开发了几种并行函数语言，通常基于 ML 和 Haskell 的方言。然而，这些语言传统上表现不佳的过程语言（例如 C 和 Java）。造成这种情况的主要原因是它们对内存的渴望，这种渴望只会随着并行性的增加而增长，导致传统的内存管理技术在内存需求的增加下崩溃。最近的工作通过识别确定性无竞争并行程序的内存属性（称为解缠结）打开了解决此问题的新角度，它限制了有关彼此内存分配的并发计算的知识。这项工作在提供良好的时间可扩展性方面表现出了一些希望。在本文中，我们提出了可证明的空间高效的自动内存管理技术，用于确定性无竞争的函数式并行程序，允许纯粹的和命令式的程序，其中内存可能会被破坏性地更新。我们证明，对于具有 R* 顺序内存的程序，任何 P 处理器垃圾收集并行运行最多需要 O(R*·P) 内存。我们还证明了 P 处理器执行的工作范围为 O(W+R*P)，同时也考虑了垃圾收集的成本。为了实现这些结果，我们将线程调度与内存管理集成起来。这个想法是将内存分配和垃圾收集与线程调度决策相协调，以便每个处理器可以在不同步的情况下分配内存，并通过咨询我们制定的收集策略来独立收集一部分内存。收集策略是完全分布式的，不需要与其他处理器进行通信。我们通过将其作为并行 ML 的 MPL 编译器的扩展来实现，证明了该方法的实用性。我们的实验结果证实了我们的理论界限，并表明这些技术的性能和扩展性良好。
Because of its many desirable properties, such as its ability to control effects and thus potentially disastrous race conditions, functional programming offers a viable approach to programming modern multicore computers. Over the past decade several parallel functional languages, typically based on dialects of ML and Haskell, have been developed. These languages, however, have traditionally underperformed procedural languages (such as C and Java). The primary reason for this is their hunger for memory, which only grows with parallelism, causing traditional memory management techniques to buckle under increased demand for memory. Recent work opened a new angle of attack on this problem by identifying a memory property of determinacy-race-free parallel programs, called disentanglement, which limits the knowledge of concurrent computations about each other’s memory allocations. The work has showed some promise in delivering good time scalability.In this paper, we present provably space-efficient automatic memory management techniques for determinacy-race-free functional parallel programs, allowing both pure and imperative programs where memory may be destructively updated. We prove that for a program with sequential live memory ofR*, anyP-processor garbage-collected parallel run requires at mostO(R*·P) memory. We also prove a work bound ofO(W+R*P) forP-processor executions, accounting also for the cost of garbage collection. To achieve these results, we integrate thread scheduling with memory management. The idea is to coordinate memory allocation and garbage collection with thread scheduling decisions so that each processor can allocate memory without synchronization and independently collect a portion of memory by consulting a collection policy, which we formulate. The collection policy is fully distributed and does not require communicating with other processors. We show that the approach is practical by implementing it as an extension to the MPL compiler for Parallel ML. Our experimental results confirm our theoretical bounds and show that the techniques perform and scale well.
登录
查看更多内容
DOI：
10.1145/301618.301648
发表时间：
1999-05
期刊：
Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages
影响因子：
--
作者：
G. Blelloch;P. Cheng
通讯作者：
G. Blelloch;P. Cheng
已证明良好且实用高效的 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
Dag-calculus：并行计算的微积分
DOI：
--
发表时间：
2016
期刊：
ACM SIGPLAN International Conference on Functional Programming
影响因子：
--
作者：
Umut A. Acar;A. Charguéraud;Mike Rainey;Filip Sieczkowski
通讯作者：
Filip Sieczkowski
响应式并行计算：桥接竞争线程和协作线程
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