Optimal Orthogonal Tiling

Rumen Andonov (a), Sanjay Rajopadhye (b) and Nicola Yanev (c)

(a) Université de Valenciennes
(b) Irisa, Rennes
(c) Bulgarian Academy of Sciences, Sofia

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 orthogonal tiling: uniform dependency programs with (hyper) parallelepiped shaped iteration domains which can be tiled with hyperplanes parallel to the domain boundaries. Our formulation includes many machine and program models used in the literature, notably the BSP programming model. We resolve the optimization problem analytically, yielding a closed form solution.

Keywords: coarse grain pipelining, SPMD programs, loop blocking, nonlinear optimization, communication-computation overlap, supernode partitioning, automatic parallelization, macro-systolic arrays.

Further info and related paper(s):

• click here for transparencies (of Sanjay's Europar 98 presentation).
• Optimal Orthogonal Tiling, Rumen Andonov, Sanjay Rajopadhye and Nicola Yanev, in Europar 98, Springer Verlag LNCS 1470, Southampton, UK, September 1998 (pages 480-490).
• Optimal Orthogonal tiling of 2-D Iterations, Rumen Andonov and Sanjay Rajopadhye, in Journal of Parallel and Distributed Computing, Vol 45, No 2, September 1997 (pages 159-165). A more detailed but older version (which also contains some discussion of the non-orthogonal case) is available as Irisa Tech report PI-999
• Two-Dimensional Orthogonal Tiling: from Theory to Practice, Rumen Andonov, Hafid Bourzoufi and Sanjay Rajopadhye, in IEEE International Conference on High Performance Computing, Tiruvananthapuram, India, December 1996 (pages 225-231).