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许可软件公开提供。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

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