Determining the Idle Time of a Tiling: New Results

In the framework of perfect loop nests with uniform dependences, tiling has been extensively studied as a source-to-source program transformation. We build upon recent results by Hogsted, Carter and Ferrante [10], who aim at determining the cumulated idle time spent by all processors while executing the partitioned (tiled) computation domain. We propose new (much shorter) proofs of all their results, and extend these in several important directions. More precisely, we provide an accurate solution for all values of the rise parameter that relates the shape of the iteration space to that of the tiles, and for all possible distributions of the tiles to processors, while the authors in [10] only deal with a limited number of cases, and provide upper bounds rather than exact formulas. This work was supported in part by the National Science Foundation Grant No. ASC-9005933; by the Defense Advanced Research Projects Agency under contract DAAH04-95-1-0077, administered by the Army Research O..