Loop Transformations for Restructuring Compilers: The FoundationsAutomatic 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. |
Contents
| 3 | |
Unimodular Matrices | 25 |
Linear Equations and Inequalities | 49 |
vi | 76 |
33 | 83 |
11 | 90 |
Basic Concepts | 97 |
15 | 102 |
49 | 150 |
Introduction to Loop Transformations | 163 |
Appendix | 195 |
52 | 203 |
55 | 212 |
59 | 235 |
Bibliography | 293 |
Linear Dependence Problem | 113 |
Other editions - View all
Loop Transformations for Restructuring Compilers: The Foundations Utpal Banerjee Limited preview - 2007 |
Loop Transformations for Restructuring Compilers: The Foundations Utpal Banerjee No preview available - 1993 |
Common terms and phrases
Algorithm 2.1 antichains B₁ calloc calloc(m cause a dependence coefficient define denote dependence constraints dependence equation dependence graph dependence problem dependent on statement diagonal diagonal matrix digraph direction vector distance vectors doall loop double loop echelon matrix echelon reduction elementary matrices elements enddo enddo enddoall equivalence relation equivalent Example execute in parallel execution order Exercise FILE file_ptr flow dependence fprintf(file_ptr GCD test given I₁ index points index value index variables input variable instance S(i integer matrix integer solution integer vector Interchange rows iteration H(i j₁ K₁ K₂ loop limits loop nest loop permutation loop transformation m-vectors memory location n₁ nonempty nonzero partial order permutation matrix printf("Enter the Number RATIONAL relation satisfying sequential sizeof(INT Solution to XA solutions exist solve statement instances STEP strongly connected component subsets Theorem transformed program unimodular matrix V₁ weakly connected components X(IA
Popular passages
Page 26 - AB is defined if and only if the number of columns of A is equal to the number of rows of B...
Page 297 - Zhu. An Efficient Data Dependence Analysis for Parallelizing Compilers. IEEE Transactions on Parallel and Distributed Systems, vol. 1, no. 1, pp.
Page 299 - Data Dependence and Its Application to Parallel Processing," International Journal of Parallel Programming, Vol.
Page 6 - S is said to be a chain if it contains no incomparable elements; a chain is maximal if it is not a proper subset of any other chain.
Page 294 - Nicolau et al. [NGGP91], pages 192-219. [BCKT79] Utpal Banerjee, Shyh-Ching Chen, David J. Kuck, and Ross A. Towle. Time and parallel processor bounds for Fortranlike loops.
Page 4 - The Cartesian product S x T of two sets S and T is the set of all ordered pairs (a, b) with ae S and be T. The product S x 5 is abbreviated as S2, S2 XS is abbreviated as S3 and so on. The elements of 5" are called n-tuples of elements of S.
Page 5 - A relation is an equivalence relation if it is reflexive, symmetric and transitive. An equivalence relation ~ on a set S gives rise to equivalence classes.
Page 45 - I ought to have stated antecedently, is a deduction from the theory of resultants and the well-known fact that the determinant of a product of matrices is the product of their determinants. Thus each of the three laws of motion is deduced independently of the two others.
Page 101 - When we pass an assignment, we "relativize" the path condition (p with respect to it; if the assignment is of the form x := e, where x is a variable and e is an expression, we substitute e instead of each free occurrence of x in the path condition.
Page 6 - If a < ¿>, then we say that a is a predecessor of b, and that b is a successor of a. If a < b and there is no с in 5 such that a < с < b, then a is an immediate predecessor of b.