CAREER: Towards Practical Deterministic Parallel Languages

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

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.