Determining the Idle Time of a Tiling: New Results.

(eng) 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\"ogsted, 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.(fre) Dans le cadre des boucle complètement permutables, le pavage a été beaucoup étudié comme une transformation source-à-source. Nous nous basons sur des travaux récents de H\"ogsted, Carter, et Ferrante~\cite{HogstedtCF97}, dont le but est de déterminer le temps d'attente cumulé passé par tous les processeurs pendant l'exécution le domaine de calcul partionné (pavé). Nous proposons des nouvelles preuves, plus courtes, de tous leurs résultats et nous les étendons dans plusieurs directions importantes. Nous donnons une solution plus précise pour toutes les valeurs du paramètre {\em rise} qui relie la forme de l'espace d'itération à celle des tuiles, et pour toutes les distributions possibles des tuiles sur les processeurs. Les auteurs dans~\cite{HogstedtCF97} ne traitent qu'un nombre limité de cas et fournissent des bornes supérieures plutôt que des formules exactes