  Automatic parallelization improves the performance of serial program by
automatically converting to parallel program. Automatic parallelization
typically works in three phases: check for data dependencies in the input
program, perform transformations, and generate the parallel code for target
machine. Though automatic parallelization is beneficial, it is not done as a
part of compiling process because of the time complexity of the data dependence
tests and transformation techniques. Data dependencies arise because of data
access from memory required for the execution of instructions of the program.
In a program, memory is allocated for variables like scalars, arrays and
pointers. As of now, different techniques are used to identify data
dependencies in scalars, arrays and pointers in a program. In this paper, we
propose a graph based Data Dependence Identifier (DDI), which is capable of
identifying all types of data dependencies that arise in all types of
variables, in polynomial time. In our proposed DDI model, for identifying data
dependence in a program, we represent a program as graph. Though many graphical
representation of program exist, our approach of representing a program as
graph takes a different approach. Also using our DDI model, one can perform
basic transformations like dead code elimination, constant propagation, and
induction variable detection.

Distributed, Parallel, and Cluster Computing