Name
Abstract | ||
|---|---|---|
Loop nest optimization is a combinatorial problem. Due to the growing complexity of modern architectures, it involves two increasingly difficult tasks: (1) analyzing the profitability of sequences of transformations to enhance parallelism, locality, and resource usage, which amounts to a hard problem on a non-linear objective function; (2) the construction and exploration of search space of legal transformation sequences. Practical optimizing and parallelizing compilers decouple these tasks, resorting to a predefined set of enabling transformations to eliminate all sorts of optimization-limiting semantical constraints. State-of-the-art optimization heuristics face a hard decision problem on the selection of enabling transformations only remotely related to performance. We propose a new design where optimization heuristics first address the main performance anomalies, then correct potentially illegal loop transformations a posteriori, attempting to minimize the performance impact of the necessary adjustments. We propose a general method to correct any sequence of loop transformations through a combination of loop shifting, code motion and index-set splitting. Sequences of transformations are modeled by compositions of geometric transformations on multidimensional affine schedules. We provide experimental evidence of the scalability of the algorithms on real loop optimizations. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/PACT.2007.17 | PACT |
Keywords | Field | DocType |
hard decision problem,real loop optimizations,hard problem,illegal loop,automatic correction,state-of-the-art optimization heuristics,loop nest optimization,enabling transformation,loop transformations,combinatorial problem,loop transformation,main performance anomaly,profitability,decision theory,objective function,indexation,sequences,intermediate representation,geometry,geometric transformations,polyhedral model,search space,loop optimization,decision problem,scheduling,boundary condition | Affine transformation,Loop nest optimization,Decision problem,Computer science,Transformation geometry,Parallel computing,Loop fission,Theoretical computer science,Schedule,Heuristics,Scalability | Conference |
ISSN | ISBN | Citations |
1089-795X | 0-7695-2944-5 | 7 |
PageRank | References | Authors |
0.58 | 19 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Vasilache | 1 | 354 | 19.45 |
| Albert Cohen | 2 | 1002 | 72.30 |
| Louis-noël Pouchet | 3 | 880 | 47.61 |