Loop Shifting for Loop Parallelization - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2000

Loop Shifting for Loop Parallelization


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.
Fichier principal
Vignette du fichier
RR2000-22.pdf (568.78 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101749 , version 1 (17-04-2019)


  • HAL Id : hal-02101749 , version 1


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


Gmail Mastodon Facebook X LinkedIn More