Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs

摘要: This paper presents an optimal algorithm for detecting line or medium grain parallelism in nested loops whose dependences are described by approximation of distance vectors polyhedra. In particular, this is the classical direction sectors. result generalizes, to case several statements. Wolf and Lam's which a single statement. Our relies on dependence uniformization process parallelization techniques related system uniform recurrence equations. It can also be viewed as combination both Allen Kennedy's algorithm.