Collaborative Research: SHF: Medium: Responsive Parallelism for Interactive Applications: Theory and Practice

协作研究：SHF：媒介：交互式应用程序的响应式并行性：理论与实践

• 批准号: 2107241
• 负责人: Umut Acar
• 金额: $ 34.83万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2107241&HistoricalAwards=false
• 关键词: Collaborative; Research; SHF; Medium; Responsive

The hardware advances of recent years have brought multicore chips and parallel computing to the mainstream. As a result, today, parallelism is not found just in the traditional scientific applications that have dominated research and development in parallel computing in past decades. We must now consider parallelism in interactive applications which are characterized by frequent interactions with users or other software systems and therefore must be responsive. This project’s aim is to develop a practical approach to interactive parallel applications. The project’s novelty, in addition to focusing on this under-studied intersection of parallelism and interaction, is that it follows an end-to-end methodology that brings together many areas of computer science and bridges theory with practice. The project has the potential to impact the design of several application areas that require large-scale interactive applications, including web services, desktop clients for CAD/CAM, games, and a variety of mobile applications. This research’s end-to-end goals require advances in type systems, programming languages, scheduling theory, and runtime systems. The research team will develop a calculus for modeling interactive parallel applications at a high level of abstraction. This calculus will equip a fully general formal programming language based on Church's Lambda Calculus with a cost semantics, making it possible 1) to express interactive parallel applications and 2) to reason about the throughput and responsiveness of the programs. A type system will ensure the absence of thorny bugs such as priority inversions that can prevent establishing responsiveness guarantees. The investigators will prove that this calculus is realizable by developing scheduling algorithms that can faithfully match the cost semantics so as to guarantee the desired performance criteria. On the practical side, the project team will extend Cilk, a C-based parallel programming language, to support interactive parallel applications. This will require developing a run-time system that faithfully implements the scheduling algorithms and optimizations that ensure practical performance. The educational component of this project, which involves teaching undergraduates parallel algorithms, will create ample opportunities to test the practical effectiveness of the proposed approach.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.

近年来硬件的进步使多核芯片和并行计算成为主流。因此，今天，并行性不仅仅存在于过去几十年主导并行计算研究和开发的传统科学应用中。我们现在必须考虑交互式应用程序中的并行性，这些应用程序的特点是与用户或其他软件系统频繁交互，因此必须具有响应能力。 该项目的目标是开发一种实用的交互式并行应用程序方法。 该项目的新颖之处在于，除了关注并行性和交互性这一尚未充分研究的交叉点之外，它还遵循一种端到端的方法，该方法将计算机科学的许多领域结合在一起，并将理论与实践联系起来。 该项目有可能影响需要大规模交互式应用程序的多个应用程序领域的设计，包括 Web 服务、CAD/CAM 桌面客户端、游戏和各种移动应用程序。 这项研究的端到端目标需要类型系统、编程语言、调度理论和运行时系统方面的进步。 研究团队将开发一种微积分，用于在高抽象级别上对交互式并行应用程序进行建模。该演算将为基于 Church 的 Lambda 演算的完全通用的形式编程语言配备成本语义，从而可以 1) 表达交互式并行应用程序，2) 推理程序的吞吐量和响应能力。类型系统将确保不存在棘手的错误，例如可能阻止建立响应性保证的优先级反转。研究人员将证明这种演算可以通过开发能够忠实匹配成本语义的调度算法来实现，从而保证所需的性能标准。 在实践方面，项目团队将扩展基于C的并行编程语言Cilk，以支持交互式并行应用程序。这需要开发一个运行时系统，忠实地实现调度算法和优化，以确保实际性能。该项目的教育部分涉及向本科生教授并行算法，将为测试所提出方法的实际有效性创造充足的机会。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Efficient Parallel Self-Adjusting Computation

高效并行自调整计算

• DOI: 10.1145/3409964.3461799
• 发表时间: 2021
• 期刊: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA
• 作者: Anderson, Daniel;Blelloch, Guy E.;Baweja, Anubhav;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

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.

Task parallel assembly language for uncompromising parallelism

任务并行汇编语言可实现毫不妥协的并行性

• DOI: 10.1145/3453483.3460969
• 发表时间: 2021
• 期刊: PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
• 作者: Rainey, Mike;Newton, Ryan R.;Hale, Kyle;Hardavellas, Nikos;Campanoni, Simone;Dinda, Peter;Acar, Umut A.
• 通讯作者: Acar, Umut A.

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.