Combining Retiming and Scheduling Techniques for Loop Parallelization and Loop Tiling

Alain Darte 1 Georges-André Silber 1, 2 Frédéric Vivien 1
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : 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 paper, 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 the 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 parallelization as well.
Type de document :
Article dans une revue
Parallel Processing Letters, World Scientific Publishing, 1997, 7 (4), pp.379--392. 〈10.1142/S0129626497000383〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00856890
Contributeur : Equipe Roma <>
Soumis le : lundi 2 septembre 2013 - 16:19:10
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Identifiants

Collections

Citation

Alain Darte, Georges-André Silber, Frédéric Vivien. Combining Retiming and Scheduling Techniques for Loop Parallelization and Loop Tiling. Parallel Processing Letters, World Scientific Publishing, 1997, 7 (4), pp.379--392. 〈10.1142/S0129626497000383〉. 〈hal-00856890〉

Partager

Métriques

Consultations de la notice

153