EUVIMEDOdkrijte EUVIMED
Open access · CC BY 4.0

Compiling Recurrences over Dense and Sparse Arrays

Shiv Sundram, Muhammad Usman Tariq, Fredrik Kjolstad

Proceedings of the ACM on Programming Languages · 2024-04-29 · 8 (OOPSLA1) · 250-275

DOI: 10.1145/3649820 ↗

At a glance

Journal article in Proceedings of the ACM on Programming Languages, published online on 2024-04-29. Written by Shiv Sundram and 2 co-authors. Cited 6 times so far (Crossref); 41 references. The full text is freely available (open access, CC BY 4.0). Funded by: SRC, NSF.

PovzetekBibliografski podatkiCiteRelated studies

Abstract (original language)

We present a framework for compiling recurrence equations into native code. In our framework, users specify a system of recurrences, the types of data structures that store inputs and outputs, and scheduling commands for optimization. Our compiler then lowers these specifications into native code that respects the dependencies in the recurrence equations. Our compiler can generate code over both sparse and dense data structures, and determines if the recurrence system is solvable with the provided scheduling primitives. We evaluate the performance and correctness of the generated code on several recurrences, from domains as diverse as dense and sparse matrix solvers, dynamic programming, graph problems, and sparse tensor algebra. We demonstrate that the generated code has competitive performance to hand-optimized implementations in libraries. However, these handwritten libraries target specific recurrences, specific data structures, and specific optimizations. Our system, on the other hand, automatically generates implementations from recurrences, data formats, and schedules, giving our system more generality than library approaches.

Funding

  • SRC
  • NSF

Cite

APA

Sundram, S., Tariq, M. U., & Kjolstad, F. (2024). Compiling Recurrences over Dense and Sparse Arrays. Proceedings of the ACM on Programming Languages, 8(OOPSLA1), 250-275. https://doi.org/10.1145/3649820

Vancouver

Sundram S, Tariq MU, Kjolstad F. Compiling Recurrences over Dense and Sparse Arrays. Proceedings of the ACM on Programming Languages. 2024;8(OOPSLA1):250-275. doi:10.1145/3649820

BibTeX
@article{Sundram2024,
  author = {Sundram, Shiv and Tariq, Muhammad Usman and Kjolstad, Fredrik},
  title = {Compiling Recurrences over Dense and Sparse Arrays},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {OOPSLA1},
  pages = {250--275},
  doi = {10.1145/3649820}
}
Start for free →