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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01581081
Contributor : Philippe Clauss <>
Submitted on : Monday, September 4, 2017 - 11:28:05 AM
Last modification on : Tuesday, February 12, 2019 - 9:12:31 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

266

Files downloads

443