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

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

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.