Automatic transformation of a sequential program into a parallel form is
a subject that presents a great intellectual challenge and promises
great practical rewards. 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), but the demand for increasing speed is constant. The job of a
restructuring compiler is to discover the dependence structure of a
given program and transform the program in a way that is consistent with
both that dependence structure and the characteristics of the given
machine. Much attention in this field of research 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.
Loop Transformations for Restructuring Compilers: The Foundations
provides a rigorous theory of loop transformations. The transformations
are developed in a consistent mathematical framework using objects like
directed graphs, matrices and linear equations. The algorithms that
implement the transformations can then be precisely described in terms
of certain abstract mathematical algorithms. The book provides the
general mathematical background needed for loop transformations
(including those basic mathematical algorithms), discusses data
dependence, and introduces the major transformations. The next volume
will build a detailed theory of loop transformations based on the
material developed here.
Loop Transformations for Restructuring Compilers: The Foundations
presents a theory of loop transformations that is rigorous and yet
reader-friendly.
