SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Thu 21 Oct 2021 11:35 - 11:50 at Zurich G - PLDI 2021, PLDI 2020, and OOPSLA 2020 Papers 1 Chair(s): James Koppel

We address the problem of optimizing sparse tensor algebra in a compiler and show how to define standard loop transformations (such as splitting, collapsing, and reordering) for sparse iteration spaces. The key idea is that these transformations map sparse iteration spaces into \textit{derived} iteration spaces. This results in a new iteration order that respects the constraints inherent in sparse data structures. We further demonstrate that derived iteration spaces can be used to tile over both the indexes (coordinates) and the nonzeros; the former is equivalent to tiling dense iteration spaces, while the latter tiles sparse iteration spaces into statically load-balanced blocks of nonzeros. Tiling the space of nonzeros lets the compiler efficiently exploit heterogeneous compute resources such as threads, vector units, and GPUs.

We implemented these concepts and an associated scheduling API on top of the open-source TACO system. The scheduling API can be used manually by performance engineers or be the target of an automatic scheduling system. We outline a heuristics-based autoscheduling system in this paper, but many other systems are possible and enabled by our API. Using the scheduling API, we show how to optimize sparse and mixed sparse-dense tensor algebra expressions on both CPUs and GPUs. Our results show that the sparse transformations are sufficient to generate code with competitive performance to hand-optimized implementations from the literature, while generalizing to all of the tensor algebra.

Thu 21 Oct

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

10:50 - 12:10
PLDI 2021, PLDI 2020, and OOPSLA 2020 Papers 1SIGPLAN Papers at Zurich G
Chair(s): James Koppel Massachusetts Institute of Technology, USA
10:50
15m
Talk
Example-Guided Synthesis of Relational Queries
SIGPLAN Papers
Aalok Thakkar University of Pennsylvania, Aaditya Naik University of Pennsylvania, Nathaniel Sands University of Southern California, Mukund Raghothaman University of Southern California, Mayur Naik University of Pennsylvania, Rajeev Alur University of Pennsylvania
11:05
15m
Talk
Web Question Answering with Neurosymbolic Program Synthesis
SIGPLAN Papers
Jocelyn (Qiaochu) Chen University of Texas at Austin, USA, Aaron Lamoreaux University of Texas at Austin, Xinyu Wang University of Michigan, Greg Durrett University of Texas at Austin, USA, Osbert Bastani University of Pennsylvania, Işıl Dillig University of Texas at Austin
11:20
15m
Talk
Reactive Probabilistic Programming
SIGPLAN Papers
Guillaume Baudart IBM Research, USA, Louis Mandel IBM Research, Eric Atkinson Massachusetts Institute of Technology, Benjamin Sherman Massachusetts Institute of Technology, USA, Marc Pouzet École normale supérieure, Michael Carbin Massachusetts Institute of Technology
DOI Pre-print
11:35
15m
Talk
A Sparse Iteration Space Transformation Framework for Sparse Tensor Algebra
SIGPLAN Papers
Ryan Senanayake Reservoir Labs, Changwan Hong Massachusetts Institute of Technology, Ziheng Wang Massachusetts Institute of Technology, Amalee Wilson Stanford University, Stephen Chou Massachusetts Institute of Technology, Shoaib Kamil Adobe Research, Saman Amarasinghe Massachusetts Institute of Technology, Fredrik Kjolstad Stanford University
11:50
20m
Live Q&A
Discussion, Questions and Answers
SIGPLAN Papers