Polyhedral-based Loop Optimizations and Dependence Analysis Part 1
SalemDerisavi 270000QDYS Visits (9336)
Polyhedral model is a linear algebraic model to represent, reason about, and transform loop nests that perform a significant amount of computation on large arrays. These types of loop nests are typically found in High-Performance Computing applications. The model can make it possible for the XLC compiler to generate more efficient code for parts of programs that contain "affine" (or linear) accesses such as a[i][j][k] or a[i+j][i-j][2*k], where a is an array and i, j, and k are loop induction variables.
Using the option -qhot=level=1 (which is implied by using -qhot) the polyhedral-based dependence analyzer is enabled, which can provide more accurate dependence information than the traditional analysis. This makes it possible to exploit more transformation opportunities, such as loop interchange for perfectly-nested loops, loop fusion and loop distribution. When used with the -qsmp option, -qhot=level=1 also enables the parallelization of loops.
Using the options -qhot=level=2 -qsmp the polyhedral-based loop transformation framework is enabled. This enables more aggressive loop transformation than -qhot=level=1, for both perfectly nested and imperfectly nested loops. These transformations include loop tiling, loop interchange, loop fusion, loop distribution, and loop parallelization.
In Part 2, I will present source code examples in which the use of the polyhedral-based dependence analysis (that is, using -qhot=level=1) will enable the compiler to prove the legality of and apply certain loop transformations for loop nests with complex iteration spaces and/or complex index expressions.