diff --git a/mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorBase.td b/mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorBase.td --- a/mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorBase.td +++ b/mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorBase.td @@ -15,14 +15,51 @@ let name = "sparse_tensor"; let cppNamespace = "::mlir::sparse_tensor"; let description = [{ - The `sparse tensor` dialect is intended to hold primitives that - form a bridge between high-level operations on sparse tensors - and lower-level operations on the actual sparse storage schemes - consisting of pointers, indices, and values. This bridge - simplifies a `sparse compiler` pass by postponing actual - code generation for the supported primitives to a later phase, - either by generating calls into a runtime support library - or by further lowering the primitives into actual code. + 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 + tensors types and lower-level operations on the actual sparse storage + schemes consisting of pointers, indices, 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 concept of **treating sparsity as a property, not a tedious + implementation detail**, by letting a **sparse compiler** generate + sparse code automatically was pioneered for dense linear algebra by + [Bik96] in MT1 (see https://www.aartbik.com/sparse.php) and formalized + to tensor algebra by [Kjolstad17,Kjolstad20] in the Sparse Tensor + Algebra Compiler (TACO) project (see http://tensor-compiler.org/). + + The MLIR implementation closely follows the "sparse iteration theory" + that forms the foundation of TACO. A rewriting rule is applied to each + tensor expression in the Linalg dialect (MLIR's tensor index notation) + where the sparsity of tensors is indicated using the per-dimension level + types dense/compressed together with a specification of the order on the + dimensions (see [Chou18] for an in-depth discussions and possible + extensions to these level types). Subsequently, a topologically sorted + iteration graph, reflecting the required order on indices with respect + to the dimensions of each tensor, is constructed to ensure that all tensors + are visited in natural index order. Next, iteration lattices are + constructed for the tensor expression for every index in topological + order. Each iteration lattice point consists of a conjunction of tensor + indices together with a tensor (sub)expression that needs to be evaluated + for that conjunction. Within the lattice, iteration points are ordered + according to the way indices are exhausted. As such these iteration + lattices drive actual sparse code generation, which consists of a + relatively straightforward one-to-one mapping from iteration lattices + to combinations of for-loops, while-loops, and if-statements. + + * [Bik96] Aart J.C. Bik. Compiler Support for Sparse Matrix Computations. + PhD thesis, Leiden University, May 1996. + * [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. + * [Kjolstad20] Fredrik Berg Kjolstad. Sparse Tensor Algebra Compilation. + PhD thesis, MIT, February, 2020. + * [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. }]; } diff --git a/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp b/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp --- a/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp +++ b/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp @@ -6,39 +6,8 @@ // //===----------------------------------------------------------------------===// // -// This file implements lowering sparse tensor types to actual sparse code. +// This file implements converting sparse tensor types to actual sparse code. // -// The concept of letting a compiler generate sparse code automatically was -// pioneered for dense linear algebra code in Fortran by [Bik96] in MT1 and -// formalized to tensor algebra by [Kjolstad17,20] for the Sparse Tensor -// Algebra Compiler (TACO). The implementation in this file closely follows -// the "sparse iteration theory" that forms the foundation of TACO. A rewriting -// rule is applied to each tensor expression in linalg (MLIR's tensor index -// notation) where the sparsity of tensors is indicated with annotation using -// a per-dimension specification of sparse/dense storage together with a -// specification of the order on the dimensions. Subsequently, a topologically -// sorted iteration graph, reflecting the required order on indices with respect -// to the dimensions of each tensor, is constructed to ensure that all tensors -// are visited in natural index order. Next, iteration lattices are constructed -// for the tensor expression for every index in topological order. Each -// iteration lattice point consists of a conjunction of tensor indices together -// with a tensor (sub)expression that needs to be evaluated for that -// conjunction. Within the lattice, iteration points are ordered according to -// the way indices are exhausted. As such these iteration lattices drive actual -// sparse code generation, which consists of a tedious but relatively -// straightforward one-to-one mapping from iteration lattices to combinations -// of for-loops, while-loops, and if-statements. -// -// [Bik96] Aart J.C. Bik. Compiler Support for Sparse Matrix Computations. -// PhD thesis, Leiden University, May 1996 (aartbik.com/sparse.php). -// [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. -// [Kjolstad20] Fredrik Berg Kjolstad. Sparse Tensor Algebra Compilation. -// PhD thesis, MIT, February, 2020 (tensor-compiler.org). -// -// Implementation detail: We use llvm::SmallVector for vectors with -// variable lengths and std::vector for vectors with fixed lengths. //===----------------------------------------------------------------------===// #include "mlir/Dialect/Linalg/IR/LinalgOps.h"