一句话：为稀疏数组语言编译形状算子并融合计算，无需物化中间临时数组，显著加速 reshape、concat 等操作。
现有稀疏数组编程系统仅对部分稀疏数据结构实现通用形状算子，其他结构上的形状算子需归约到已有结构，且不支持融合。本文构建了一个支持形状算子（如 reshape、concat）与计算算子的稀疏数组语言编译器，将稀疏数组表达式编译为能高效迭代不规则稀疏数据结构重塑视图的代码，无需为中间结果物化临时存储，并支持形状与计算算子融合。评估表明，生成代码与 scipy.sparse 手写内核相比取得 1.66×–15.3× 的几何平均加速，与 pydata/sparse 通用实现相比取得 1.67×–651× 加速；在需要数据结构转换时，相比两者分别取得 7.29×–13.0× 与 21.3×–511× 的加速；融合形状与计算算子还能为若干表达式带来 1.22×–2.23× 的几何平均加速。
We show how to build a compiler for a sparse array language that supports shape operators such as reshaping or concatenating arrays, in addition to compute operators. Existing sparse array programming systems implement generic shape operators for only some sparse data structures, reduce shape operators on other data structures to those, and do not support fusion. Our system compiles sparse array expressions to code that efficiently iterates over reshaped views of irregular sparse data structures, without needing to materialize temporary storage for intermediates. Our evaluation shows that our approach generates sparse array code competitive with popular sparse array libraries: our generated shape operators achieve geometric mean speed-ups of 1.66×–15.3× when compared to hand-written kernels in scipy.sparse and 1.67×–651× when compared to generic implementations in pydata/sparse . For operators that require data structure conversions in these libraries, our generated code achieves geometric mean speed-ups of 7.29×–13.0× when compared to scipy.sparse and 21.3×–511× when compared to pydata/sparse . Finally, our evaluation demonstrates that fusing shape and compute operators improves the performance of several expressions by geometric mean speed-ups of 1.22×–2.23×.
@article{RootYLGBK24,
title = {Compilation of Shape Operators on Sparse Arrays},
author = {Alexander J Root and Bobby Yan and Peiming Liu and Christophe Gyurgyik and Aart J.C. Bik and Fredrik Kjolstad},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {OOPSLA2},
year = {2024},
doi = {10.1145/3689752}
}