Skip to Main content Skip to Navigation

Optimal tiling

Rumen Andonov 1 Sanjay Rajopadhye 1
1 API - Parallel VLSI Architectures
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : Iteration space tiling is a common strategy used by parallelizing compilers to reduce communication overhead. We address the problem of determining the optimal tile size (which minimizes the total execution time of the program), for a particular program schema. We use a realistic model of the architecture which accounts for coprocessors that permit overlapping of communication and computation, context switching times, etc. Determining the optimal tile size is shown to reduce to a non-linear optimization problem. We solve this analytically, yielding a closed form solution that involves only parameters of the architecture and program that are easily determined at compile time. It can thus be used by a compiler before code generation. Although we solve the problem for a particular schema of programs, our results can be generalized to uniform dependence loops and also to certain classes of lopp programs with dynamic dependence vectors.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 3:42:31 PM
Last modification on : Thursday, February 11, 2021 - 2:48:03 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:32:05 PM


  • HAL Id : inria-00074537, version 1


Rumen Andonov, Sanjay Rajopadhye. Optimal tiling. [Research Report] RR-2135, INRIA. 1994. ⟨inria-00074537⟩



Record views


Files downloads