A Method of Data Dependency Analysis for C Program with Recursive Data Structures

摘要

Recently, the necessity for parallel programming has been increased with the rapid spread of multicore/multiprocessor systems. However, it is difficult for a programmer to create a highly-effective and high-performance parallel program. So, we are developing the automatic translator from C programs to parallel programs using MPI(Message Passing Interface). In our conventional automatic parallelism analysis of C program with pointer variables, it was able to analyze the data dependencies of only the pointer variables declared explicitly in the code. In this research, we have first applied the Shape analysis to C programs with pointer variables for getting to know the form of the recursive data structures which will be allocated and constructed dynamically at the time of execution. Then, using the result of the analysis, we can analyze the data dependencies of recursive data structures, such as linked list or binary tree structures, and detect more parallelism from C program.