Loop Shifting for Loop Parallelization

Abstract : The automatic detection of parallel loops is a well-known problem. Sophisticated polynomial algorithms have been proposed to produce code transformations that reveal parallel loops, in an optimal way as long as the only objective is to reveal as much parallelism as possible. However, a weakness of these techniques is that there is very few control on the solutions they built. For example, it may happen that the produced solution needs a very complex unimodular transformation plus a shift of the different statements even though a much simpler solution exists. It would be more useful to first select its own unimodular transformation and to be able to check that it can be completed by a shift while revealing the same parallelism. Unfortunately, the main result of this paper is that this is a hard problem: finding a (multi-dimensional) shift that makes an innermost loop parallel is strongly NP-complete. Nevertheless, we show that several subcases of this problem are easily solvable and that the general problem can be solved thanks to integer linear programming.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101749
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 8:58:29 AM
Last modification on : Friday, April 19, 2019 - 1:38:13 AM

File

RR2000-22.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101749, version 1

Collections

Citation

Alain Darte, Guillaume Huard. Loop Shifting for Loop Parallelization. [Research Report] Laboratoire de l'informatique du parallélisme. 2000, 2+40p. ⟨hal-02101749⟩

Share

Metrics

Record views

22

Files downloads

55