(PEN)-ULTIMATE TILING

In the framework of perfect loop nests with uniform dependences, tilin g is a technique used to group elemental computation points so as to i ncrease computation granularity and to reduce the overhead due to comm unication time. We review existing approaches from the literature, tog ether with the optimization criteria that are used for determining a ' 'good'' or ''optimal'' tiling. Then we explain the need to introduce y et another criterion for defining ''optimal tiling'' in a scalable env ironment. Although our criterion is more complex than previously used ones, we are able to prove a theorem on optimality, and to provide a c onstructive method for defining the ''optimal tiling''.