首页 | 本学科首页   官方微博 | 高级检索  
     


Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs
Authors:Alain Darte  Frédéric Vivien
Affiliation:(1) Laboratoire LIP, URA CNRS 1398, École Normale Supérieure de Lyon, F-69364 Lyon Cedex 07
Abstract:This paper presents an optimal algorithm for detecting line or medium grain parallelism in nested loops whose dependences are described by an approximation of distance vectors by polyhedra. In particular, this algorithm is optimal for the classical approximation by direction sectors. This result generalizes, to the case of several statements. Wolf and Lam's algorithm which is optimal for a single statement. Our algorithm relies on a dependence uniformization process and on parallelization techniques related to system of uniform recurrence equations. It can also be viewed as a combination of both Allen and Kennedy's algorithm and Wolf and Lam's algorithm.
Keywords:Automatic parallelization  multi-dimensional schedule  loop nest  system of uniform recurrence equations  dependence analysis  polyhedral reduced dependence graph
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号