Dependence analysis and evaluation of inherent parallelism of programs

Abstract

Dependencies are relations between statements of a program. They indicate the constraints imposed on the order of statement execution, and are often used for the evaluation, optimization, vectorization and parallelization of programs. By means of dependence analysis, much work has been done to exploit the parallelism in the loops in which there are no dependencies that cross from one iteration of the loop to another. Only recently an approach was proposed for exploiting the parallelism available in loops with cross-iteration dependencies. -- The aim of this project is to evaluate inherent parallelism of sequential programs by means of dependence analysis. The thesis first introduces the definitions, concepts and basic dependency analysis algorithms, and presents a uniform representation of dependencies called a dependence graph. Then, using the dependence graph, a general approach is presented which can be used to analyze the parallelism between loops as well as between loops and other parts of a program. This approach was implemented as a program called DSA (Dependence and Speedup Analyzer), used to perform the dependence analysis and to evaluate the inherent parallelism of Fortran programs. Finally, the implementation of DSA is briefly described and its use is illustrated by a series of examples.