SHF: Medium: Algorithmic lambda-Calculus for the Design, Analysis, and Implementation of Parallel Algorithms

SHF：Medium：用于并行算法设计、分析和实现的算法 lambda 演算

基本信息

批准号：
1901381
负责人：
Guy Blelloch
金额：
$ 119.98万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1901381&HistoricalAwards=false
关键词：
SHF Medium Algorithmic lambda Calculus

项目摘要

The hardware advances of recent years have brought multicore chips and parallel computing to the mainstream. While there have been many advances in parallel software for such multicore chips over the past decade, there is still no satisfactory model for analyzing the performance of parallel algorithms. In particular, and unlike the case for sequential algorithms, there is a gap between cost models for estimating performance of algorithms and easy to use programming models for implementing the algorithms. This project is developing a practical approach to parallel algorithms by bringing together two fundamental but distinct theories of computing---one based on machine models and following the work that dates back to Dr. Alan Turing, and the other based on language models and following the work that dates back to Dr. Alonzo Church. The novelty of the project is in combining these two theories, for which there is currently a large rift. The impact of the project is in making significant steps in simplifying the design and analysis of parallel algorithms, and better understanding of the relationship between the two theories of computing. The educational component of this project involves teaching undergraduates parallel algorithms and creates ample opportunities to test the practical effectiveness of the proposed approach, along with concrete efforts to broaden participation in computing through programs at Carnegie-Mellon University.The work is following an end-to-end methodology bridging Church and Turing's theories along with practice. On the theory side, the project is developing a calculus called the ``algorithmic lambda-calculus,'' that equips Church's lambda-calculus with a cost semantics, making it possible to reason about the total work and parallel span (time) of programs, which in turn can be used to understand the performance of algorithms, at least asymptotically. To show that this calculus is realizable, the project is theoretically establishing that the calculus is faithful to a transition semantics, which can then be efficiently realized on an abstract machine such as the Parallel-RAM. On the practical side, the project is developing a programming language and a compiler that faithfully implements this theory. The project is also extending the algorithmic lambda-calculus, the realizability theorems, and the implementation to support important features such as aggregate parallel data structures, interaction, and different forms of parallelism.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.

近年来的硬件进步为主流带来了多芯片和并行计算。尽管在过去十年中，对于此类多项芯片的并行软件有很多进展，但仍没有令人满意的模型来分析并行算法的性能。特别是，与顺序算法不同，估计算法性能的成本模型与易于使用的编程模型之间存在差距。该项目正在通过将两个基本但独特的计算理论汇总到基于机器模型的基本理论，并遵循艾伦·图灵（Alan Turing）博士，另一个基于语言模型，并遵循追溯到Alonzo Church博士的工作。该项目的新颖性在于将这两种理论结合在一起，目前有一个很大的裂痕。该项目的影响是在简化并行算法的设计和分析方面做出重要步骤，并更好地理解计算的两种理论之间的关系。该项目的教育组成部分涉及教学本科生平行算法，并创造了足够的机会来测试拟议方法的实际有效性，以及具体的努力，通过在卡内基 - 梅隆大学通过计划来扩展计算。这项工作是在始终的终端方法论培养教会和蒂宁的理论之后。在理论方面，该项目正在开发一个称为``算法的lambda-calculus''的微积分，它使教堂的lambda-calculus拥有成本语义，使得可以理解总的工作和平行工作（时间），而这些程序又可以用来理解Algorithms的表现，至少是ASMPTESS的表现。为了证明这种演算是可以实现的，从理论上讲，该项目是忠实于过渡语义的演算，然后可以在抽象的机器（例如Parallel-RAM）上有效地实现。从实际方面来说，该项目正在开发一种编程语言和忠实地实现该理论的编译器。该项目还扩展了算法的lambda-calculus，可靠性理论以及支持重要功能的实施，例如总体数据结构，交互和不同形式的并行性。该奖项反映了NSF的立法使命，并以基础的智力评估和广泛的评论值得评估。

项目成果

期刊论文数量（27）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Program equivalence for assisted grading of functional programs

功能程序辅助评分的程序等效性

DOI：
10.1145/3428239
发表时间：
2020
期刊：
Proceedings of the ACM on Programming Languages
影响因子：
0
作者：
Clune, Joshua;Ramamurthy, Vijay;Martins, Ruben;Acar, Umut A.
通讯作者：
Acar, Umut A.

Parallelism in Randomized Incremental Algorithms

DOI：
10.1145/3402819
发表时间：
2020-10-01
期刊：
JOURNAL OF THE ACM
影响因子：
2.5
作者：
Blelloch, Guy E.;Gu, Yan;Sun, Yihan
通讯作者：
Sun, Yihan

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
影响因子：
0
作者：
Wilkins, Michael;Westrick, Sam;Kandiah, Vijay;Bernat, Alex;Suchy, Brian;Deiana, Enrico Armenio;Campanoni, Simone;Acar, Umut A.;Dinda, Peter;Hardavellas, Nikos
通讯作者：
Hardavellas, Nikos

Provably space-efficient parallel functional programming

经证明节省空间的并行函数式编程