Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs
- 24 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 281-291
- https://doi.org/10.1109/pact.1996.552676
Abstract
This paper proposes an optimal algorithm for detecting fine or medium grain parallelism in nested loops whose dependences are described by an approximation of distance vectors by polyhedra. In particular it is optimal for direction vectors, which generalizes Wolf and Lam's algorithm (1991) to the case of several statements. It relies on a dependence uniformization process and an parallelization techniques related to system of uniform recurrence equations.Keywords
This publication has 13 references indexed in Scilit:
- Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A classification of nested loops parallelization algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- REVISITING THE DECOMPOSITION OF KARP, MILLER AND WINOGRADParallel Processing Letters, 1995
- Affine-by-Statement Scheduling of Uniform and Affine Loop Nests over Parametric DomainsJournal of Parallel and Distributed Computing, 1995
- Constructive methods for scheduling uniform loop nestsIEEE Transactions on Parallel and Distributed Systems, 1994
- Some efficient solutions to the affine scheduling problem. Part II. Multidimensional timeInternational Journal of Parallel Programming, 1992
- Some efficient solutions to the affine scheduling problem. I. One-dimensional timeInternational Journal of Parallel Programming, 1992
- A loop transformation theory and an algorithm to maximize parallelismIEEE Transactions on Parallel and Distributed Systems, 1991
- Supernode partitioningPublished by Association for Computing Machinery (ACM) ,1988
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967