Efficient Parallel Functional Programming with Effects
Efficient Parallel Functional Programming with Effects
复制标题
带效果的高效并行函数编程
DOI：
10.1145/3591284
复制
发表时间：
2023
影响因子：
--
通讯作者：
Acar, Umut A.
中科院分区：
文献类型：
--
作者：
Arora, Jatin;Westrick, Sam;Acar, Umut A.
尽管函数式编程语言通过帮助程序员避免数据竞争来简化编写安全的并行程序，但它们传统上提供的性能很差。最近的工作通过使用分层内存体系结构提高了性能，该体系结构允许处理器在没有任何同步的情况下独立分配和回收内存，从而解决了困扰函数式程序的关键性能挑战。然而，该方法限制了突变或记忆效应，以确保“去纠缠”，这是一种低级别的内存属性，保证了层次结构中不同堆之间的独立性。我们的技术通过区分解缠和纠缠对象来管理纠缠，并保护解缠对象免受纠缠管理成本的影响。我们提出了一种语义，将纠缠形式化为存储对象粒度上的一种属性，并定义了几个代价度量来推理和限定纠缠的时间和空间代价。我们通过扩展并行ML的MPL编译器，给出了这些技术的一个实现。扩展的编译器支持并行ML语言的所有功能，包括无限制的效果。实验表明，与顺序运行相比，MPL的时间和空间开销较小，可伸缩性较好，与C++、Go、Java、OCaml等语言相比具有较强的竞争力。这些结果表明，我们的技术可以将函数式编程的安全益处与性能结合起来。
Although functional programming languages simplify writing safe parallel programs by helping programmers to avoid data races, they have traditionally delivered poor performance. Recent work improved performance by using a hierarchical memory architecture that allows processors to allocate and reclaim memory independently without any synchronization, solving thus the key performance challenge afflicting functional programs. The approach, however, restricts mutation, or memory effects, so as to ensure "disentanglement", a low-level memory property that guarantees independence between different heaps in the hierarchy.This paper proposes techniques for supporting entanglement and for allowing functional programs to use mutation at will. Our techniques manage entanglement by distinguishing between disentangled and entangled objects and shielding disentangled objects from the cost of entanglement management. We present a semantics that formalizes entanglement as a property at the granularity of memory objects, and define several cost metrics to reason about and bound the time and space cost of entanglement. We present an implementation of the techniques by extending the MPL compiler for Parallel ML. The extended compiler supports all features of the Parallel ML language, including unrestricted effects. Our experiments using a variety of benchmarks show that MPL incurs a small time and space overhead compared to sequential runs, scales well, and is competitive with languages such as C++, Go, Java, OCaml. These results show that our techniques can marry the safety benefits of functional programming with performance.
登录
查看更多内容
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
Dag-calculus：并行计算的微积分
DOI：
--
发表时间：
2016
期刊：
ACM SIGPLAN International Conference on Functional Programming
影响因子：
--
作者：
Umut A. Acar;A. Charguéraud;Mike Rainey;Filip Sieczkowski
通讯作者：
Filip Sieczkowski
并行函数数组
DOI：
--
发表时间：
2017
期刊：
ACM-SIGACT Symposium on Principles of Programming Languages
影响因子：
--
作者：
Ananya Kumar;G. Blelloch;R. Harper
通讯作者：
R. Harper
响应式并行计算：桥接竞争线程和协作线程
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
将并行性改造到 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