On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops

Abstract : We explore the link between dependence abstractions and maximal parallelism extraction in nested loops. Our goal is to find, for each dependence abstraction, the minimal transformations needed for maximal parallelism extraction. The result of this paper is that Allen and Kennedy's algorithm is optimal when dependences are approximated by dependence levels. This means that even the most sophisticated algorithm cannot detect more parallelism than found by Allen and Kennedy's algorithm, as long as dependence level is the only information available. In other words, loop distribution is sufficient for detecting maximal parallelism in dependence graphs with levels.
Document type :
Reports
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101988
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:11:26 AM
Last modification on : Wednesday, May 8, 2019 - 1:34:28 AM

File

RR1996-05.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101988, version 1

Collections

Citation

Alain Darte, Frédéric Vivien. On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops. [Research Report] LIP RR-1996-05, Laboratoire de l'informatique du parallélisme. 1996, 2+34p. ⟨hal-02101988⟩

Share

Metrics

Record views

10

Files downloads

44