Title :
Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs
Author :
Darte, Alain ; Vivien, Frédéric
Author_Institution :
Lab. LIP, Ecole Normale Superieure de Lyon, France
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 :
computational geometry; parallel algorithms; parallel architectures; direction vectors; distance vectors; nested loops; optimal algorithm; optimal fine grain parallelism detection; optimal medium grain parallelism detection; parallelization techniques; polyhedra; polyhedral reduced dependence graphs; uniform recurrence equations; Approximation algorithms; Difference equations; Linear programming; Linear systems; Scheduling algorithm; Vectors;
Conference_Titel :
Parallel Architectures and Compilation Techniques, 1996., Proceedings of the 1996 Conference on
Conference_Location :
Boston, MA
Print_ISBN :
0-8186-7633-7
DOI :
10.1109/PACT.1996.552676
