SHF: Medium: Algorithmic lambda-Calculus for the Design, Analysis, and Implementation of Parallel Algorithms
SHF:Medium:用于并行算法设计、分析和实现的算法 lambda 演算
基本信息
- 批准号:1901381
- 负责人:
- 金额:$ 119.98万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2019
- 资助国家:美国
- 起止时间:2019-07-01 至 2024-06-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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.
项目成果
期刊论文数量(27)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Program equivalence for assisted grading of functional programs
功能程序辅助评分的程序等效性
- DOI:10.1145/3428239
- 发表时间:2020
- 期刊:
- 影响因子: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
- 期刊:
- 影响因子: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
- 期刊:
- 影响因子: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
经证明节省空间的并行函数式编程
- DOI:10.1145/3434299
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Arora, Jatin;Westrick, Sam;Acar, Umut A.
- 通讯作者:Acar, Umut A.
A cost-aware logical framework
成本意识逻辑框架
- DOI:10.1145/3498670
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Niu, Yue;Sterling, Jonathan;Grodin, Harrison;Harper, Robert
- 通讯作者:Harper, Robert
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Guy Blelloch其他文献
Guy Blelloch的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Guy Blelloch', 18)}}的其他基金
AF: Small: Shared-Memory Parallel Algorithms: Theory and Practice
AF:小型:共享内存并行算法:理论与实践
- 批准号:
1910030 - 财政年份:2019
- 资助金额:
$ 119.98万 - 项目类别:
Standard Grant
SPX: Parallel Models and Algorithms for Emerging Memory Systems
SPX:新兴内存系统的并行模型和算法
- 批准号:
1919223 - 财政年份:2019
- 资助金额:
$ 119.98万 - 项目类别:
Standard Grant
XPS: FULL: Bridging Parallel and Queueing-Theoretic Scheduling
XPS:FULL:桥接并行和排队理论调度
- 批准号:
1629444 - 财政年份:2016
- 资助金额:
$ 119.98万 - 项目类别:
Standard Grant
XPS: FULL: FP: Write-Efficient Parallel Algorithms for Emerging Memory Technologies
XPS:FULL:FP:用于新兴内存技术的写高效并行算法
- 批准号:
1533858 - 财政年份:2015
- 资助金额:
$ 119.98万 - 项目类别:
Standard Grant
SHF: AF: Large: Collaborative Research: Parallelism without Concurrency
SHF:AF:大型:协作研究:无并发的并行性
- 批准号:
1314590 - 财政年份:2013
- 资助金额:
$ 119.98万 - 项目类别:
Continuing Grant
NSF Workshop on Research Directions in the Principles of Parallel Computing
NSF 并行计算原理研究方向研讨会
- 批准号:
1242283 - 财政年份:2012
- 资助金额:
$ 119.98万 - 项目类别:
Standard Grant
SHF: AF: Small: Locality with Dynamic Parallelism
SHF:AF:小:具有动态并行性的局部性
- 批准号:
1018188 - 财政年份:2010
- 资助金额:
$ 119.98万 - 项目类别:
Continuing Grant
ITR/SY+IM+AP: Center for Applied Algorithms
ITR/SY IM AP:应用算法中心
- 批准号:
0122581 - 财政年份:2001
- 资助金额:
$ 119.98万 - 项目类别:
Continuing Grant
ITR: Algorithms: From Theory to Application
ITR:算法:从理论到应用
- 批准号:
0085982 - 财政年份:2000
- 资助金额:
$ 119.98万 - 项目类别:
Standard Grant
Advanced Languages for Scientific Computation Environments
科学计算环境的高级语言
- 批准号:
9706572 - 财政年份:1997
- 资助金额:
$ 119.98万 - 项目类别:
Continuing Grant
相似国自然基金
复合低维拓扑材料中等离激元增强光学响应的研究
- 批准号:12374288
- 批准年份:2023
- 资助金额:52 万元
- 项目类别:面上项目
基于管理市场和干预分工视角的消失中等企业:特征事实、内在机制和优化路径
- 批准号:72374217
- 批准年份:2023
- 资助金额:41.00 万元
- 项目类别:面上项目
托卡马克偏滤器中等离子体的多尺度算法与数值模拟研究
- 批准号:12371432
- 批准年份:2023
- 资助金额:43.5 万元
- 项目类别:面上项目
中等质量黑洞附近的暗物质分布及其IMRI系统引力波回波探测
- 批准号:12365008
- 批准年份:2023
- 资助金额:32 万元
- 项目类别:地区科学基金项目
中等垂直风切变下非对称型热带气旋快速增强的物理机制研究
- 批准号:42305004
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
相似海外基金
Collaborative Research: III: MEDIUM: Responsible Design and Validation of Algorithmic Rankers
合作研究:III:媒介:算法排序器的负责任设计和验证
- 批准号:
2312932 - 财政年份:2023
- 资助金额:
$ 119.98万 - 项目类别:
Standard Grant
Collaborative Research: III: MEDIUM: Responsible Design and Validation of Algorithmic Rankers
合作研究:III:媒介:算法排序器的负责任设计和验证
- 批准号:
2312930 - 财政年份:2023
- 资助金额:
$ 119.98万 - 项目类别:
Standard Grant
Collaborative Research: CIF: Medium: Statistical and Algorithmic Foundations of Distributionally Robust Policy Learning
合作研究:CIF:媒介:分布式稳健政策学习的统计和算法基础
- 批准号:
2312205 - 财政年份:2023
- 资助金额:
$ 119.98万 - 项目类别:
Continuing Grant
AF: Medium:Algorithmic Market Design
AF:媒介:算法市场设计
- 批准号:
2312156 - 财政年份:2023
- 资助金额:
$ 119.98万 - 项目类别:
Continuing Grant
Collaborative Research: III: MEDIUM: Responsible Design and Validation of Algorithmic Rankers
合作研究:III:媒介:算法排序器的负责任设计和验证
- 批准号:
2312931 - 财政年份:2023
- 资助金额:
$ 119.98万 - 项目类别:
Standard Grant