Optimal Orthogonal Tiling of 2-D Iterations

✍ Scribed by Rumen Andonov; Sanjay Rajopadhye

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 113 KB
• Volume: 45
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1371

✦ Synopsis

Iteration space tiling is a common strategy used by parallelizing compilers and in performance tuning of parallel codes. We address the problem of determining the tile size that minimizes the total execution time. We restrict our attention to uniform dependency computations with two-dimensional, parallelogramshaped iteration domain which can be tiled with lines parallel to the domain boundaries. The target architecture is a linear array (or a ring). Our model is developed in two steps. We first abstract each tile by two simple parameters, namely tile period P t and intertile latency L t . We formulate and partially resolve the corresponding optimization problem independent of the machine and program. Next, we refine the model with realistic machine and program parameters, yielding a discrete nonlinear optimization problem. We solve this analytically, yielding a closed form solution, which can be used by a compiler before code generation.