Author retrospective for synthesizing transformations for locality enhancement of imperfectly-nested loop nests
Keshav K. Pingali · 2014
This paper describes a technique for transforming imperfectly-nested loops to enhance locality of reference. The key idea is to embed the iteration space of every statement in the loop nest into a special iteration space called the product space. The product space is interpreted as a perfectly-nested loop that is transformed to enhance locality and enable tiling; after that, fully permutable loops are tiled, and a new imperfectly-nested loop with better locality than the original one is generated. Experimental results show that this approach is effective in locality enhancement for dense matrix factorization codes and relaxation codes, among others.