EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Finch: Sparse and Structured Tensor Programming with Control Flow

Willow Ahrens, Teodoro Fields Collin, Radha Patel, Kyle Deeds, Changwan Hong, Saman Amarasinghe

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →