Parallelizing graph construction operations in programs with cyclic graphs

摘要

Combining pointer analysis and dependence analysis can identify parallelism in programs with pointers or graphs. The compiler analysis techniques that have been proposed so far can only recognize parallelism in the traversal references of programs with cyclic graphs by analyzing the traversal patterns on graphs. Consequently, only the graph traversal operations will be parallelized while the graph construction operations will be left to be executed in sequential. Although this approach can usually parallelize the most time-consuming part of these programs (the graph traversal operations account for over 90% of total execution times in most programs), the rest of programs that accounts for less than 10% will dominate the execution on multiprocessor systems according to Amdahl's law. This paper presents a technique that can identify parallelism in the construction operations of programs even with cyclic graphs. Experiment results show this approach can parallelize the construction phase of such programs and achieve good speedup on multiprocessor systems.