Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Determining the Idle Time of a Tiling: New Results

Frédéric Desprez 1 Jack Dongarra 2 Fabrice Rastello 1 Yves Robert 1 
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In the framework of fully permutable loops, tiling has been studied extensively as a source-to-source program transformation. We build upon recent results by Högsted, Carter, and Ferrante~\cite{HogstedtCF97}, who aim at determining the cumulated idle time spent by all processors while executing the partitioned (tiled) computation domain. We propose new, much shorter proofs of all their results and extend these in several important directions. More precisely, we provide an accurate solution for all values of the {\em rise} parameter that relates the shape of the iteration space to that of the tiles, and for all possible distributions of the tiles to processors. In contrast, the authors in~\cite{HogstedtCF97} deal only with a limited number of cases and provide upper bounds rather than exact formulas.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:44:57 PM
Last modification on : Friday, November 18, 2022 - 9:23:11 AM


  • HAL Id : inria-00073417, version 1


Frédéric Desprez, Jack Dongarra, Fabrice Rastello, Yves Robert. Determining the Idle Time of a Tiling: New Results. [Research Report] RR-3272, LIP RR-1997-35, INRIA, LIP. 1997. ⟨inria-00073417⟩



Record views


Files downloads