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

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

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.