一句话：提出 REPTILE 编译器，将递推方程递归分解为唯一分块并生成与手写库性能相当的 C 代码。
针对以数学递推方程表达的程序，现有编译器难以自动进行高性能分块优化，往往需要依赖手写库。REPTILE 将递推程序递归分解为一组唯一分块，再把每个分块化简为不同的递推方程；用户可声明递推方程、优化策略，并可选择把递推子表达式映射到外部库调用。由此生成的 C 代码将编译器生成的循环与手写优化库调用组合起来。评估覆盖可表达为递推方程的线性求解器以及 Needleman-Wunsch、Smith-Waterman。当分块规约给当时，REPTILE 在 LU、Cholesky、三角矩阵求逆、多右端三角求解上相对 Intel MKL 达到 0.79–2.72 倍性能，对生物信息学递推较手写实现获得 1.14–1.73 倍加速。
We introduce REPTILE, a compiler that performs tiling optimizations for programs expressed as mathematical recurrence equations. REPTILE recursively decomposes a recurrence program into a set of unique tiles and then simplifies each into a different set of recurrences. Given declarative user specifications of recurrence equations, optimizations, and optional mappings of recurrence subexpressions to external libraries calls, REPTILE generates C code that composes compiler-generated loops with calls to external hand-optimized libraries. We show that for direct linear solvers expressible as recurrence equations, the generated C code matches and often exceeds the performance of standard hand-optimized libraries. We evaluate REPTILE’s generated C code against hand-optimized implementations of linear solvers in Intel MKL, as well as two nonsolver recurrences from bioinformatics: Needleman-Wunsch and Smith-Waterman. When the user provides good tiling specifications, REPTILE achieves parity with MKL, achieving between 0.79−1.27x speedup for the LU decomposition, 0.97−1.21x speedup for the Cholesky decomposition, 1.61x−2.72x for lower triangular matrix inversion, 1.01−1.14x speedup for triangular solve with multiple right-hand sides, and 1.14−1.73x speedup over handwritten implementations of the bioinformatics recurrences.
@article{paperbot2953,
title = {REPTILE: Performant Tiling of Recurrences},
author = {Muhammad Usman Tariq and Shiv Sundram and Fredrik Kjolstad},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {OOPSLA2},
year = {2025},
doi = {10.1145/3763074}
}