SHF: Small: Solving the Parallel Functional Programming Challenge

SHF：小型：解决并行函数式编程挑战

• 批准号: 2115104
• 负责人: Umut Acar
• 金额: $ 44.98万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-15 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2115104&HistoricalAwards=false
• 关键词: SHF; Small; Solving; Parallel; Functional

Nearly all computers today ranging from mobile devices to servers are multicore systems that contain as many as hundreds of cores. Many applications therefore demand parallel software, but parallel programming is understood and practiced by few expert programmers (it is simply too hard). Researchers have argued for decades that functional programming can be a game changer for parallel programming, because functional programs can be parallel by default, and in principle require no additional effort for parallelization. However, functional languages have been unable to deliver the efficiency and performance expected of parallel programs. Prior research has identified memory management as the key performance bottleneck in functional programs. This project aims to solve this problem. The projects novelties are 1) a theory of "disentanglement" that, based on the principles of parallel programming, unlocks efficient and scalable memory management 2) techniques for detecting and handling entanglement dynamically on the fly and 3) provably and practically efficient memory-management techniques. The projects impacts are 1) development of the foundations for parallel programming that could enable everyday programmers to write performant parallel programs and 2) development of educational materials for teaching undergraduate students about parallel algorithms and programming.To achieve these goals, the project develops a technique for organizing the memory as a hierarchy of heaps, which may be managed independently and in parallel, except when entanglement arises due to non-deterministic accesses to mutable data. To handle entanglement, the project develops techniques for detecting it during run-time, and handling it so that parallel execution can continue unimpeded. The project then presents space, work, and run-time bounds that take the cost of memory management into account. Even though such bounds are critical for all languages, including procedural ones, they are under-studied. The project assesses the practicality of the techniques by providing an implementation, evaluating it, and integrating it into education.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

如今，从移动的设备到服务器，几乎所有的计算机都是包含多达数百个内核的多核系统。 因此，许多应用程序需要并行软件，但并行编程很少被专业程序员理解和实践（这太难了）。几十年来，研究人员一直认为函数式编程可以改变并行编程的游戏规则，因为函数式程序在默认情况下可以并行，并且原则上不需要额外的并行化工作。 然而，函数式语言一直无法提供并行程序所期望的效率和性能。 先前的研究已经确定内存管理是函数式程序中的关键性能瓶颈。 本项目旨在解决这一问题。 该项目的创新之处在于：1）基于并行编程原理的“解纠缠”理论，解锁了高效和可扩展的内存管理; 2）动态检测和处理纠缠的技术; 3）可证明和实际有效的内存管理技术。 该项目的影响是：1）开发并行编程的基础，使日常程序员能够编写高性能的并行程序; 2）开发用于教授本科生并行算法和编程的教育材料。为了实现这些目标，该项目开发了一种将内存组织为堆层次结构的技术，可以独立并行管理，除了当由于对可变数据的非确定性访问而引起纠缠时。为了处理纠缠，该项目开发了在运行时检测它的技术，并处理它，以便并行执行可以继续畅通无阻。然后，该项目将显示空间、工作和运行时界限，这些界限将内存管理的成本考虑在内。 尽管这样的界限对所有语言都很重要，包括过程语言，但它们的研究还不够。该项目通过提供一个实施方案，对其进行评估，并将其融入教育来评估技术的实用性。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Entanglement detection with near-zero cost

近乎零成本的纠缠检测

• DOI: 10.1145/3547646
• 发表时间: 2022
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Westrick, Sam;Arora, Jatin;Acar, Umut A.
• 通讯作者: Acar, Umut A.

WARDen: Specializing Cache Coherence for High-Level Parallel Languages

WARDen：专门针对高级并行语言的缓存一致性

• DOI: 10.1145/3579990.3580013
• 发表时间: 2023
• 期刊: Proceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization
• 作者: Wilkins, Michael;Westrick, Sam;Kandiah, Vijay;Bernat, Alex;Suchy, Brian;Deiana, Enrico Armenio;Campanoni, Simone;Acar, Umut A.;Dinda, Peter;Hardavellas, Nikos
• 通讯作者: Hardavellas, Nikos

Efficient Parallel Functional Programming with Effects

带效果的高效并行函数编程

• DOI: 10.1145/3591284
• 发表时间: 2023
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Arora, Jatin;Westrick, Sam;Acar, Umut A.
• 通讯作者: Acar, Umut A.

Quartz: superoptimization of Quantum circuit

Quartz：量子电路的超级优化

• DOI: 10.1145/3519939.3523433
• 发表时间: 2022
• 期刊: PLDI 2022: Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation
• 作者: Xu, Mingkuan;Li, Zikun;Padon, Oded;Lin, Sina;Pointing, Jessica;Hirth, Auguste;Ma, Henry;Palsberg, Jens;Aiken, Alex;Acar, Umut A.
• 通讯作者: Acar, Umut A.