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 metadatas

https://hal-mines-paristech.archives-ouvertes.fr/hal-00752774
Contributor : Claire Medrala <>
Submitted on : Friday, November 16, 2012 - 2:35:30 PM
Last modification on : Wednesday, October 14, 2020 - 3:52:18 AM
Long-term archiving on: : Saturday, December 17, 2016 - 10:45:42 AM

File

A-195.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

379

Files downloads

821