Loop-Synthesizing using a Unimodular Transformation

S. Lee and H. Aso (Japan)


Enhancing locality, Loop-synthesizing, Tiling


On modern computers, performance of a program is often limited by memory latency rather than by processor speed. To reduce the impact of memory latency, restructuring compiler researchers have developed locality enhancing program transformations. It is known that enhancing local ity with parallelization of loop nests can be performed by loop transformations, but some of them have restrictions. Tiling is the most well-known locality enhancing program transformation, and is restricted to apply to perfectly nested loops. We present a simple loop-synthesizing method to transform a sequence of loop nests into a perfectly nested loop. New loop-synthesizing transformation is represented by a unimodular matrix. The result of our algorithm is a fully permutable loop nest which can directly be tiled.

Important Links:

Go Back