Iterative Optimization in the Polyhedral Model: Part II, Multidimensional Time

International audienceHigh-level loop optimizations are necessary to achieve good performanceover a wide variety of processors. Their performance impactcan be significant because they involve in-depth program transformationsthat aim to sustain a balanced workload over the computational,storage, and communication resources of the target architecture.Therefore, it is mandatory that the compiler accurately modelsthe target architecture as well as the effects of complex coderestructuring.However, because optimizing compilers (1) use simplistic performancemodels that abstract away many of the complexities ofmodern architectures, (2) rely on inaccurate dependence analysis,and (3) lack frameworks to express complex interactions of transformationsequences, they typically uncover only a fraction of thepeak performance available on many applications. We propose acomplete iterative framework to address these issues. We rely onthe polyhedral model to construct and traverse a large and expressivesearch space. This space encompasses only legal, distinct versionsresulting from the restructuring of any static control loop nest.We first propose a feedback-driven iterative heuristic tailoredto the search space properties of the polyhedral model. Though, itquickly converges to good solutions for small kernels, larger benchmarkscontaining higher dimensional spaces are more challengingand our heuristic misses opportunities for significant performanceimprovement. Thus, we introduce the use of a genetic algorithmwith specialized operators that leverage the polyhedral representationof program dependences. We provide experimental evidencethat the genetic algorithm effectively traverses huge optimizationspaces, achieving good performance improvements on large loopnests with complex memory accesses