TABLE OF CONTENTS This chapter and the next cover the use of dependence to automatically parallelize sequential code. Following the historical development, we begin with parallelism that has no minimum granularity. This kind of parallelism is useful in vector machines and machines with instruction-level parallelism, such as VLIW and superscalar processors. Because most of the theory was developed first on vector machines, the discussion will concentrate on vectorization. The treatment of granularity-sensitive parallelism will be postponed until Chapter 6.
In Chapter 2, we presented the parallelization algorithm codegen, shown in Figure 2.2, for automatically finding fine-grained parallelism in a Fortran program. That algorithm finds essentially all the parallelism possible using only the transformations of loop distribution and statement reordering. In this chapter, we expand on the basic code generation algorithm by exploring other transformations, such as loop interchange, needed to increase the amount of fine-grained parallelism to a level that makes automatic vectorization practical and effective.
We illustrate the power of two of these advanced transformations on a fairly typical sequential coding of matrix multiplication:
DO J = 1, M DO I = 1, N T = 0.0 DO K = 1, L T = T + A(I,K) * B(K,J) ENDDO...
