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教育的入门编程课程中采用确定性并行编程。改变如何编程是必要的，利用硬件并行成为一个正常的和不例外的一部分，编写software.Three具体的技术挑战，在这项研究中得到解决。首先，LVars传统上随着时间的推移需要更多的存储空间，因为“删除”操作不与其他操作交换。在语义上，每个LVar的状态空间形成连接半格，并且所有修改必须单调地将状态“向上”移动。然而，这个项目研究了LVars可以释放内存的新方法，使用饱和LVars的概念。其次，本研究旨在正式的关系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.