Arrays often contain underlying structure, such as sparsity, runs of repeated values, or symmetry. Support for structured data is fragmented and incomplete. Existing frameworks limit the array structures and program control flow they support to better simplify the problem.

We propose a new programming language, Finch, which supports both flexible control flow and diverse data structures. Finch facilitates a programming model which resolves the challenges of computing over structured arrays by combining control flow and data structures into a common representation where they can be co-optimized. Finch automatically specializes control flow to data so that performance engineers can focus on experimenting with many algorithms. Finch supports a familiar programming language of loops, statements, ifs, breaks, etc., over a wide variety of array structures, such as sparsity, run-length-encoding, symmetry, triangles, padding, or blocks. Finch reliably utilizes the key properties of structure, such as structural zeros, repeated values, or clustered non-zeros. We show that this leads to dramatic speedups in operations such as SpMV and SpGEMM, image processing, graph analytics, and a high-level tensor operator fusion interface.

https://github.com/willow-ahrens/Finch.jl

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.