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.
Type de document :
[Research Report] RR-2135, INRIA. 1994
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:42:31
Dernière modification le : vendredi 16 novembre 2018 - 01:30:36
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:32:05



  • HAL Id : inria-00074537, version 1


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



Consultations de la notice


Téléchargements de fichiers