簡介

將稀疏性視為屬性，而非 (繁瑣的) 實作細節，可讓編譯器的稀疏化器 1 自動產生稀疏程式碼。[Bik96] 在 MT1 中率先提出線性代數的概念，[Kjolstad17,Kjolstad20] 則在稀疏張量代數編譯器 (TACO) 專案中，將此概念正式化為張量代數。

SparseTensor 方言支援所有屬性、型別、作業和傳遞，可讓稀疏張量型別成為 MLIR 編譯器基礎架構中的一流公民。方言會在稀疏張量類型的高階作業，以及由位置、座標和值組成的實際稀疏儲存空間配置的低階作業之間，形成橋樑。低階支援可能包含完整產生的程式碼，或透過小型稀疏的執行階段支援程式庫提供。

MLIR 實作 [Biketal22] 緊密遵循「稀疏疊代理論」，這是 TACO 的基礎。編譯器會為 Linalg 方言 (MLIR 的張量索引標記) 中的每個張量運算式提供重寫規則：張量每個層級的稀疏性會以層級類型 (例如密集、壓縮、單例) 和層級順序規格表示 (如需深入討論及這些層級類型的可能擴充功能，請參閱 [Chou18])。對於輸入中的每個張量運算式，編譯器會先建構拓撲排序的疊代圖，反映相對於每個張量層級的座標順序；這可確保所有張量都以自然層級座標順序存取。接著，系統會以拓撲順序，為每個索引建構疊代格。每個疊代格點都包含張量座標的連詞，以及需要針對該連詞評估的張量 (子) 運算式。在格架中，疊代點會根據座標耗盡的方式排序。因此，這些疊代格架構會驅動實際的稀疏程式碼生成，從疊代格架構到 for 迴圈、while 迴圈和 if 陳述式的組合，相對來說是直接的一對一對應。如果所有平行迴圈都是最外層，則會直接插入未初始化的稀疏張量輸出內容；否則，會間接透過 1 維存取模式擴展 (又稱工作區) 插入內容 (如可行) [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。 Format Abstraction for Sparse Tensor Algebra Compilers. Proceedings of the ACM on Programming Languages, October 2018.

  • [Chou20] Stephen Chou、Fredrik Berg Kjolstad 和 Saman Amarasinghe。 自動產生有效率的稀疏張量格式轉換常式。第 41 屆 ACM SIGPLAN 程式設計語言設計與實作會議論文集，2020 年 6 月。

  • [Gustavson72] Fred G. Gustavson。解決稀疏線性方程式系統的一些基本技巧。In Sparse Matrices and Their Applications, pages 41–52. Plenum Press, New York, 1972.

  • [Kjolstad17] Fredrik Berg Kjolstad、Shoaib Ashraf Kamil、Stephen Chou、 David Lugato 和 Saman Amarasinghe。Tensor 代數編譯器。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 International Symposium on Code Generation and Optimization 論文集，2019 年。

  • [Kjolstad20] Fredrik Berg Kjolstad. 稀疏張量代數編譯。博士論文，麻省理工學院，2020 年 2 月。

你願意貢獻心力嗎？以下列出一些適合新手解決的問題。

  1. 請注意，我們現在偏好使用「稀疏化器」一詞，而非也常見的「稀疏編譯器」術語，來指稱這類傳遞，以明確指出稀疏化器傳遞並非獨立的編譯器，而是應成為使用 MLIR 編譯器基礎架構建構的任何編譯器管道不可或缺的一部分。 ↩