Related Information
Publication List
|
Parallelizing Compilers
We have recently developed a flow-sensitive algorithm to compute the
interprocedural definition-use chains of dynamic pointer-linked data structures.
This algorithm relates the statements that construct links of dynamic
pointer-linked data structures (i.e. definitions) to the statements that might
traverse the structures via the links (i.e. uses). The outcome of this
computation provides the essential information for program transformations and
communication generations of data-parallel programs or optimizations and
parallelization of sequential programs with dynamic pointer-linked data
structures on parallel and distributed systems.
We have proposed a traversal-pattern-sensitive shape analysis approach to take
advantage of the availability of the definition-use information. It gathers the
traversal patterns of programs on dynamic pointer-linked data structures and
then estimates the possible shapes and connections of structures specified by
traversal patterns. This approach can simplify dependence analysis by using the
knowledge of traversal patterns to avoid gathering unnecessary alias and
connection information. Furthermore, it can facilitate dependence analysis
algorithm to detect parallelism in programs even with cyclic data
structures. The dependence test algorithm presented in my dissertation first
performs conflict analysis by assuming that each unique path leads to a distinct
storage location, and then validates the result by taking the effects of aliases
and connections into account using traversal-pattern-sensitive shape analysis.
|
