Identifying parallelism in programs with cyclic graphs

摘要: Dependence analysis algorithms have been proposed to identify parallelism in programs with tree-like data structures. However, they cannot analyze the dependence of statements if recursive structures are cyclic. This paper presents a technique cyclic graphs. The consists three steps: (1) traversal patterns that loops or procedures traverse graphs identified, and construct links will be located by definition-use chains structures; (2) traversal-pattern-sensitive shape is performed estimate possible shapes patterns, (3) using result analysis. approach can due facts many follow acyclic (i.e. patterns) access all nodes on Once isolated from overall structures, applied parallelism.