Introduction
Stay organized with collections
Save and categorize content based on your preferences.
Treating sparsity as a property instead of a (tedious) implementation
detail lets the compiler's sparsifier1 generate sparse
code automatically. The concept was pioneered for linear
algebra by [Bik96] in MT1
and formalized to tensor algebra by [Kjolstad17,Kjolstad20]
in the Sparse Tensor Algebra Compiler
(TACO) project.
The SparseTensor dialect supports all the attributes,
types, operations, and passes that are required to make sparse-tensor types
first-class citizens within the MLIR compiler infrastructure. The dialect
forms a bridge between high-level operations on sparse-tensor types and
lower-level operations on the actual sparse-storage schemes
consisting of positions, coordinates, and values. Lower-level
support may consist of fully generated code or may be provided
by means of a small sparse runtime support library.
The MLIR implementation [Biketal22] closely follows
the 'sparse iteration theory' that forms the foundation of TACO.
The compiler has a rewriting rule for each tensor expression in the Linalg
dialect (MLIR's tensor index notation): the sparsity of each level of a
tensor is indicated by the level-types
(e.g., dense, compressed, singleton) and a specification of the order
on the levels (see [Chou18]
for an in-depth discussions and possible extensions to these level-types).
For each tensor expression in the input, the compiler first constructs a
topologically sorted iteration graph that reflects the ordering of
coordinates with respect to the levels of each tensor; this ensures that
all tensors are visited in the natural level-coordinate order. Next,
iteration lattices are constructed for every index in topological order.
Each iteration-lattice
point consists of a conjunction of tensor coordinates and
a tensor (sub)expression that needs to be evaluated for that conjunction.
Within the lattice, iteration points are ordered according to the way
coordinates are exhausted. As such, these iteration lattices drive actual
sparse-code generation, a relatively straightforward
one-to-one mapping from iteration lattices to combinations of for-loops,
while-loops, and if-statements. Sparse-tensor outputs that materialize
uninitialized are handled with either direct insertions, if all parallel loops
are outermost, or insertions that indirectly
go through a 1-dimensional
access pattern expansion (a.k.a. workspace),
where feasible [Gustavson72,Bik96,Kjolstad19].
[Bik96] Aart J.C. Bik. Compiler Support for Sparse Matrix Computations. PhD thesis, Leiden University, May 1996.
[Biketal22] Aart J.C. Bik, Penporn Koanantakool, Tatiana Shpeisman,
Nicolas Vasilache, Bixia Zheng, and Fredrik Kjolstad.
Compiler Support for Sparse Tensor Computations in MLIR.
ACM Transactions on Architecture and Code Optimization, June, 2022.
See: https://dl.acm.org/doi/10.1145/3544559
[Chou18] Stephen Chou, Fredrik Berg Kjolstad, and Saman Amarasinghe.
Format Abstraction for Sparse Tensor Algebra Compilers. Proceedings of the
ACM on Programming Languages, October 2018.
[Chou20] Stephen Chou, Fredrik Berg Kjolstad, and Saman Amarasinghe.
Automatic Generation of Efficient Sparse
Tensor Format Conversion Routines. Proceedings of the 41st
ACM SIGPLAN Conference on Programming Language
Design and Implementation, June, 2020.
[Gustavson72] Fred G. Gustavson. Some basic techniques for solving sparse
systems of linear equations. 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, and Saman Amarasinghe. The Tensor Algebra Compiler. Proceedings
of the ACM on Programming Languages, October 2017.
[Kjolstad19] Fredrik Berg Kjolstad, Peter Ahrens, Shoaib Ashraf Kamil, and
Saman Amarasinghe. Tensor Algebra Compilation with Workspaces, Proceedings of
the IEEE/ACM International Symposium on Code Generation and Optimization, 2019.
[Kjolstad20] Fredrik Berg Kjolstad. Sparse Tensor Algebra Compilation. PhD
thesis, MIT, February, 2020.
Would you like to contribute? Here are some
good first issues.
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-09-03 UTC.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-09-03 UTC."],[[["\u003cp\u003eThe SparseTensor dialect in MLIR enables treating sparsity as a property, allowing automatic generation of sparse code by the compiler's sparsifier.\u003c/p\u003e\n"],["\u003cp\u003eThis dialect bridges high-level sparse tensor operations with lower-level sparse storage schemes, enhancing efficiency.\u003c/p\u003e\n"],["\u003cp\u003eMLIR's implementation leverages sparse iteration theory, utilizing iteration graphs and lattices for code generation.\u003c/p\u003e\n"],["\u003cp\u003eSparse code generation involves a direct mapping from iteration lattices to loops and conditional statements for optimized execution.\u003c/p\u003e\n"],["\u003cp\u003eThe approach handles uninitialized sparse tensor outputs through direct or indirect insertions via a workspace when necessary.\u003c/p\u003e\n"]]],[],null,["# Introduction\n\nTreating sparsity as a property instead of a (tedious) implementation\ndetail lets the compiler's sparsifier^[1](#fn1)^ generate sparse\ncode automatically. The concept was pioneered for linear\nalgebra by \\[Bik96\\] in [MT1](https://www.aartbik.com/sparse.php)\nand formalized to tensor algebra by \\[Kjolstad17,Kjolstad20\\]\nin the Sparse Tensor Algebra Compiler\n[(TACO) project](http://tensor-compiler.org).\n\nThe SparseTensor dialect supports all the attributes,\ntypes, operations, and passes that are required to make sparse-tensor types\nfirst-class citizens within the MLIR compiler infrastructure. The dialect\nforms a bridge between high-level operations on sparse-tensor types and\nlower-level operations on the actual sparse-storage schemes\nconsisting of positions, coordinates, and values. Lower-level\nsupport may consist of fully generated code or may be provided\nby means of a small sparse runtime support library.\n\nThe MLIR implementation \\[Biketal22\\] closely follows\nthe 'sparse iteration theory' that forms the foundation of TACO.\nThe compiler has a rewriting rule for each tensor expression in the Linalg\ndialect (MLIR's tensor index notation): the sparsity of each level of a\ntensor is indicated by the level-types\n(e.g., dense, compressed, singleton) and a specification of the order\non the levels (see \\[Chou18\\]\nfor an in-depth discussions and possible extensions to these level-types).\nFor each tensor expression in the input, the compiler first constructs a\ntopologically sorted iteration graph that reflects the ordering of\ncoordinates with respect to the levels of each tensor; this ensures that\nall tensors are visited in the natural level-coordinate order. Next,\niteration lattices are constructed for every index in topological order.\nEach iteration-lattice\npoint consists of a conjunction of tensor coordinates and\na tensor (sub)expression that needs to be evaluated for that conjunction.\nWithin the lattice, iteration points are ordered according to the way\ncoordinates are exhausted. As such, these iteration lattices drive actual\nsparse-code generation, a relatively straightforward\none-to-one mapping from iteration lattices to combinations of for-loops,\nwhile-loops, and if-statements. Sparse-tensor outputs that materialize\nuninitialized are handled with either direct insertions, if all parallel loops\nare outermost, or insertions that indirectly\ngo through a 1-dimensional\naccess pattern expansion (a.k.a. workspace),\nwhere feasible \\[Gustavson72,Bik96,Kjolstad19\\].\n\n- \\[Bik96\\] Aart J.C. Bik. Compiler Support for Sparse Matrix Computations. PhD thesis, Leiden University, May 1996.\n\n- \\[Biketal22\\] Aart J.C. Bik, Penporn Koanantakool, Tatiana Shpeisman,\n Nicolas Vasilache, Bixia Zheng, and Fredrik Kjolstad.\n Compiler Support for Sparse Tensor Computations in MLIR.\n ACM Transactions on Architecture and Code Optimization, June, 2022.\n See: https://dl.acm.org/doi/10.1145/3544559\n\n- \\[Chou18\\] Stephen Chou, Fredrik Berg Kjolstad, and Saman Amarasinghe.\n Format Abstraction for Sparse Tensor Algebra Compilers. Proceedings of the\n ACM on Programming Languages, October 2018.\n\n- \\[Chou20\\] Stephen Chou, Fredrik Berg Kjolstad, and Saman Amarasinghe.\n Automatic Generation of Efficient Sparse\n Tensor Format Conversion Routines. Proceedings of the 41st\n ACM SIGPLAN Conference on Programming Language\n Design and Implementation, June, 2020.\n\n- \\[Gustavson72\\] Fred G. Gustavson. Some basic techniques for solving sparse\n systems of linear equations. In Sparse Matrices and Their Applications,\n pages 41--52. Plenum Press, New York, 1972.\n\n- \\[Kjolstad17\\] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou,\n David Lugato, and Saman Amarasinghe. The Tensor Algebra Compiler. Proceedings\n of the ACM on Programming Languages, October 2017.\n\n- \\[Kjolstad19\\] Fredrik Berg Kjolstad, Peter Ahrens, Shoaib Ashraf Kamil, and\n Saman Amarasinghe. Tensor Algebra Compilation with Workspaces, Proceedings of\n the IEEE/ACM International Symposium on Code Generation and Optimization, 2019.\n\n- \\[Kjolstad20\\] Fredrik Berg Kjolstad. Sparse Tensor Algebra Compilation. PhD\n thesis, MIT, February, 2020.\n\nWould you like to contribute? Here are some\n[good first issues](https://github.com/llvm/llvm-project/issues?q=is%3Aopen+is%3Aissue+assignee%3Aaartbik+label%3A%22good+first+issue%22). \n\n*** ** * ** ***\n\n1. Please note that we now prefer the term 'sparsifier' over the also commonly used 'sparse compiler' terminology to refer to such a pass to make it clear that the sparsifier pass is not a separate compiler, but should be an integral part of any compiler pipeline that is built with the MLIR compiler infrastructure. [↩](#fnref1)"]]