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
Times are displayed in time zone: (GMT-07:00) Tijuana, Baja California change

16:00 - 17:15: Research Papers - Optimization at PLDI Main RED (Portland 256)
Chair(s): Michelle StroutColorado State University
pldi2015-papers16:00 - 16:25
Yousun KoYonsei University, Bernd BurgstallerYonsei University, Bernhard ScholzThe University of Sydney
Media Attached
pldi2015-papers16:25 - 16:50
Wei DingPennsylvania State University, Xulong TangPenn State, Mahmut Taylan KandemirPennsylvania State University, Yuanrui ZhangIntel, Emre KultursayPennsylvania State University
Media Attached
pldi2015-papers16:50 - 17:15
Sanyam MehtaUniversity of Minnesota, Pen-Chung YewUniversity of Minnesota
Media Attached