Simplifying dependent reductions in the polyhedral model
Simplifying dependent reductions in the polyhedral model
复制标题
简化多面体模型中的相关约简
DOI：
10.1145/3434301
复制
发表时间：
2021
影响因子：
--
通讯作者：
Carbin, Michael
中科院分区：
文献类型：
--
作者：
Yang, Cambridge;Atkinson, Eric;Carbin, Michael
约简-使用关联和交换运算符对一组值进行累加-是许多数值计算中的常见计算，包括科学计算，机器学习，计算机视觉和金融分析。当代基于多面体的编译技术使得优化约简（诸如前缀和）成为可能，其中约简的输出的每个分量潜在地与约简中的另一分量共享计算。因此，优化编译器可以识别多个组件之间共享的计算，并生成只计算一次共享计算的代码。然而，这些技术不支持在多面体模型的语言中表达时跨越多个依赖语句的归约。在这种情况下，现有的方法可以生成不正确的代码，违反了原始的数据依赖，未优化的program.In这项工作中，我们确定并形式化的依赖减少作为一个整数双线性规划的优化。我们提出了一个启发式优化算法，使用仿射顺序计划，以确定如何简化减少仍然保留程序的dependences.We证明，该算法提供了最佳的复杂性，从文献中的概率推理算法，其性能严重依赖于简化这些减少基准程序。11个程序中有10个程序的复杂度至少显著提高了输入数据的大小，对于典型的真实的应用程序输入，输入数据的大小在104到106之间。我们还通过显示从1.1倍到超过106倍的挂钟时间加速来确认改进的重要性。
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 104to 106for 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 106x.
登录
查看更多内容
DOI：
--
发表时间：
1995
期刊：
--
影响因子：
--
作者：
通讯作者：
--
按需参数化阵列数据流分析
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Sven Verdoolaege;Hristo Nikolov;T. Stefanov
通讯作者：
T. Stefanov
从概率程序生成高效的 MCMC 内核
DOI：
--
发表时间：
2014
期刊：
International Conference on Artificial Intelligence and Statistics
影响因子：
--
作者：
Lingfeng Yang;P. Hanrahan;Noah D. Goodman
通讯作者：
Noah D. Goodman
DOI：
10.1145/181181.181319
发表时间：
1994
期刊：
ACM Trans. Program. Lang. Syst.
影响因子：
--
作者：
Xavier Redon;P. Feautrier
通讯作者：
P. Feautrier
DOI：
10.1073/pnas.0307752101
发表时间：
2004-04-06
影响因子：
11.1
作者：
Griffiths, TL;Steyvers, M
通讯作者：
Steyvers, M