Iterative Optimization in the Polyhedral Model: Part I, One-Dimensional Time Export

@proceedings{noel07iterative, abstract = {Emerging microprocessors offer unprecedented parallel computing capabilities and deeper memory hierarchies, increasing the importance of loop transformations in optimizing compilers. Because compiler heuristics rely on simplistic performance models, and because they are bound to a limited set of transformations sequences, they only uncover a fraction of the peak performance on typical benchmarks. Iterative optimization is a maturing framework to address these limitations, but so far, it was not successfully applied complex loop transformation sequences because of the combinatorics of the optimization search space. We focus on the class of loop transformation which can be expressed as one-dimensional affine schedules. We define a systematic exploration method to enumerate the space of all legal, distinct transformations in this class. This method is based on an upstream characterization, as opposed to state-of-the-art downstream filtering approaches. Our results demonstrate orders of magnitude improvements in the size of the search space and in the convergence speed of a dedicated iterative optimization heuristic}, author = {Pouchet, Louis-Noel and Bastoul, Cedric and Cohen, Albert and Vasilache, Nicolas}, booktitle = {Code Generation and Optimization, 2007. CGO '07. International Symposium on}, citeulike-article-id = {3438471}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/CGO.2007.21}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4145111}, doi = {10.1109/CGO.2007.21}, journal = {Code Generation and Optimization, 2007. CGO '07. International Symposium on}, pages = {144--156}, posted-at = {2008-10-22 04:01:53}, priority = {3}, title = {Iterative Optimization in the Polyhedral Model: Part I, One-Dimensional Time}, url = {http://dx.doi.org/10.1109/CGO.2007.21}, year = {2007} }

TY - CONF ID - noel07iterative L3 - citeulike-article-id:3438471 N2 - Emerging microprocessors offer unprecedented parallel computing capabilities and deeper memory hierarchies, increasing the importance of loop transformations in optimizing compilers. Because compiler heuristics rely on simplistic performance models, and because they are bound to a limited set of transformations sequences, they only uncover a fraction of the peak performance on typical benchmarks. Iterative optimization is a maturing framework to address these limitations, but so far, it was not successfully applied complex loop transformation sequences because of the combinatorics of the optimization search space. We focus on the class of loop transformation which can be expressed as one-dimensional affine schedules. We define a systematic exploration method to enumerate the space of all legal, distinct transformations in this class. This method is based on an upstream characterization, as opposed to state-of-the-art downstream filtering approaches. Our results demonstrate orders of magnitude improvements in the size of the search space and in the convergence speed of a dedicated iterative optimization heuristic JF - Code Generation and Optimization, 2007. CGO '07. International Symposium on EP - 156 TI - Iterative Optimization in the Polyhedral Model: Part I, One-Dimensional Time T2 - Code Generation and Optimization, 2007. CGO '07. International Symposium on SP - 144 AU - Pouchet, Louis-Noel AU - Bastoul, Cedric AU - Cohen, Albert AU - Vasilache, Nicolas PY - 2007/// UR - http://dx.doi.org/10.1109/CGO.2007.21 ER -