CAREER: Towards Practical Deterministic Parallel Languages

职业：走向实用的确定性并行语言

• 批准号: 1453508
• 负责人: Ryan Newton
• 金额: $ 53.5万
• 依托单位: Indiana University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-02-15 至 2020-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1453508&HistoricalAwards=false
• 关键词: CAREER; Towards; Practical; Deterministic; Parallel

Title: CAREER: Towards Practical Deterministic Parallel LanguagesParallel, multicore processors have become ubiquitous, but parallel programming has not. This gap implies that many everyday programs do not fully use the hardware on which they run. The problem persists because traditional parallel programming approaches are high-risk: a parallel program can yield inconsistent answers, or even crash, due to unpredictable interactions between simultaneous tasks. Certain classes of programs, however, admit strong mathematical guarantees that they will behave the same in spite of parallel execution. That is, they enable deterministic parallel programming. Functional programming, extended with "LVars" --shared-state data structures that support commutating operations-- is one such model. While this theoretical model has been proven deterministic, significant questions remain regarding practical aspects such as efficiency and scalability. This research addresses those questions by developing new LVar data structures and scaling them to larger distributed memory machines. The intellectual merits are in the development of novel algorithms that support parallel programming. Further, the LVar model provides a new lens through which to view problems in parallel programming, which can lead to downstream discoveries. The project's broader significance and importance are (1) its potential to lower the cost and risk of parallel programming and (2) its educational goal: to employ deterministic parallel programming in the introductory programming course at both a university level, and in K-12 education. Changing how programming is taught may be necessary for leveraging hardware parallelism to become a normal and unexceptional part of writing software.Three specific technical challenges are addressed in this research. First, LVars traditionally require more storage space over time, because "delete" operations do not commute with others. Semantically, the state-space of each LVar forms a join semi-lattice and all modifications must move the state "upwards" monotonically. Nevertheless, this project investigates new ways that LVars can free memory, using a concept of Saturating LVars. Second, this research seeks to formalize the relationship of LVar-based parallel programs to their purely functional counterparts, characterizing asymptotic performance advantages. Finally, this project explores the scalability of LVar-based programming abstractions in a distributed memory setting, where they share similarities with recent distributed programming constructs such as concurrent replicated data structures.

标题：职业：走向实用的确定性并行语言并行、多核处理器已经变得无处不在，但并行编程却还没有。这种差距意味着许多日常程序没有充分利用它们运行的​​硬件。这个问题仍然存在，因为传统的并行编程方法具有高风险：由于同时任务之间不可预测的交互，并行程序可能会产生不一致的答案，甚至崩溃。 然而，某些类别的程序承认强有力的数学保证，尽管并行执行，它们的行为仍然相同。也就是说，它们支持确定性并行编程。用“LVars”（支持交换操作的共享状态数据结构）扩展的函数式编程就是这样的模型之一。虽然该理论模型已被证明是确定性的，但在效率和可扩展性等实际方面仍然存在重大问题。这项研究通过开发新的 Lvar 数据结构并将其扩展到更大的分布式内存机器来解决这些问题。智力优势在于开发支持并行编程的新颖算法。此外，LVar 模型提供了一个新的视角，通过它来查看并行编程中的问题，这可以导致下游发现。该项目更广泛的意义和重要性在于 (1) 降低并行编程成本和风险的潜力，以及 (2) 其教育目标：在大学和 K-12 的入门编程课程中采用确定性并行编程教育。为了利用硬件并行性成为编写软件的正常且普通的部分，改变编程的教学方式可能是必要的。本研究解决了三个具体的技术挑战。首先，随着时间的推移，Lvar 传统上需要更多的存储空间，因为“删除”操作不会与其他操作交换。从语义上讲，每个 LVar 的状态空间形成一个连接半格子，所有修改都必须单调“向上”移动状态。尽管如此，该项目使用饱和 LVar 的概念，研究了 LVar 释放内存的新方法。其次，本研究旨在形式化基于 LVar 的并行程序与其纯函数对应程序的关系，表征渐近性能优势。最后，该项目探讨了分布式内存设置中基于 LVar 的编程抽象的可扩展性，它们与最近的分布式编程结构（例如并发复制数据结构）有相似之处。

项目成果

Generic and flexible defaults for verified, law-abiding type-class instances

经过验证、遵守法律的类型类实例的通用且灵活的默认值

• DOI: 10.1145/3331545.3342591
• 发表时间: 2019
• 期刊: Haskell 2019: Proceedings of the 12th ACM SIGPLAN International Symposium on Haskell
• 作者: Scott, Ryan G.;Newton, Ryan R.
• 通讯作者: Newton, Ryan R.