一句话：将多面体模型中的依赖归约优化形式化为整数双线性规划，并提出保持依赖的启发式算法。
归约是数值计算与机器学习中的常见计算。现有多面体编译可优化前缀和等归约，复用多个输出分量间的共享计算，但无法处理跨多个依赖语句的归约，可能生成违反原程序数据依赖的错误代码。本文将该依赖归约优化问题形式化为整数双线性规划，并给出启发式算法：利用程序的仿射顺序调度决定如何简化归约且保持依赖。作者在概率推断算法基准上评估，11 个程序中有 10 个达到最优复杂度，复杂度显著降低；对 10^4 至 10^6 规模的真实输入，墙钟加速 1.1x 到超过 10^6x。
A Reduction – an accumulation over a set of values, using an associative and commutative operator – is a common computation in many numerical computations, including scientific computations, machine learning, computer vision, and financial analytics. Contemporary polyhedral-based compilation techniques make it possible to optimize reductions, such as prefix sums, in which each component of the reduction’s output potentially shares computation with another component in the reduction. Therefore an optimizing compiler can identify the computation shared between multiple components and generate code that computes the shared computation only once. These techniques, however, do not support reductions that – when phrased in the language of the polyhedral model – span multiple dependent statements. In such cases, existing approaches can generate incorrect code that violates the data dependences of the original, unoptimized program. In this work, we identify and formalize the optimization of dependent reductions as an integer bilinear program. We present a heuristic optimization algorithm that uses an affine sequential schedule of the program to determine how to simplfy reductions yet still preserve the program’s dependences. We demonstrate that the algorithm provides optimal complexity for a set of benchmark programs from the literature on probabilistic inference algorithms, whose performance critically relies on simplifying these reductions. The complexities for 10 of the 11 programs improve siginifcantly by factors at least of the sizes of the input data, which are in the range of 10 4 to 10 6 for typical real application inputs. We also confirm the significance of the improvement by showing speedups in wall-clock time that range from 1.1x to over 10 6 x.
@article{paperbot1170,
title = {Simplifying dependent reductions in the polyhedral model},
author = {Cambridge Yang and Eric Atkinson and Michael Carbin},
journal = {Proceedings of the ACM on Programming Languages},
volume = {5},
number = {POPL},
year = {2021},
doi = {10.1145/3434301}
}