Automatic Collapsing of Non-Rectangular Loops

Philippe Clauss 1, 2 Ervin Altıntas 1 Matthieu Kuhn 3
2 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
3 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
Abstract : Loop collapsing is a well-known loop transformation which combines some loops that are perfectly nested into one single loop. It allows to take advantage of the whole amount of parallelism exhibited by the collapsed loops, and provides a perfect load balancing of iterations among the parallel threads. However, in the current implementations of this loop optimization , as the ones of the OpenMP language, automatic loop collapsing is limited to loops with constant loop bounds that define rectangular iteration spaces, although load imbalance is a particularly crucial issue with non-rectangular loops. The OpenMP language addresses load balance mostly through dynamic runtime scheduling of the parallel threads. Nevertheless, this runtime schedule introduces some unavoidable execution-time overhead, while preventing to exploit the entire parallelism of all the parallel loops. In this paper, we propose a technique to automatically collapse any perfectly nested loops defining non-rectangular iteration spaces, whose bounds are linear functions of the loop iterators. Such spaces may be triangular, tetrahedral, trapezoidal, rhomboidal or parallelepiped. Our solution is based on original mathematical results addressing the inversion of a multi-variate polynomial that defines a ranking of the integer points contained in a convex polyhedron. We show on a set of non-rectangular loop nests that our technique allows to generate parallel OpenMP codes that outperform the original parallel loop nests, parallelized either by using options " static " or " dynamic " of the OpenMP-schedule clause.
Type de document :
Communication dans un congrès
IEEE International. Parallel and Distributed Processing Symposium (IPDPS), 2017, May 2017, Orlando, United States. pp.778 - 787, 2017, 〈〉. 〈10.1109/IPDPS.2017.34〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
Contributeur : Philippe Clauss <>
Soumis le : lundi 4 septembre 2017 - 11:28:05
Dernière modification le : jeudi 29 mars 2018 - 09:10:05


Fichiers produits par l'(les) auteur(s)



Philippe Clauss, Ervin Altıntas, Matthieu Kuhn. Automatic Collapsing of Non-Rectangular Loops. IEEE International. Parallel and Distributed Processing Symposium (IPDPS), 2017, May 2017, Orlando, United States. pp.778 - 787, 2017, 〈〉. 〈10.1109/IPDPS.2017.34〉. 〈hal-01581081〉



Consultations de la notice


Téléchargements de fichiers