other · LARA - Libre Acces aux Rapports scientifiques et techniques · 2006

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

Laboratoire de l'informatique du parallélisme, Darte, Alain, Vivien, Frédéric

Cited by 0Abstract and details only

Abstract

(eng) 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.

Cite this paper

APA 7

du parallélisme, L. D. L., Darte, A., & Vivien, F. (2006). On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops. LARA - Libre Acces aux Rapports scientifiques et techniques.

MLA 9

du parallélisme, Laboratoire de l'informatique, et al. “On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops.” LARA - Libre Acces aux Rapports scientifiques et techniques, 2006.

Chicago

du parallélisme, Laboratoire de l'informatique, Alain Darte, and Frédéric Vivien. 2006. “On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops.” LARA - Libre Acces aux Rapports scientifiques et techniques.

Harvard

du parallélisme, L.D.L., Darte, A. and Vivien, F. (2006) ‘On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops’, LARA - Libre Acces aux Rapports scientifiques et techniques.

BibTeX

@misc{duparallelisme2006optimality,
  title = {{On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops}},
  author = {du parallélisme, Laboratoire de l'informatique and Darte, Alain and Vivien, Frédéric},
  journal = {LARA - Libre Acces aux Rapports scientifiques et techniques},
  year = {2006}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.