Automatic transformation of a sequential program into a parallel form is
a subject that presents a great intellectual challenge and promises a
great practical award. There is a tremendous investment in existing
sequential programs, and scientists and engineers continue to write
their application programs in sequential languages (primarily in
Fortran). The demand for higher speedups increases. The job of a
restructuring compiler is to discover the dependence structure and the
characteristics of the given machine. Much attention has been focused on
the Fortran do loop. This is where one expects to find major chunks of
computation that need to be performed repeatedly for different values of
the index variable. Many loop transformations have been designed over
the years, and several of them can be found in any parallelizing
compiler currently in use in industry or at a university research
facility.
The book series on KappaLoop Transformations for Restructuring
Compilerskappa provides a rigorous theory of loop transformations and
dependence analysis. We want to develop the transformations in a
consistent mathematical framework using objects like directed graphs,
matrices, and linear equations. Then, the algorithms that implement the
transformations can be precisely described in terms of certain abstract
mathematical algorithms. The first volume, Loop Transformations for
Restructuring Compilers: The Foundations, provided the general
mathematical background needed for loop transformations (including those
basic mathematical algorithms), discussed data dependence, and
introduced the major transformations. The current volume, Loop
Parallelization, builds a detailed theory of iteration-level loop
transformations based on the material developed in the previous book.
