Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Claire Medrala Connect in order to contact the contributor
Submitted on : Friday, November 16, 2012 - 2:35:30 PM
Last modification on : Wednesday, November 17, 2021 - 12:31:44 PM
Long-term archiving on: : Saturday, December 17, 2016 - 10:45:42 AM


Files produced by the author(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⟩



Record views


Files downloads