将稀疏性视为一种属性，而不是（繁琐的）实现细节，可让编译器的稀疏化器1 自动生成稀疏代码。[Bik96] 在 MT1 中率先将这一概念应用于线性代数，[Kjolstad17,Kjolstad20] 在稀疏张量代数编译器 (TACO) 项目中将其正式应用于张量代数。
SparseTensor 方言支持所有必需的属性、类型、操作和传递，以使稀疏张量类型在 MLIR 编译器基础架构中成为一等公民。该方言在稀疏张量类型的高级运算与由位置、坐标和值组成的实际稀疏存储方案的低级运算之间架起了一座桥梁。较低级别的支持可能包含完全生成的代码，也可能通过小型稀疏运行时支持库提供。
MLIR 实现 [Biketal22] 紧密遵循构成 TACO 基础的“稀疏迭代理论”。编译器针对 Linalg 方言（MLIR 的张量索引表示法）中的每个张量表达式都有一条重写规则：张量的每个级别的稀疏度由级别类型（例如，密集、压缩、单例）和级别顺序规范来指示（有关这些级别类型的深入讨论和可能的扩展，请参阅 [Chou18]）。对于输入中的每个张量表达式，编译器首先构建一个拓扑排序的迭代图，该图反映了坐标相对于每个张量级别的顺序；这可确保以自然级别-坐标顺序访问所有张量。接下来，按拓扑顺序为每个索引构建迭代网格。每个迭代网格点都包含张量坐标的合取和需要针对该合取求值的张量（子）表达式。在网格内，迭代点会根据坐标的穷尽方式进行排序。因此，这些迭代网格会驱动实际的稀疏代码生成，即从迭代网格到 for 循环、while 循环和 if 语句组合的相对简单的一对一映射。如果所有并行循环都是最外层循环，则通过直接插入来处理具体化未初始化的稀疏张量输出；否则，通过间接插入来处理，即通过一维访问模式扩展（也称为工作区）来处理 [Gustavson72,Bik96,Kjolstad19]。
[Bik96] Aart J.C. Bik. 针对稀疏矩阵计算的编译器支持。博士论文，莱顿大学，1996 年 5 月。
[Biketal22] Aart J.C. Bik、Penporn Koanantakool、Tatiana Shpeisman、Nicolas Vasilache、Bixia Zheng 和 Fredrik Kjolstad。 MLIR 中稀疏张量计算的编译器支持。 ACM Transactions on Architecture and Code Optimization，2022 年 6 月。 请参阅：https://dl.acm.org/doi/10.1145/3544559
[Chou18] Stephen Chou、Fredrik Berg Kjolstad 和 Saman Amarasinghe。 稀疏张量代数编译器的格式抽象。Proceedings of the ACM on Programming Languages，2018 年 10 月。
[Chou20] Stephen Chou、Fredrik Berg Kjolstad 和 Saman Amarasinghe。 自动生成高效的稀疏张量格式转换例程。第 41 届 ACM SIGPLAN 编程语言设计与实现会议论文集，2020 年 6 月。
[Gustavson72] Fred G. Gustavson. 用于求解稀疏线性方程组的一些基本技巧。在《稀疏矩阵及其应用》一书中，第 41-52 页。Plenum Press，纽约，1972 年。
[Kjolstad17] Fredrik Berg Kjolstad、Shoaib Ashraf Kamil、Stephen Chou、David Lugato 和 Saman Amarasinghe。Tensor Algebra Compiler。Proceedings of the ACM on Programming Languages，2017 年 10 月。
[Kjolstad19] Fredrik Berg Kjolstad、Peter Ahrens、Shoaib Ashraf Kamil 和 Saman Amarasinghe。Tensor Algebra Compilation with Workspaces，IEEE/ACM 代码生成和优化国际研讨会论文集，2019 年。
[Kjolstad20] Fredrik Berg Kjolstad. 稀疏张量代数编译。博士论文，麻省理工学院，2020 年 2 月。
您想贡献自己的力量吗？以下是一些适合新手的问题。
-
请注意，我们现在更倾向于使用“稀疏化器”一词，而不是同样常用的“稀疏编译器”一词来指代此类传递，以明确表明稀疏化器传递不是单独的编译器，而应是使用 MLIR 编译器基础架构构建的任何编译器流水线的组成部分。 ↩