Multi-level Tiling Interactions

Jeanne Ferrante, Nicholas Mitchell, Karin Hogstedt, Larry Carter
University of California, San Diego

Optimizations, including tiling, often target a single level of memory or parallelism, such as cache. These optimizations usually operate on a level-by-level basis, guided by a cost function parameterized by features of that single level. The benefits of optimizations guided by these one-level cost functions decreases as architectures tend towards a hierarchy of memory and of parallelism. We have identified three common architectural scenarios where a single tiling choice could be improved by using information from multiple levels in concert. For each scenario, we derive multi-level cost functions which guide the optimal choice of tile size and shape, and quantify the improvement gained. We give both analysis and simulation results to support our points.

Further info and related paper(s):

• Jeanne Ferrante's home page
• Quantifying the Multi-Level Nature of Tiling Interactions, Mitchell, N., L. Carter, J. Ferrante, and K. Hogstedt 10th International Workshop on Languages and Compilers for Parallel Computing August, 1997.