@inproceedings{7b5fcb4a8e8844e6b3cf1c72d7c420a1,
title = "Identifying parallelism in programs with cyclic graphs",
abstract = "Dependence analysis algorithms have been proposed to identify parallelism in programs with tree-like data structures. However, they can not analyze the dependence of statements if recursive data structures of programs are cyclic. This paper presents a technique to identify parallelism in programs with cyclic graphs. The technique consists of three steps: (1) Traversal patterns that loops or recursive procedures traverse graphs are identified, and the statements that construct the links of traversal patterns are located by definition-use chains of recursive data structures; (2) Shape analysis is performed to estimate possible shapes of traversal patterns; (3) Dependence analysis is performed to identify parallelism using the result of shape analysis. This approach can identify parallelism in programs with cyclic data structures due to the facts that many programs follow acyclic structures (i.e. traversal patterns) to access all nodes on the cyclic data structures. Once the traversal patterns are isolated from the overall data structures, dependence analysis can be applied to identify parallelism.",
keywords = "Algorithm design and analysis, Data analysis, Data structures, Pattern analysis, Performance analysis, Recursive estimation, Shape, State estimation, Tree data structures, Tree graphs",
author = "Hwang, \{Yuan Shin\} and J. Saltz",
note = "Publisher Copyright: {\textcopyright} 2000 IEEE.; International Conference on Parallel Processing, ICPP 2000 ; Conference date: 21-08-2000 Through 24-08-2000",
year = "2000",
doi = "10.1109/ICPP.2000.876120",
language = "English",
series = "Proceedings of the International Conference on Parallel Processing",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "201--208",
editor = "Lilja, \{David J.\}",
booktitle = "Proceedings - 2000 International Conference on Parallel Processing, ICPP 2000",
}