Determining the Idle Time of a Tiling: New Results

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.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ögsted, Carter et Ferrante [12] 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 rise qui relie la forme de l'espace d'itérationa celle des tuiles et pour toutes les distributions possibles des tuiles sur les processeurs. Les auteurs dans [12] ne traitent qu'un nombre limité de cas et fournissent des bornes supérieures plutôt que des formules exacte