一句话：提出 Finch 语言，统一控制流与结构化张量表示并协同优化，自动特化控制流到数据，显著加速稀疏张量计算。
现有张量系统大多只支持稠密、规则的整数网格，对稀疏、重复值、对称、三角、填充、块等真实世界结构化数据支持碎片化且不完整，并常通过限制控制流来简化问题。本文提出编程语言 Finch，支持灵活的控制流与多样的张量数据结构。其核心思想是将控制流和数据结构统一到同一表示中，使二者能够协同优化；Finch 会自动将控制流特化到具体数据，让性能工程师可以专注于算法实验。该语言提供熟悉的循环、语句、if、break 等结构，并能可靠利用结构零、重复值和聚簇非零等结构性质。评估表明，Finch 在 SpMV、SpGEMM、图像处理和图分析等操作中带来显著加速。
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.
@article{paperbot3216,
title = {Finch: Sparse and Structured Tensor Programming with Control Flow},
author = {Willow Ahrens and Teodoro Fields Collin and Radha Patel and Kyle Deeds and Changwan Hong and Saman Amarasinghe},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {OOPSLA1},
year = {2025},
doi = {10.1145/3720473}
}