A general compilation algorithm to parallelize and optimize counted loops with dynamic data-dependent bounds

Jie Zhao 1 Albert Cohen 2
1 Parkas - Parallélisme de Kahn Synchrone
Inria de Paris, DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique
Abstract : We study the parallelizing compilation and loop nest optimization of an important class of programs where counted loops have a dynamically computed, data-dependent upper bound. Such loops are amenable to a wider set of transformations than general while loops with inductively defined termination conditions: for example, the substitution of closed forms for induction variables remains applicable, removing the data dependences induced by termination conditions. We propose an automatic compilation approach to parallelize and optimize dynamic counted loops. Our approach relies on affine relations only, as implemented in state-of-the-art polyhedral libraries. Revisiting a state-of- the-art framework to parallelize arbitrary while loops, we introduce additional control dependences on data-dependent predicates. Our method goes beyond the state of the art in fully automating the process, specializing the code generation algorithm to the case of dynamic counted loops and avoiding the introduction of spurious loop-carried dependences. We conduct experiments on representative irregular computations, from computer vision and finite element methods to sparse matrix linear algebra. We validate that the method is applicable to general affine transformations for locality optimization, vectorization and parallelization.
Type de document :
Communication dans un congrès
IMPACT 2017 - 7th International Workshop on Polyhedral Compilation Techniques, Jan 2017, Stockholm, Sweden. pp.1-10, 2017, 〈http://impact.gforge.inria.fr/impact2017/〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01657608
Contributeur : Jie Zhao <>
Soumis le : jeudi 7 décembre 2017 - 11:21:27
Dernière modification le : vendredi 23 novembre 2018 - 09:50:42

Fichier

impact-17-a-general-compilatio...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01657608, version 1

Citation

Jie Zhao, Albert Cohen. A general compilation algorithm to parallelize and optimize counted loops with dynamic data-dependent bounds. IMPACT 2017 - 7th International Workshop on Polyhedral Compilation Techniques, Jan 2017, Stockholm, Sweden. pp.1-10, 2017, 〈http://impact.gforge.inria.fr/impact2017/〉. 〈hal-01657608〉

Partager

Métriques

Consultations de la notice

188

Téléchargements de fichiers

47