Dependence Analysis and Parallelizing Transformations
Sanjay V. Rajopadhye · 2002
The first impression one gets when phrases like dependence analysis and automatic parallelization are mentioned, is that of loop programs and array variables. This is not surprising, since loops is the classic repetitive structure in any programming language, and clearly, this is where programs spend a significant amount of their time. Second, because of the early impetus on high performance computing for large numerical applications (eg. FORTRAN programs) on supercomputers, there has been a long research effort on parallelizing such programs. The area has been active for over a quarter century, and a number of well known texts on this topic are readily available. Any approach to automatic parallelization must be based on the following fundamental notions: (i) detection of which statements in which iterations of a (possibly multiply nested and possibly imperfect) loop depend on each other, in the precise sense that one of them produces a value that is consumed by the other; (ii) hence determining which operations can be executed in parallel; and (iii) transforming the program so that this choice of parallelization rendered explicit. The first problem is called dependence analysis, the second constitutes the additional analysis necessary to choose the parallelization, and the third is called program or restructuring. In all generality, these are extremely difficult problems. Nevertheless, for certain classes of programs elegant and powerful methods are available. Therefore, rather than giving “yet another survey” of a vast field, we present in this chapter, a somewhat less known approach,