Predicting performance for tiled perfectly nested loops
Karin Högstedt, Jeanne Ferrante, Larry Carter · 1999
Many computationally-intensive programs, such as those for differential equations, spatial interpolation, and dynamic programming, spend a large portion of their execution time in multiply-nested loops that have a regular stencil of data dependences. Tiling is a well-known optimization that improves performance on such loops, particularly for computers with a multi-levelled hierarchy of parallelism and memory. Most previous work on tiling restricts the tile shape to be rectangular. Our work shows that using parallelogram-shaped tiles can improve parallel execution time by decreasing the time that a processor spends waiting for data or synchronization. This thesis presents a prediction formula for the execution time of tiled, perfectly nested loops. We also derive the tiling parameters that minimizes this formula for two dimensional iteration spaces. In K dimensions we can either minimize the formula numerically, or apply an algorithm exponential in K, which is usually very small. These formulae can be used by a compiler to automatically determine the best tiling. We introduce a model that allows us to demonstrate the equivalence in complexity of linear programming and determining the length of the longest path of dependent tiles. Assuming sufficient parallelism, this length is a measure of the execution time. We introduce the notion of rise, a measure of the relationship between the shape of the tiles and the iteration space. Using the rise, we derive a simple formula for the length of the longest path of dependent tiles in rectilinear iteration spaces, a sub-class of the convex iteration spaces. We study how the longest path of dependent tiles within a rectilinear iteration space changes with the tile shape. We run experiments and find that our formulae can accurately predict the optimal tiling parameters. The actual execution time of our application changes as predicted with the shape and size of the tiles. We notice a speedup from 1.12 to 1.55 depending on the problem size when using parallelogram-shaped tiles as opposed to rectangular tiles.