Compilation of sparse array programming models
Abstract
This paper shows how to compile sparse array programming languages. A sparse array programming language is an array programming language that supports element-wise application, reduction, and broadcasting of arbitrary functions over dense and sparse arrays with any fill value. Such a language has great expressive power and can express sparse and dense linear and tensor algebra, functions over images, exclusion and inclusion filters, and even graph algorithms. Our compiler strategy generalizes prior work in the literature on sparse tensor algebra compilation to support any function applied to sparse arrays, instead of only addition and multiplication. To achieve this, we generalize the notion of sparse iteration spaces beyond intersections and unions. These iteration spaces are automatically derived by considering how algebraic properties annotated onto functions interact with the fill values of the arrays. We then show how to compile these iteration spaces to efficient code. When compared with two widely-used Python sparse array packages, our evaluation shows that we generate built-in sparse array library features with a performance of 1.4× to 53.7× when measured against PyData/Sparse for user-defined functions and between 0.98× and 5.53× when measured against SciPy/Sparse for sparse array slicing. Our technique outperforms PyData/Sparse by 6.58× to 70.3×, and (where applicable) performs between 0.96× and 28.9× that of a dense NumPy implementation, on end-to-end sparse array applications. We also implement graph linear algebra kernels in our system with a performance of between 0.56× and 3.50× compared to that of the hand-optimized SuiteSparse:GraphBLAS library.
Article
Article
Appendix
Movie
BibTeX
@article{henry2021oopsla,
author = {Henry, Rawn and Hsu, Olivia and Yadav, Rohan and Chou, Stephen and Olukotun, Kunle and Amarasinghe, Saman and Kjolstad, Fredrik},
title = {Compilation of Sparse Array Programming Models},
year = {2021},
issue_date = {October 2021},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {5},
number = {OOPSLA},
url = {https://doi-org.stanford.idm.oclc.org/10.1145/3485505},
doi = {10.1145/3485505},
abstract = {This paper shows how to compile sparse array programming languages.
A sparse array programming language is an array programming language that
supports element-wise application, reduction, and broadcasting of arbitrary
functions over dense and sparse arrays with any fill value. Such a language has
great expressive power and can express sparse and dense linear and tensor
algebra, functions over images, exclusion and inclusion filters, and even graph
algorithms. Our compiler strategy generalizes prior work in the literature on
sparse tensor algebra compilation to support any function applied to sparse
arrays, instead of only addition and multiplication. To achieve this, we
generalize the notion of sparse iteration spaces beyond intersections and
unions. These iteration spaces are automatically derived by considering how
algebraic properties annotated onto functions interact with the fill values of
the arrays. We then show how to compile these iteration spaces to efficient
code. When compared with two widely-used Python sparse array packages, our
evaluation shows that we generate built-in sparse array library features with a
performance of 1.4x to 53.7x when measured against
PyData/Sparse for user-defined functions and between 0.98x and
5.53x when measured against SciPy/Sparse for sparse array slicing.
Our technique outperforms PyData/Sparse by 6.58x to
70.3x, and (where applicable) performs between 0.96x and
28.9x that of a dense NumPy implementation, on end-to-end sparse
array applications. We also implement graph linear algebra kernels in our
system with a performance of between 0.56x and 3.50x
compared to that of the hand-optimized SuiteSparse:GraphBLAS library.},
journal = {Proc. ACM Program. Lang.},
month = {oct},
articleno = {128},
numpages = {29},
keywords = {Sparse Arrays, Sparse Array Programming, Compilation} }