Mon 15 Jun 2015 16:50 - 17:15 at PLDI Main RED (Portland 256) - Optimization Chair(s): Michelle Strout

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 Jun

Displayed 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
16:00
25m
Talk
LaminarIR: Compile-Time Queues for Structured Streams
Research Papers
Yousun Ko Yonsei University, Bernd Burgstaller Yonsei University, Bernhard Scholz The University of Sydney
Media Attached
16:25
25m
Talk
Optimizing Off-Chip Accesses in Multicores
Research Papers
Wei Ding Pennsylvania State University, Xulong Tang Penn State, Mahmut Taylan Kandemir Pennsylvania State University, Yuanrui Zhang Intel, Emre Kultursay Pennsylvania State University
Media Attached
16:50
25m
Talk
Improving Compiler Scalability: Optimizing Large Programs at Small Price
Research Papers
Sanyam Mehta University of Minnesota, Pen-Chung Yew University of Minnesota
Media Attached