Thu 24 Oct 2024 10:40 - 11:00 at San Gabriel - Compilers and Optimisation 1 Chair(s): Emery D. Berger

We show how to build a compiler for a sparse array language that supports shape operators (e.g. 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 ranging from $1.66\times$ to $15.3\times$ when compared to hand-written kernels in scipy.sparse and $1.67\times$ to $651\times$ 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 ranging from $7.29\times$ to $13.0\times$ when compared to scipy.sparse and $21.3\times$ to $511\times$ when compared to pydata/sparse. Finally, our evaluation also shows that fusing shape and compute operators improves the performance of several expressions (geometric means $1.22\times$-$2.23\times$).

Thu 24 Oct

Displayed time zone: Pacific Time (US & Canada) change

10:40 - 12:20
Compilers and Optimisation 1OOPSLA 2024 at San Gabriel
Chair(s): Emery D. Berger University of Massachusetts Amherst
10:40
20m
Talk
Compilation of Shape Operators on Sparse Arrays
OOPSLA 2024
Alexander J Root Stanford University, Bobby Yan Stanford University, Peiming Liu Google Inc, Christophe Gyurgyik Stanford University, Aart Bik Google, Inc., Fredrik Kjolstad Stanford University
DOI Pre-print
11:00
20m
Talk
Compiler Support for Sparse Tensor Convolutions
OOPSLA 2024
Peiming Liu Google Inc, Alexander J Root Stanford University, Anlun Xu Google, Yinying Li Google, Fredrik Kjolstad Stanford University, Aart Bik Google, Inc.
DOI
11:20
20m
Talk
Compiling Recurrences over Dense and Sparse Arrays
OOPSLA 2024
Shiv Sundram Stanford University, Muhammad Usman Tariq Stanford University, Fredrik Kjolstad Stanford University
DOI
11:40
20m
Talk
Fully Verified Instruction Scheduling
OOPSLA 2024
Ziteng Yang Georgia Institute of Technology, Jun Shirako Georgia Institute of Technology, Vivek Sarkar Georgia Institute of Technology
DOI Pre-print
12:00
20m
Talk
Homeostasis: Design and Implementation of a Self-Stabilizing Compiler (TOPLAS)
OOPSLA 2024
Aman Nougrahiya IIT Madras, V Krishna Nandivada IIT Madras
Link to publication