A classification of nested loops parallelization algorithms
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 217-234
- https://doi.org/10.1109/etfa.1995.496776
Abstract
Compares three nested loops parallelization algorithms (Allen and Kennedy's algorithm, Wolf and Lam's algorithm and Darte and Vivien's algorithm) that use different representations of distance vectors as input. The authors identify the concepts that make them similar or different. The authors study the optimality of each with respect to the dependence analysis it uses. The authors propose well-chosen examples that illustrate the power and limitations of the three algorithms. This study permits the authors to identify which algorithm is the most suitable for a given representation of dependences.Keywords
This publication has 14 references indexed in Scilit:
- Revisiting the decomposition of Karp, Miller and WinogradPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- (Pen)-ultimate tiling?Integration, 1994
- Mapping uniform loop nests onto distributed memory architecturesParallel Computing, 1994
- Some efficient solutions to the affine scheduling problem. I. One-dimensional timeInternational Journal of Parallel Programming, 1992
- LINEAR SCHEDULING IS NEARLY OPTIMALParallel Processing Letters, 1991
- Dataflow analysis of array and scalar referencesInternational Journal of Parallel Programming, 1991
- Supernode partitioningPublished by Association for Computing Machinery (ACM) ,1988
- The parallel execution of DO loopsCommunications of the ACM, 1974
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967
- Analysis of Programs for Parallel ProcessingIEEE Transactions on Electronic Computers, 1966