Improving Compiler Scalability: Optimizing Large Programs at Small Price
Compiler scalability is a well known problem: reasoning 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 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 to incorporate given the compile time constraints.
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 optimizer. That is, we identify representative statements (and dependences) in the program that expose 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.
Mon 15 JunDisplayed time zone: Tijuana, Baja California change
16:00 - 17:15
OptimizationResearch Papers at PLDI Main RED (Portland 256)
Chair(s): Michelle Strout Colorado State University
|LaminarIR: Compile-Time Queues for Structured Streams|
Yousun Ko Yonsei University, Bernd Burgstaller Yonsei University, Bernhard Scholz The University of SydneyMedia Attached
|Optimizing Off-Chip Accesses in Multicores|
Wei Ding Pennsylvania State University, Xulong Tang Penn State, Mahmut Taylan Kandemir Pennsylvania State University, Yuanrui Zhang Intel, Emre Kultursay Pennsylvania State UniversityMedia Attached
|Improving Compiler Scalability: Optimizing Large Programs at Small Price|
Sanyam Mehta University of Minnesota, Pen-Chung Yew University of MinnesotaMedia Attached