Optimal tiling - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1994

Optimal tiling

Rumen Andonov

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-2135.pdf (357.57 Ko) Télécharger le fichier

Dates et versions

inria-00074537 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074537 , version 1

Citer

Rumen Andonov, Sanjay Rajopadhye. Optimal tiling. [Research Report] RR-2135, INRIA. 1994. ⟨inria-00074537⟩
172 Consultations
132 Téléchargements

Partager

Gmail Facebook X LinkedIn More