Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Scanning polyhedra with DO loops

Abstract : Supercompilers perform complex program transformations which often result in new loop bounds. This paper shows that, under the usual assumptions in automatic parallelization, most transformations on loop nests can be expressed as affine transformations on integer sets defined by polyhedra and that the new loop bounds can be computed with algorithms using Fourier's pairwise elimination method although it is not exact for integer sets. Sufficient conditions to use pairwise elimination on integer sets and to extend it to pseudo-linear constraints are also given. A tradeoff has to be made between dynamic overhead due to some bound slackness and compilation complexity but the resulting code is always correct. Thse algorithms can be used to onterchange or block loops regardless of the loop bounds or the blocking strategy and to safety exchange array parts between two levels of a memory hierarchy or between neighboring processors in a distributed memory machine.
Type de document :
Communication dans un congrès
Liste complète des métadonnées
Contributeur : Claire Medrala <>
Soumis le : vendredi 16 novembre 2012 - 14:35:30
Dernière modification le : mercredi 14 octobre 2020 - 03:52:18
Archivage à long terme le : : samedi 17 décembre 2016 - 10:45:42


Fichiers produits par l'(les) auteur(s)



Corinne Ancourt, François Irigoin. Scanning polyhedra with DO loops. Principles and Pratice of Parallel Programming, PPoPP'91, Apr 1991, Williamsburg, Virginia,, United States. pp.Pages 39 - 50, ⟨10.1145/109626.109631⟩. ⟨hal-00752774⟩



Consultations de la notice


Téléchargements de fichiers