Improving locality and parallelism in nested loops

Abstract

Researchers have identified a core set of program transformations that are effective in array-based loop nest optimization: these loop transformations include interchange, skewing, reversal and tiling. Researchers have studied these transformations individually for their legality and effect on parallelism and memory hierarchy performance; but they have not discussed in any detail how to choose the combination of transformations that best optimizes a loop nest. Other researchers have taken another approach: they consider each loop nest as a whole, applying an elegant matrix theory of loop nest transformation, but one that is only applicable to a limited class of loop nests, those whose dependences can be expressed as distance vectors. In this limited context, the problems of memory hierarchy improvement and parallelization are simplified, but their approach has not been extended to apply to general loop nests. We have combined the elegance of the matrix theory with the generality of general dependence vectors into a new theory of loop transformation. This theory has enabled us to apply an algorithmic approach to solving optimization goals. Using this theory, we have developed efficient algorithms for the compiler to use to improve memory hierarchy utilization and parallelism of general loop nests. The parallelization improving algorithm maximizes the degree of parallelism within a loop nest, at either a coarse or fine granularity. The locality improving algorithm uses the same theory, and also reuse information about array accesses within loop nests, to guide the transformation process. The parallelization and locality improvement algorithms are unified so that locality and parallelism can be improved simultaneously without significantly reducing either. We have implemented versions of these algorithms in Stanford's SUIF compiler and performed experimentation on the Perfect Club and the NASA kernels. We have found compiler locality improvement to significantly improve performance when applicable. We have also demonstrated a tremendous sensitivity of performance on tile size for tiled codes on machines with direct-mapped or low set associativity caches.