Program Optimization with Data-Specific Compilation

通过特定于数据的编译来优化程序

• 批准号: 2009020
• 负责人: Louis-Noel Pouchet
• 金额: $ 44.99万
• 依托单位: Colorado State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2009020&HistoricalAwards=false
• 关键词: Program; Optimization; Data; Specific; Compilation

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.

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

项目成果

Custom High-Performance Vector Code Generation for Data-Specific Sparse Computations

• DOI: 10.1145/3559009.3569668
• 发表时间: 2022-10
• 期刊: Proceedings of the International Conference on Parallel Architectures and Compilation Techniques
• 作者: Marcos Horro;L. Pouchet;Gabriel Rodríguez;J. Touriño

MARTA: Multi-configuration Assembly pRofiler and Toolkit for performance Analysis

MARTA：用于性能分析的多配置装配配置文件和工具包

• DOI: 10.1109/ispass55109.2022.00008
• 发表时间: 2022
• 期刊: 2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS
• 作者: Horro, Marcos;Pouchet, Louis-Noel;RodriDguez, Gabriel;Tourino, Juan
• 通讯作者: Tourino, Juan

FOURST: A code generator for FFT-based fast stencil computations

第四：用于基于 FFT 的快速模板计算的代码生成器

• DOI: 10.1109/ispass55109.2022.00010
• 发表时间: 2022
• 期刊: ACM International Symposium on Performance Analysis of Systems and Software (ISPASS
• 作者: Ahmad, Zafar;Javanmard, Mohammad Mahdi;Croisdale, Gregory;Gregory, Aaron;Ganapathi, Pramod;Pouchet, Louis-Noel;Chowdhury, Rezaul
• 通讯作者: Chowdhury, Rezaul

Representing Integer Sequences Using Piecewise-Affine Loops

使用分段仿射循环表示整数序列

• DOI: 10.3390/math9192368
• 发表时间: 2021
• 期刊: Mathematics
• 影响因子: 2.4
• 作者: Rodríguez, Gabriel;Pouchet, Louis-Noël;Touriño, Juan
• 通讯作者: Touriño, Juan