A Unified Transformation Technique for Multilevel Blocking

Abstract. This paper presents a new unified method for simultaneously tiling the register and cache levels of the memory hierarchy. We will only focus on the code transformation phase of tiling. Our algorithm uses strip-mining and loop interchange on all memory hierarchy levels to determine the tiles as usual, and, afterwards, and due to the special characteristics of the register level, we apply index set splitting, unrolling and scalar replacement to this level. After applying strip-mining, the iteration space is non-convex. To perform in a single step the loop interchange in non-convex iteration spaces, we use non-unimodular matrices. The order proposed to perform index set splitting to the loops guarantees that each loop in the nest has to be processed only once and also avoids code explosion.