Fri 22 Jun 2018 11:00 - 11:25 at Grand Ballroom AB - Optimization and Locality Chair(s): Milind Kulkarni

State-of-the-art algorithms used in automatic polyhedral transformation for parallelization and locality optimization typically rely on Integer Linear Programming (ILP). This poses a scalability issue when scaling to tens or hundreds of statements, and may be disconcerting in production compiler settings. In this work, we consider relaxing integrality in the ILP formulation of the Pluto algorithm, a popular algorithm used to find good affine transformations. We show that the rational solutions obtained from the relaxed LP formulation can easily be scaled to valid integral ones to obtain desired solutions, although with some caveats. We first present formal results connecting the solution of the relaxed LP to the original Pluto ILP. We then show that there are difficulties in realizing the above theoretical results in practice, and propose an alternate approach to overcome those while still leveraging linear programming. Our new approach obtains dramatic compile-time speedups for a range of large benchmarks. While achieving these compile-time improvements, we show that the performance of the transformed code is not sacrificed. Our approach to automatic transformation provides a mean compilation time improvement of 5.6x over state-of-the-art on relevant challenging benchmarks from the NAS PB, SPEC CPU 2006, and PolyBench suites. We also came across situations where prior frameworks failed to find a transformation in a reasonable amount of time, while our new approach did so instantaneously.

Fri 22 Jun

pldi-2018-papers
11:00 - 12:15: PLDI Research Papers - Optimization and Locality at Grand Ballroom AB
Chair(s): Milind KulkarniPurdue University
pldi-2018-papers11:00 - 11:25
Talk
Aravind AcharyaIndian Institute of Science, Bangalore, Uday BondhugulaIndian Institute of Science, Albert CohenInria, France / ENS, France
Media Attached
pldi-2018-papers11:25 - 11:50
Talk
Simon MollSaarland University, Germany, Sebastian HackSaarland University, Germany
Media Attached
pldi-2018-papers11:50 - 12:15
Talk
Dong ChenUniversity of Rochester, Fangzhou LiuUniversity of Rochester, Chen DingUniversity of Rochester, Sreepathi PaiUniversity of Rochester
Media Attached