CAREER: A Unified Compiler for Sparse Array Operations and Relational Algebra

职业：稀疏数组运算和关系代数的统一编译器

• 批准号: 2143061
• 负责人: Fredrik Berg Kjoelstad
• 金额: $ 57.63万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-02-01 至 2027-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2143061&HistoricalAwards=false
• 关键词: CAREER; Unified; Compiler; Sparse; Array

Society is increasingly dependent on scalable data analytics to solve societal and industrial problems. However the data being analyzed and the computers being used are both becoming so diverse and irregular that it is much harder to deliver efficient software. To drive innovation in both data analytics and hardware development, computer systems are needed that take advantage of the structure and sparsity of the data and the capabilities of new hardware. However, taking advantage of these properties and capabilities with current approaches makes the software a lot more complicated. The project's novelties are the development of a software system that automatically specializes itself to combine diverse and irregular data sources and to target diverse hardware. The project's impacts are a 10x-100x performance improvement across a large class of irregular data analytics computations, including sparse tensor algebra, sparse array operations, and relational algebra. Even greater performance improvements will be possible by taking advantage of emerging specialized hardware. The project explores new programming language constructs and a new unified compiler system for sparse tensor algebra, sparse array operations (e.g., sparse NumPy), and relational algebra. The unified compiler combines three separate languages that describe respectively the application logic (e.g., a relational query followed by sparse array operations), the data representations (e.g., relational tries and sparse arrays stored in compressed form), and the organization of the computation (e.g., to target a GPU equipped with specialized tensor processing hardware). To achieve these goals, the project will develop a unified compiler theory for sparse array operations and relational algebra, develop new data representations for relations, and develop techniques to compile these applications to specialized accelerators. Success of this project will lead to new flexible data analytics systems that port across both data structures and hardware and that are orders of magnitude faster than current general approaches without loss of generality.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.

社会越来越依赖可扩展的数据分析来解决社会和工业问题。然而，正在分析的数据和正在使用的计算机都变得如此多样化和不规则，以至于交付高效的软件变得更加困难。为了推动数据分析和硬件开发的创新，需要利用数据的结构和稀疏性以及新硬件的功能的计算机系统。然而，利用当前方法的这些属性和功能会使软件变得更加复杂。该项目的新颖之处在于开发了一个软件系统，该系统自动专门结合不同的和不规则的数据源并针对不同的硬件。该项目的影响是将一大类不规则数据分析计算（包括稀疏张量代数、稀疏数组运算和关系代数）的性能提高 10 倍到 100 倍。通过利用新兴的专用硬件，甚至可以实现更大的性能改进。该项目探索新的编程语言结构和用于稀疏张量代数、稀疏数组运算（例如稀疏 NumPy）和关系代数的新统一编译器系统。统一编译器结合了三种不同的语言，分别描述应用程序逻辑（例如，关系查询后跟稀疏数组操作）、数据表示（例如，关系尝试和以压缩形式存储的稀疏数组）和计算组织（例如，针对配备专用张量处理硬件的 GPU）。为了实现这些目标，该项目将为稀疏数组运算和关系代数开发统一的编译器理论，开发新的关系数据表示形式，并开发将这些应用程序编译到专用加速器的技术。该项目的成功将带来新的灵活的数据分析系统，该系统可以跨数据结构和硬件移植，并且在不失通用性的情况下比当前的通用方法快几个数量级。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Indexed Streams: A Formal Intermediate Representation for Fused Contraction Programs

• DOI: 10.1145/3591268
• 发表时间: 2023-06
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: S. Kovach;Praneeth Kolichala;Tiancheng Gu;Fredrik Kjolstad

The Sparse Abstract Machine

• DOI: 10.1145/3582016.3582051
• 发表时间: 2022-08
• 期刊: Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3
• 作者: Olivia Hsu;Maxwell Strange;Jaeyeon Won;Ritvik Sharma;K. Olukotun;J. Emer;M. Horowitz;Fredrik Kjolstad

Mosaic: An Interoperable Compiler for Tensor Algebra

Mosaic：张量代数的可互操作编译器

• DOI: 10.1145/3591236
• 发表时间: 2023
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Bansal, Manya;Hsu, Olivia;Olukotun, Kunle;Kjolstad, Fredrik
• 通讯作者: Kjolstad, Fredrik