Loop Shifting for Loop Parallelization
Résumé
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.
Domaines
Informatique [cs]| Origine | Fichiers produits par l'(les) auteur(s) |
|---|