CAREER: The Exocompiler: Decoupling Algorithms from the Organization of Computation and Data

职业：Exocompiler：将算法与计算和数据的组织解耦

• 批准号: 2328543
• 负责人: Jonathan Ragan-Kelley
• 金额: $ 52.54万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-03-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2328543&HistoricalAwards=false
• 关键词: CAREER; Exocompiler; Decoupling; Algorithms; Organization

The performance of many important algorithms is dominated by the way their computations and data are organized for execution on specific hardware. Traditional ways of programming conflate algorithms and their organization such that a straightforward implementation is unacceptably slow. At the same time, neither one can be written or optimized independently, which limits the productivity of programmers and the portability of programs to future hardware. Optimized organizations are often an order of magnitude faster and more complex since they necessarily take a global, rather than per-operation, view of the algorithm to exploit parallelism and locality. This project's novelty is in creating a new kind of programming language in which the algorithm and its organization are decoupled from one another. Programming systems are the tool through which computation is applied to human problems. The project's impact will be transforming the way major classes of software are written, enabling a wider range of people to more productively write new algorithms which are both high-performance and portable to future computing hardware. This project explores a programming model that decouples algorithms from their organization, represented explicitly in the language as a "schedule." It extends this paradigm from multidimensional arrays to more general computations and data structures, including sparse matrices and graphs, and builds a machine-learning system to automatically find schedules competitive with human experts. To realize this vision, it pursues four major research directions: (a) combining tree search with neural networks in a reinforcement learning system to automatically find expert-quality schedules; (b) broadening the class of expressible computations and schedules to include general loops and program gradients; (c) broadening the class of data structures and schedules with a relational model to process sparse and linked data; and (d) creating a comprehensive performance benchmark suite to serve as our evaluation testbed, and also be shared broadly to foster new research in systems, compilers, and architecture. The resulting language and compiler enables productive high-performance programming and provides a powerful foundation for easily building new domain-specific programming systems.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.

许多重要算法的性能取决于其计算和数据在特定硬件上执行的组织方式。传统的编程方式将算法及其组织混为一谈，因此简单的实现速度慢得令人无法接受。同时，两者都不能独立编写或优化，这限制了程序员的生产力以及程序向未来硬件的可移植性。优化的组织通常速度更快、更复杂一个数量级，因为它们必须采用全局而不是每个操作的算法视图来利用并行性和局部性。该项目的新颖之处在于创建了一种新型编程语言，其中算法及其组织相互解耦。编程系统是将计算应用于人类问题的工具。该项目的影响将改变主要类别软件的编写方式，使更多人能够更高效地编写高性能且可移植到未来计算硬件的新算法。该项目探索了一种将算法与其组织解耦的编程模型，在语言中明确表示为“时间表”。它将这种范式从多维数组扩展到更通用的计算和数据结构，包括稀疏矩阵和图形，并构建了一个机器学习系统来自动找到与人类专家竞争的时间表。为了实现这一愿景，它追求四个主要研究方向：（a）在强化学习系统中将树搜索与神经网络相结合，以自动查找专家质量的时间表； (b) 扩大可表达计算和调度的类别，以包括一般循环和程序梯度； (c) 通过关系模型扩大数据结构和时间表的类别，以处理稀疏和链接的数据； (d) 创建一个全面的性能基准套件作为我们的评估测试平台，并广泛共享以促进系统、编译器和架构方面的新研究。由此产生的语言和编译器可实现高效的高性能编程，并为轻松构建新的特定领域编程系统提供强大的基础。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查进行评估，被认为值得支持标准。

项目成果

Gradient Descent: The Ultimate Optimizer

梯度下降：终极优化器

• 发表时间: 2022-12
• 期刊: Advances in neural information processing systems
• 作者: Chandra, Kartik;Xie, Audrey;Ragan;Meijer, Erik
• 通讯作者: Meijer, Erik

Designing Perceptual Puzzles by Differentiating Probabilistic Programs

通过区分概率程序来设计感知谜题

• DOI: 10.1145/3528233.3530715
• 发表时间: 2022-08
• 期刊: ACM SIGGRAPH Conference Proceedings
• 作者: Chandra, Kartik;Li, Tzu;Tenenbaum, Joshua;Ragan
• 通讯作者: Ragan

SLANG.D: Fast, Modular and Differentiable Shader Programming

SLANG.D：快速、模块化和可微分的着色器编程

• DOI: 10.1145/3618353
• 发表时间: 2023-12
• 期刊: ACM Transactions on Graphics
• 影响因子: 6.2
• 作者: Bangaru, Sai Praveen;Wu, Lifan;Li, Tzu;Munkberg, Jacob;Bernstein, Gilbert;Ragan;Durand, Frédo;Lefohn, Aaron;He, Yong
• 通讯作者: He, Yong

Acting as Inverse Inverse Planning

充当逆向规划

• DOI: 10.1145/3588432.3591510
• 发表时间: 2023-07
• 期刊: ACM
• 作者: Chandra, Kartik;Li, Tzu;Tenenbaum, Joshua;Ragan
• 通讯作者: Ragan