Compilation of Shape Operators on Sparse Arrays
Proceedings of the ACM on Programming Languages · 08.10.2024 · 8 (OOPSLA2) · 1162-1188
DOI: 10.1145/3689752 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 08.10.2024. Verfasst von Alexander J Root und 5 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 40 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF.
Abstract (Originalsprache)
We show how to build a compiler for a sparse array language that supports shape operators such as reshaping or concatenating arrays, in addition to compute operators. Existing sparse array programming systems implement generic shape operators for only some sparse data structures, reduce shape operators on other data structures to those, and do not support fusion. Our system compiles sparse array expressions to code that efficiently iterates over reshaped views of irregular sparse data structures, without needing to materialize temporary storage for intermediates. Our evaluation shows that our approach generates sparse array code competitive with popular sparse array libraries: our generated shape operators achieve geometric mean speed-ups of 1.66×–15.3× when compared to hand-written kernels in scipy.sparse and 1.67×–651× when compared to generic implementations in pydata/sparse . For operators that require data structure conversions in these libraries, our generated code achieves geometric mean speed-ups of 7.29×–13.0× when compared to scipy.sparse and 21.3×–511× when compared to pydata/sparse . Finally, our evaluation demonstrates that fusing shape and compute operators improves the performance of several expressions by geometric mean speed-ups of 1.22×–2.23×.
Förderung
- NSF
Zitieren
APA
Root, A. J., Yan, B., Liu, P., Gyurgyik, C., Bik, A. J., & Kjolstad, F. (2024). Compilation of Shape Operators on Sparse Arrays. Proceedings of the ACM on Programming Languages, 8(OOPSLA2), 1162-1188. https://doi.org/10.1145/3689752
Vancouver
Root AJ, Yan B, Liu P, Gyurgyik C, Bik AJ, Kjolstad F. Compilation of Shape Operators on Sparse Arrays. Proceedings of the ACM on Programming Languages. 2024;8(OOPSLA2):1162-1188. doi:10.1145/3689752
BibTeX
@article{Root2024,
author = {Root, Alexander J and Yan, Bobby and Liu, Peiming and Gyurgyik, Christophe and Bik, Aart J.C. and Kjolstad, Fredrik},
title = {Compilation of Shape Operators on Sparse Arrays},
journal = {Proceedings of the ACM on Programming Languages},
year = {2024},
volume = {8},
number = {OOPSLA2},
pages = {1162--1188},
doi = {10.1145/3689752}
}
EUVIMED