(PEN)-ULTIMATE TILING

In the framework of perfect loop nests with uniform dependences, tiling is a technique used to group elemental computation points so as to increase computation granularity and to reduce the overhead due to communication time. We review existing approaches from the literature, together with the optimization criteria that are used for determining a ''good'' or ''optimal'' tiling. Then we explain the need to introduce yet another criterion for defining ''optimal tiling'' in a scalable environment. Although our criterion is more complex than previously used ones, we are able to prove a theorem on optimality, and to provide a constructive method for defining the ''optimal tiling''.