A Survey of Data Dependence Analysis Techniques for Automated Parallelization

Description

Finding parallelism that exists in a software program depends a great deal on determining the dependencies that exist between statements that exist in that program. Instructions that are found to be independent of one another can be executed in parallel with one another with the hope of increasing the execution speed of a software program. Determining dependence relationships between statements in software programs, however, is not an easy task. There exist many different methods for determining dependence relations, filling different requirements from speed to accuracy. This paper will discuss a number of these techniques, detailing several different classes of dependence analysis techniques as well as several different techniques within these classes.