Combining retiming and scheduling techniques for loop parallelization and loop tiling.

Alain Darte (1) , Georges-Andre Silber (1) , Frédéric Vivien (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

Tiling is a technique used for exploiting medium-grain parallelism in nested loops. It relies on a first step that detects sets of permutable nested loops. All algorithms developed so far consider the statements of the loop body as a single block, in other words, they are not able to take advantage of the structure of dependences between different statements. In this report, we overcome this limitation by showing how the structure of the reduced dependence graph can be taken into account for detecting more permutable loops. Our method combines graph retiming techniques and graph scheduling techniques. It can be viewed as an extension of Wolf and Lam's algorithm to the case of loops with multiple statements. Loop independent dependences play a particular role in our study, and we show how the way we handle them can be useful for fine-grain loop parallelization as well.

``Loop tiling'' est une technique utilisée pour exploiter du parallélisme à grain moyen dans les boucles imbriquées. Elle repose sur une première étape de détection de boucles permutables. Tous les algorithmes développés jusqu'à maintenant considéraient les instructions du corps du nid de boucles comme un bloc indissociable. En d'autres termes, ils ne pouvaient pas tirer profit de la structure des dépendances entre différentes instructions. Dans ce rapport, nous surmontons cette limitation en montrant comment la structure du graphe de dépendance réduit peut être prise en compte pour détecter plus de boucles permutables. Notre méthode combine des techniques de synchronisation et d'ordonnancement de graphes. Elle peut être vue comme une extension de l'algorithme de Wolf et Lam au cas de boucles comportant plusieurs instructions. Les dépendances qui ne sont pas portées par une boucle (loop independent dependences) jouent un rôle particulier dans notre étude et nous montrons comment la façon particulière dont nous les traitons peut être utile également pour la parallélisation à grain fin.

Mots clés: Automatic parallelization; Medium grain; Nested loops; Permutable loops

Mots clés: Boucles permutables; Grain moyen; Nids de boucles; Parallélisation automatique; Tiling

Domaines: Informatique [cs]

Alain Darte, Georges-Andre Silber, Frédéric Vivien. Combining retiming and scheduling techniques for loop parallelization and loop tiling.. [Research Report] LIP RR-1996-34, Laboratoire de l'informatique du parallélisme. 1996, 2+11p. ⟨hal-02102115⟩