一句话：提出动态检测并行函数式程序中纠缠的技术，并证明其可靠性且实现近乎零开销。
并行函数式编程的并行内存管理器依赖 disentanglement（解缠）性质来保证高效的工作与空间复杂度，但此前没有技术能确保该性质，程序员需自行推理底层内存分配与访问。本文提出运行时动态检测 entanglement（纠缠）的技术：为带引用的函数式语言给出动态语义，通过查询程序中的并行与顺序依赖关系来检查纠缠，且仅需检查可变对象；作者证明了该动态语义的可靠性，并给出剪枝大量检测的高效实现及 work/space 界。该技术在 Parallel ML 的 MPL 编译器中实现，多个基准测试在最多 72 核上平均时间与空间开销低于 5%，表明纠缠检测成本可忽略，可常开部署。
Recent research on parallel functional programming has culminated in a provably efficient (in work and space) parallel memory manager, which has been incorporated into the MPL (MaPLe) compiler for Parallel ML and shown to deliver practical efficiency and scalability. The memory manager exploits a property of parallel programs called disentanglement, which restricts computations from accessing concurrently allocated objects. Disentanglement is closely related to race-freedom, but subtly differs from it. Unlike race-freedom, however, no known techniques exists for ensuring disentanglement, leaving the task entirely to the programmer. This is a challenging task, because it requires reasoning about low-level memory operations (e.g., allocations and accesses), which is especially difficult in functional languages. In this paper, we present techniques for detecting entanglement dynamically, while the program is running. We first present a dynamic semantics for a functional language with references that checks for entanglement by consulting parallel and sequential dependency relations in the program. Notably, the semantics requires checks for mutable objects only. We prove the soundness of the dynamic semantics and present several techniques for realizing it efficiently, in particular by pruning away a large number of entanglement checks. We also provide bounds on the work and space of our techniques. We show that the entanglement detection techniques are practical by implementing them in the MPL compiler for Parallel ML. Considering a variety of benchmarks, we present an evaluation and measure time and space overheads of less than 5% on average with up to 72 cores. These results show that entanglement detection has negligible cost and can therefore remain deployed with little or no impact on efficiency, scalability, and space.
@article{paperbot1495,
title = {Entanglement detection with near-zero cost},
author = {Sam Westrick and Jatin Arora and Umut A. Acar},
journal = {Proceedings of the ACM on Programming Languages},
volume = {6},
number = {ICFP},
year = {2022},
doi = {10.1145/3547646}
}