HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 3:42:31 PM
Last modification on : Friday, February 4, 2022 - 3:17:18 AM
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