Finch: Sparse and Structured Tensor Programming with Control Flow
Proceedings of the ACM on Programming Languages · 09.04.2025 · 9 (OOPSLA1) · 1042-1072
DOI: 10.1145/3720473 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 09.04.2025. Verfasst von Willow Ahrens und 5 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 104 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Intel and NSF PPoSS, DARPA PROWESS Award, NSF SHF.
Abstract (Originalsprache)
From FORTRAN to NumPy, tensors have revolutionized how we express computation. However, tensors in these, and almost all prominent systems, can only handle dense rectilinear integer grids. Real world tensors 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 tensor structures and program control flow they support to better simplify the problem. In this work, 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 tensors 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 tensor 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, and graph analytics.
Förderung
- Intel and NSF PPoSS
- DARPA PROWESS Award
- NSF SHF
- DoE PSAAP Center
- DARPA SBIR
Zitieren
APA
Ahrens, W., Collin, T. F., Patel, R., Deeds, K., Hong, C., & Amarasinghe, S. (2025). Finch: Sparse and Structured Tensor Programming with Control Flow. Proceedings of the ACM on Programming Languages, 9(OOPSLA1), 1042-1072. https://doi.org/10.1145/3720473
Vancouver
Ahrens W, Collin TF, Patel R, Deeds K, Hong C, Amarasinghe S. Finch: Sparse and Structured Tensor Programming with Control Flow. Proceedings of the ACM on Programming Languages. 2025;9(OOPSLA1):1042-1072. doi:10.1145/3720473
BibTeX
@article{Ahrens2025,
author = {Ahrens, Willow and Collin, Teodoro Fields and Patel, Radha and Deeds, Kyle and Hong, Changwan and Amarasinghe, Saman},
title = {Finch: Sparse and Structured Tensor Programming with Control Flow},
journal = {Proceedings of the ACM on Programming Languages},
year = {2025},
volume = {9},
number = {OOPSLA1},
pages = {1042--1072},
doi = {10.1145/3720473}
}
EUVIMED