Scanning polyhedra with DO loops - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès acm Année : 1991

Scanning polyhedra with DO loops

(1) , (1)
1
Corinne Ancourt
François Irigoin

Résumé

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

Dates et versions

hal-00752774 , version 1 (16-11-2012)

Identifiants

Citer

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⟩
206 Consultations
825 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More