Program Analysis Techniques for Transforming Programs for Parallel Execution

Kleanthis Psarris
Department of Computer Science
The University of Texas at San Antonio


In a multiple processor system, computer programs have to be redesigned to 
efficiently use the parallel processors and deliver higher performance. One 
major approach is automatic detection of parallelism, in which existing 
conventional sequential programs are translated into parallel programs, in 
order to benefit from the presence of multiple processors. Optimizing 
compilers rely upon program analysis techniques to detect data dependences 
between program statements. The results of the analysis enable the compiler 
to identify code fragments that can be executed in parallel. 

In this talk we discuss various program analysis techniques employed by 
compilers to detect data dependences in scientific programs. The data 
dependence problem can not be solved efficiently in general. A number of data 
dependence tests have been proposed in the literature. In each test there is 
a different tradeoff between accuracy and efficiency. We present an analytical 
and experimental evaluation of several data dependence tests, including the 
Banerjee test, the I-Test, Fourier Motzkin Variable Elimination and the 
Omega test. We show the fundamental relationship between these tests and we 
compare them in terms of accuracy and efficiency in practice. Finally, we 
integrate the above research and develop an efficient and exact dependence 
analyzer.