EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Compilation of Shape Operators on Sparse Arrays

Alexander J Root, Bobby Yan, Peiming Liu, Christophe Gyurgyik, Aart J.C. Bik, Fredrik Kjolstad

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →