Improving compiler scalability: optimizing large programs at small price
Improving compiler scalability: optimizing large programs at small price
复制标题
提高编译器可扩展性：以较小的代价优化大型程序
DOI：
10.1145/2737924.2737954
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
P. Yew
中科院分区：
文献类型：
--
作者：
Sanyam Mehta;P. Yew
编译器可扩展性是一个众所周知的问题：在编译过程中，推理在大型程序范围上应用有用的优化会消耗太多的时间和内存。在使用功能强大但成本高昂的整数编程算法来组成循环优化的多面体编译器中，这个问题更加严重。因此，多面体编译器必须为包含循环嵌套序列的真实科学应用程序等程序提供的好处对于普通用户来说仍然不切实际。在这项工作中，我们解决了多面体编译器中的可扩展性问题。我们确定了不可扩展性的三个原因，每个原因都源于程序范围内的大量语句和依赖性。我们提出了一种通过减少编译器所看到的有效语句和依赖项数量来解决该问题的一次性解决方案。我们通过用单个超级语句表示程序中的一系列语句来实现这一点。这组超级语句向整数线性规划 (ILP) 求解器公开了最小的充分约束，以找到正确的优化。我们在 PLuTo 多面体编译器中实现我们的方法，发现它将程序语句和程序依赖性分别压缩了 4.7 倍和 6.4 倍，平均超过 5 个实际应用程序中的 9 个热点区域（范围从 48 到 121 条语句）。因此，与最新版本的 PLuTo 编译器相比，编译时间和内存要求分别提高了 268 倍和 20 倍。最终编译时间与 Intel 编译器相当，而由于后者采用保守的循环优化方法，性能平均提高 1.92 倍。
Compiler scalability is a well known problem: reasoning about the application of useful optimizations over large program scopes consumes too much time and memory during compilation. This problem is exacerbated in polyhedral compilers that use powerful yet costly integer programming algorithms to compose loop optimizations. As a result, the benefits that a polyhedral compiler has to offer to programs such as real scientific applications that contain sequences of loop nests, remain impractical for the common users. In this work, we address this scalability problem in polyhedral compilers. We identify three causes of unscalability, each of which stems from large number of statements and dependences in the program scope. We propose a one-shot solution to the problem by reducing the effective number of statements and dependences as seen by the compiler. We achieve this by representing a sequence of statements in a program by a single super-statement. This set of super-statements exposes the minimum sufficient constraints to the Integer Linear Programming (ILP) solver for finding correct optimizations. We implement our approach in the PLuTo polyhedral compiler and find that it condenses the program statements and program dependences by factors of 4.7x and 6.4x, respectively, averaged over 9 hot regions (ranging from 48 to 121 statements) in 5 real applications. As a result, the improvements in time and memory requirement for compilation are 268x and 20x, respectively, over the latest version of the PLuTo compiler. The final compile times are comparable to the Intel compiler while the performance is 1.92x better on average due to the latter’s conservative approach to loop optimization.