Home
Home
  Research
    Datatypes
    Immutator
  Old Projects
  Calendar
  CV

 Publications
Fredrik Kjolstad, Peter Ahrens, Shoaib Kamil, Saman Amarasinghe
  Sparse Tensor Algebra Optimizations with Workspaces

arXiv February 2018

Abstract

This paper shows how to optimize sparse tensor algebraic expressions by introducing temporary tensors, called workspaces, into the resulting loop nests. We develop a new intermediate language for tensor operations called concrete index notation that extends tensor index notation. Concrete index notation expresses when and where sub-computations occur and what tensor they are stored into. We then describe the workspace optimization in this language, and how to compile it to sparse code by building on prior work in the literature. We demonstrate the importance of the optimization on several important sparse tensor kernels, including sparse matrix-matrix multiplication (SpMM), sparse tensor addition (SpAdd), and the matricized tensor times Khatri-Rao product (MTTKRP) used to factorize tensors. Our results show improvements over prior work on tensor algebra compilation and brings the performance of these kernels on par with state-of-the-art hand-optimized implementations. For example, SpMM was not supported by prior tensor algebra compilers, the performance of MTTKRP on the nell-2 data set improves by 35%, and MTTKRP can for the first time have sparse results.

Documents

download article:

BibTeX

@article{kjolstad2018automatic,
  title={Automatic Generation of Sparse Tensor Kernels with Workspaces},
  author={Kjolstad, Fredrik and Kamil, Shoaib and Amarasinghe, Saman},
  journal={arXiv preprint arXiv:1802.10574},
  year={2018}
}