SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Thu 21 Oct 2021 14:35 - 14:50 at Zurich C - Implementation of special Paradigms Chair(s): Frank Tip
Thu 21 Oct 2021 22:35 - 22:50 at Zurich C - Implementation of special Paradigms - mirror Chair(s): Steve Blackburn

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$\times$ to 53.7$\times$ when measured against PyData/Sparse for user-defined functions and between 0.98$\times$ and 5.53$\times$ when measured against SciPy/Sparse for sparse array slicing. Our technique outperforms PyData/Sparse by 6.58$\times$ to 70.3$\times$, and (where applicable) performs between 0.96$\times$ and 28.9$\times$ 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$\times$ and 3.50$\times$ compared to that of the hand-optimized SuiteSparse:GraphBLAS library.

Thu 21 Oct

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

13:50 - 15:10
Implementation of special ParadigmsOOPSLA at Zurich C +8h
Chair(s): Frank Tip Northeastern University
13:50
15m
Talk
Coarsening Optimization for Differentiable ProgrammingVirtual
OOPSLA
Xipeng Shen North Carolina State University; Facebook, Guoqiang Zhang North Carolina State University; Facebook, Irene Dea Facebook, Samantha Andow Facebook, Emilio Arroyo-Fang Facebook, Neal Gafter Facebook, Johann George Facebook, Melissa Grueter Facebook, Erik Meijer Facebook, Olin Grigsby Shivers Facebook, Steffi Stumpos Facebook, Alanna Tempest Facebook, Christy Warden Facebook, Shannon Yang Facebook
DOI
14:05
15m
Talk
Efficient Automatic Scheduling of Imaging and Vision Pipelines for the GPUVirtual
OOPSLA
Luke Anderson Massachusetts Institute of Technology, Andrew Adams Adobe, Karima Ma Massachusetts Institute of Technology, Tzu-Mao Li Massachusetts Institute of Technology; University of California at San Diego, Tian Jin Massachusetts Institute of Technology, Jonathan Ragan-Kelley Massachusetts Institute of Technology
DOI
14:20
15m
Talk
Statically Bounded-Memory Delayed Sampling for Probabilistic StreamsIn-Person
OOPSLA
Eric Atkinson Massachusetts Institute of Technology, Guillaume Baudart Inria; ENS; PSL University, Louis Mandel IBM Research, Charles Yuan Massachusetts Institute of Technology, Michael Carbin Massachusetts Institute of Technology
DOI
14:35
15m
Talk
Compilation of Sparse Array Programming ModelsIn-Person
OOPSLA
Rawn Henry Massachusetts Institute of Technology, Olivia Hsu Stanford University, Rohan Yadav Stanford University, Stephen Chou Massachusetts Institute of Technology, Kunle Olukotun Stanford University, Saman Amarasinghe Massachusetts Institute of Technology, Fredrik Kjolstad Stanford University
DOI
14:50
20m
Live Q&A
Discussion, Questions and Answers
OOPSLA

21:50 - 23:10
Implementation of special Paradigms - mirrorOOPSLA at Zurich C
Chair(s): Steve Blackburn Australian National University
21:50
15m
Talk
Coarsening Optimization for Differentiable ProgrammingVirtual
OOPSLA
Xipeng Shen North Carolina State University; Facebook, Guoqiang Zhang North Carolina State University; Facebook, Irene Dea Facebook, Samantha Andow Facebook, Emilio Arroyo-Fang Facebook, Neal Gafter Facebook, Johann George Facebook, Melissa Grueter Facebook, Erik Meijer Facebook, Olin Grigsby Shivers Facebook, Steffi Stumpos Facebook, Alanna Tempest Facebook, Christy Warden Facebook, Shannon Yang Facebook
DOI
22:05
15m
Talk
Efficient Automatic Scheduling of Imaging and Vision Pipelines for the GPUVirtual
OOPSLA
Luke Anderson Massachusetts Institute of Technology, Andrew Adams Adobe, Karima Ma Massachusetts Institute of Technology, Tzu-Mao Li Massachusetts Institute of Technology; University of California at San Diego, Tian Jin Massachusetts Institute of Technology, Jonathan Ragan-Kelley Massachusetts Institute of Technology
DOI
22:20
15m
Talk
Statically Bounded-Memory Delayed Sampling for Probabilistic StreamsIn-Person
OOPSLA
Eric Atkinson Massachusetts Institute of Technology, Guillaume Baudart Inria; ENS; PSL University, Louis Mandel IBM Research, Charles Yuan Massachusetts Institute of Technology, Michael Carbin Massachusetts Institute of Technology
DOI
22:35
15m
Talk
Compilation of Sparse Array Programming ModelsIn-Person
OOPSLA
Rawn Henry Massachusetts Institute of Technology, Olivia Hsu Stanford University, Rohan Yadav Stanford University, Stephen Chou Massachusetts Institute of Technology, Kunle Olukotun Stanford University, Saman Amarasinghe Massachusetts Institute of Technology, Fredrik Kjolstad Stanford University
DOI
22:50
20m
Live Q&A
Discussion, Questions and Answers
OOPSLA