Program Optimization with Data-Specific Compilation

以稀疏矩阵为例的不规则数据结构在现代计算中是必不可少的：它们在从物理模拟到图形处理的众多科学应用中都是核心。一个关键的挑战是为不规则结构上的计算提供高性能的实现，这些结构通常使用额外的数组来显式存储结构中非零元素的坐标。该项目的新颖性解决了代码定制的下一个机会，开发了一种新的特定于数据的编译方法，该方法针对输入数据结构中的独特稀疏模式进行了定制。该项目设计并完全自动化了特定于数据的编译技术，这些技术可以发现和利用稀疏结构中隐藏的规律性，从而降低开发成本以产生高性能的实现。该项目的影响还包括将不规则数据结构建模为(分段)规则结构的联合的新颖理论结果和实用算法，利用这种表示法来提高应用程序性能。在机器学习中，稀疏连接的神经网络可以直接受益于这种特定于数据的编译方法，从而能够开发针对深层网络的改进的推理实现。具体地说，该项目开发了新的理论和算法来使用分层多面体的并集来表示稀疏数据结构：非零坐标的列表可以被压缩成专门的、更紧凑的仿射函数，当评估时，将准确地生成输入坐标列表。研究人员根据SIMD引擎原理瞄准了一系列不同的硬件加速器，并通过使用成本驱动但独立于机器的算法来搜索优化实现，从而促进了性能的可移植性。制作的工具以开源BSD许可软件的形式公开提供。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Irregular data structures, as exemplified with sparse matrices, are essential in modern computing: they are central in numerous scientific applications, ranging from physics simulation to graph processing. A key challenge is to deliver high-performance implementations for computations on irregular structures, which typically use additional arrays to store explicitly the coordinates of non-zero elements in the structure. The project's novelties address the next opportunity for code customization by developing a new kind of data-specific compilation approach that is customized to the unique sparsity pattern in the input data structures. This project designs and fully automates data-specific compilation techniques that can discover and exploit hidden regularity in sparse structures, reducing the development cost to produce high-performance implementations. The project's impacts also include novel theoretical results and practical algorithms to model irregular data structures as a union of (piecewise-)regular structures, exploiting this representation for increased application performance. In machine learning, sparsely connected neural networks can directly benefit from this data-specific compilation approach, enabling the development of improved inference implementations for deep networks.Specifically, the project develops new theory and algorithms to represent sparse data structures using unions of hierarchical polyhedra: the list of non-zero coordinates can be compressed into specialized and more compact affine functions that, when evaluated, would generate exactly the input list of coordinates. The investigators target a range of different hardware accelerators based on SIMD engine principles, and facilitate performance portability by using cost-driven yet machine-independent algorithms to search for optimized implementations. Tools produced are made publicly available as open-source BSD-licensed software.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.