一句话：提出可证明空间高效的并行函数式程序自动内存管理，将线程调度与GC结合，实现O(R*·P)空间与良好伸缩。
论文针对并行函数式语言因内存消耗随并行度增长而难以伸缩的问题，基于无确定性竞争的并行程序具有的“解缠”（disentanglement）性质，提出可证明空间高效的自动内存管理技术。作者将线程调度与内存管理集成，使各处理器无需同步即可分配内存，并依据分布式收集策略独立回收部分内存。该方法支持纯函数式与可破坏更新的命令式程序，证明对顺序活内存为 R* 的程序，P 处理器垃圾回收运行的峰值内存至多为 O(R*·P)，工作量为 O(W+R*P)。在 Parallel 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 of R * , any P -processor garbage-collected parallel run requires at most O ( R * · P ) memory. We also prove a work bound of O ( W + R * P ) for P -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.
@article{paperbot1156,
title = {Provably space-efficient parallel functional programming},
author = {Jatin Arora and Sam Westrick and Umut A. Acar},
journal = {Proceedings of the ACM on Programming Languages},
volume = {5},
number = {POPL},
year = {2021},
doi = {10.1145/3434299}
}