一句话：提出一个将递推方程组按数据结构与调度编译为原生代码的框架，并判定其可解性。
本文提出一个将递推方程（recurrence equations）编译为原生代码的框架。用户以规范形式给出递推方程组、存储输入输出的数据结构类型以及用于优化的调度命令，编译器据此把规范 lowering 为尊重递推依赖关系的原生代码。该编译器既能面向稀疏数据结构也能面向稠密数据结构生成代码，并能判定在给定调度原语下递推系统是否可解。作者在来自稠密与稀疏矩阵求解、动态规划、图问题以及稀疏张量代数等多个领域的递推上评估了生成代码的正确性与性能。实验表明，生成代码的性能可与库中手工优化实现相竞争；而与只针对特定递推、特定数据结构与特定优化的手写库不同，本系统能从递推、数据格式与调度自动生成实现，因而具有更强的通用性。
We present a framework for compiling recurrence equations into native code. In our framework, users specify a system of recurrences, the types of data structures that store inputs and outputs, and scheduling commands for optimization. Our compiler then lowers these specifications into native code that respects the dependencies in the recurrence equations. Our compiler can generate code over both sparse and dense data structures, and determines if the recurrence system is solvable with the provided scheduling primitives. We evaluate the performance and correctness of the generated code on several recurrences, from domains as diverse as dense and sparse matrix solvers, dynamic programming, graph problems, and sparse tensor algebra. We demonstrate that the generated code has competitive performance to hand-optimized implementations in libraries. However, these handwritten libraries target specific recurrences, specific data structures, and specific optimizations. Our system, on the other hand, automatically generates implementations from recurrences, data formats, and schedules, giving our system more generality than library approaches.
@article{paperbot2531,
title = {Compiling Recurrences over Dense and Sparse Arrays},
author = {Shiv Sundram and Muhammad Usman Tariq and Fredrik Kjolstad},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {OOPSLA1},
year = {2024},
doi = {10.1145/3649820}
}