Multidimensional tensor frameworks like Numpy or Tensorflow have revolutionized how we express computation. Over the last decade, compilers have expanded dense programming interfaces to capture sparse datastructures. Generating code for sparse programs is uniquely challenging, requiring flexible traversal orders, intersection and union algorithms, datastructures, and fused operations. Sparse performance depends on a complex set of factors, including the sparsity patterns of the inputs at runtime. Existing frameworks struggle to support and navigate the wide variety of possible implementations.

In this work, we present Galley, an autoscheduler for the Finch sparse tensor compiler. The user can write ordinary Numpy code over sparse arrays. Galley automatically makes high-level implementation decisions, and Finch translates them to efficient low-level code. Galley uses state-of-the-art database cardinality estimation techniques to estimate the cost of sparse tensor operations based on the observed sparsity patterns. The process starts by evaluating fusion opportunities at the “logical layer,” then moves on to more granular details like loop ordering and format selection in the “physical layer.” Together, Galley and Finch provide a declarative system for sparse tensor programming that achieves high performance on a wide variety of problems including machine learning algorithms, subgraph counting, and iterative graph algorithms.

Willow Ahrens is a Ph.D. student at MIT studying tensor compilers, advised by Saman Amarasinghe and graduating this year. She is the developer of Finch, a productive datastructure-driven array programming language. Willow received her BS in Computer Science with a minor in Mathematics from University of California, Berkeley. Willow is a Department of Energy Computational Science Graduate Fellow, and values scientific applications. Willow is also a glassblower, and teaches first-time glassblowers at the MIT Glass Lab.