TABLE OF CONTENTS As we learned in Chapter 1, optimization has an important function in the acceptance of a programming language if the optimizer does not do a good job, no one will use the language. As a result, optimization technology has become quite sophisticated. However, most of the development effort in optimization technology has focused on scalar machines. On these machines, the principal optimizations are register allocation, instruction scheduling, and reducing the cost of array address calculations.
Parallelism introduces much more complexity into the optimization process. For parallel computers, the principal optimization becomes finding parallelism in a sequential code and tailoring that parallelism to the target machine, including its memory hierarchy. The principal strategy for seeking out useful parallelism is to look for a data decomposition in which parallel tasks perform similar operations on different elements of the data arrays. In Fortran, this strategy naturally maps to running different iterations of DO-loops in parallel. Data decomposition is effective on scientific problems because it is scalable as the problem size increases, so does the available parallelism.
Given the focus in Fortran on loop iterations, an advanced compiler must be able to determine whether Bernstein's conditions [40] (see Section 1.5.2) are satisfied for every pair of iterations. Examining loop iterations is complicated enough; adding to the complexity is the fact that most code within a data-parallel loop will reference subscripted array variables. As a result, the compiler must have the ability to analyze such references to determine whether two different iterations...
