EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Compiler Support for Sparse Tensor Convolutions

Peiming Liu, Alexander J Root, Anlun Xu, Yinying Li, Fredrik Kjolstad, Aart J.C. Bik

Proceedings of the ACM on Programming Languages · 08.10.2024 · 8 (OOPSLA2) · 275-303

DOI: 10.1145/3689721 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 08.10.2024. Verfasst von Peiming Liu und 5 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 59 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper extends prior work on sparse tensor algebra compilers to generate asymptotically efficient code for tensor expressions with affine subscript expressions. Our technique enables compiler support for a wide range of sparse computations, including sparse convolutions and pooling that are widely used in ML and graphics applications. We propose an approach that gradually rewrites compound subscript expressions to simple subscript expressions with loops that exploit the sparsity pattern of the input sparse tensors. As a result, the time complexity of the generated kernels is bounded by the number of stored elements and not by the shape of the tensors. Our approach seamlessly integrates into existing frameworks and is compatible with recent advances in compilers for sparse computations, including the flexibility to efficiently handle arbitrary combinations of different sparse tensor formats. The implementation of our algorithm is open source and upstreamed to the MLIR sparse compiler. Experimental results show that our method achieves 19.5x speedup when compared with the state-of-the-art compiler-based method at 99.9% sparsity. The generated sparse kernels start to outperform dense convolution implementations at about 80% sparsity

Zitieren

APA

Liu, P., Root, A. J., Xu, A., Li, Y., Kjolstad, F., & Bik, A. J. (2024). Compiler Support for Sparse Tensor Convolutions. Proceedings of the ACM on Programming Languages, 8(OOPSLA2), 275-303. https://doi.org/10.1145/3689721

Vancouver

Liu P, Root AJ, Xu A, Li Y, Kjolstad F, Bik AJ. Compiler Support for Sparse Tensor Convolutions. Proceedings of the ACM on Programming Languages. 2024;8(OOPSLA2):275-303. doi:10.1145/3689721

BibTeX
@article{Liu2024,
  author = {Liu, Peiming and Root, Alexander J and Xu, Anlun and Li, Yinying and Kjolstad, Fredrik and Bik, Aart J.C.},
  title = {Compiler Support for Sparse Tensor Convolutions},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {OOPSLA2},
  pages = {275--303},
  doi = {10.1145/3689721}
}
Kostenlos starten →