Entanglement detection with near-zero cost
Entanglement detection with near-zero cost
复制标题
近乎零成本的纠缠检测
DOI：
10.1145/3547646
复制
发表时间：
2022
影响因子：
--
通讯作者：
Acar, Umut A.
中科院分区：
文献类型：
--
作者：
Westrick, Sam;Arora, Jatin;Acar, Umut A.
最近对并行函数式编程的研究已经在一个可证明有效的（在工作和空间）并行内存管理器中达到高潮，该管理器已被纳入并行ML的MPL（MaPLe）编译器中，并显示出实际的效率和可扩展性。内存管理器利用并行程序的一个属性，称为解纠缠，它限制了计算访问并发分配的对象。解纠缠与种族自由密切相关，但又有微妙的区别。然而，与种族自由不同的是，没有已知的技术可以确保解纠缠，将任务完全留给程序员。这是一项具有挑战性的任务，因为它需要对低级存储器操作进行推理（例如，分配和访问），这是特别困难的函数式语言。在本文中，我们提出的技术动态检测纠缠，而程序运行。我们首先提出了一个动态语义的函数式语言的引用，检查纠缠咨询并行和顺序依赖关系的程序。值得注意的是，语义只要求检查可变对象。我们证明了动态语义的合理性，并提出了几种有效地实现它的技术，特别是通过修剪掉大量的纠缠检查。通过在并行机器学习的MPL编译器中的实现，我们证明了纠缠检测技术的实用性。考虑到各种基准测试，我们提出了一个评估和测量的时间和空间开销平均不到5%，最多72个核心。这些结果表明，纠缠检测的成本可以忽略不计，因此可以保持部署，对效率，可扩展性和空间几乎没有影响。
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.
登录
查看更多内容
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
响应式并行计算：桥接竞争线程和协作线程
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
将并行性改造到 OCaml 上
DOI：
--
发表时间：
2020
期刊：
Proc. ACM Program. Lang.
影响因子：
--
作者：
K. Sivaramakrishnan;Stephen Dolan;Leo White;S. Jaffer;T. Kelly;Anmol Sahoo;S. Parimala;Atul Dhiman;Anil Madhavapeddy
通讯作者：
Anil Madhavapeddy