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

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

• 批准号: 2107289
• 负责人: Stefan Muller
• 金额: $ 26.29万
• 依托单位: Illinois Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2107289&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的桌面客户端，游戏，游戏和各种移动应用程序。这项研究的端到端目标需要类型系统，编程语言，调度理论和运行时系统的进步。研究团队将开发一个微积分，用于在高水平的抽象中对交互式平行应用进行建模。该微积分将根据教堂的lambda conculus配备一种完全普遍的正式编程语言，并具有成本语义，使得1）表达交互式并行应用，以及2）对程序的吞吐量和响应性进行推理。类型系统将确保缺乏棘手的错误，例如优先倒置，可以防止确定响应能力保证。调查人员将通过开发可以忠实地匹配成本语义的调度算法来证明该计算是可以实现的，以确保所需的性能标准。在实际方面，项目团队将扩展基于C的平行编程语言CILK，以支持交互式并行应用程序。这将需要开发一个运行时系统，该系统忠实地实现计划算法和优化，以确保实际性能。该项目的教育组成部分涉及教学本科生并行算法，它将创造足够的机会来测试拟议方法的实际有效性。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准来通过评估来支持的。

项目成果

Responsive Parallelism with Synchronization

响应式并行与同步

• DOI: 10.1145/3591249
• 发表时间: 2023
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Muller, Stefan K.;Singer, Kyle;Keeney, Devyn Terra;Neth, Andrew;Agrawal, Kunal;Lee, I-Ting Angelina;Acar, Umut A.
• 通讯作者: Acar, Umut A.

Static prediction of parallel computation graphs

并行计算图的静态预测

• DOI: 10.1145/3498708
• 发表时间: 2022
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Muller, Stefan K.