Tiling Imperfectly-nested Loops
Ahmed, Nawaaz; Mateev, Nikolay; Pingali, Keshav
Tiling is one of the more important transformations for enhancing locality of reference in programs. Intuitively, tiling a set of loops achieves the effect of interleaving iterations of these loops. Tiling has been applied only to perfectly-nested loop nests which are loop nests in which all assignment statements are contained in the innermost loop. In practice, most loop nests are imperfectly-nested, so existing techniques have limited utility. In this paper, we propose an approach to tiling imperfectly-nested loop nests. The key idea is to embed the iteration space of every statement in the imperfectly-nested loop nest into a special space called the product space which is tiled to produce the final code. We evaluate the effectiveness of this approach for dense numerical linear algebra benchmarks, relaxation codes, and the tomcatv code from the SPEC benchmarks. No other approach in the literature can tile all these codes automatically.
computer science; technical report
Previously Published As