Utpal Banerjee - Böcker

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.

Automatic transformation of a sequential program into a parallel form is a subject that presents a great intellectual challenge and promises a great practical reward. 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 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, "Loop Transformations for Restructuring Compilers", provides a rigorous theory of loop transformations and dependence analysis. The aim is 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.

This text is the third volume in the series "Loop Transformations for Restructuring Compilers". This series has been designed to provide a complete mathematical theory of transformations that can be used to automatically change a sequential program containing FORTRAN-like do loops into an equivalent parallel form. In this text the author extends the model to a program consisting of do loops and assignment statements, where the loops need not be sequentially nested and are allowed to have arbitrary strides. In the context of such a program, the author studies, in detail, dependence between statements of the program caused by program variables that are elements of arrays.

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.

This book is on dependence concepts and general methods for dependence testing. Here, dependence means data dependence and the tests are compile-time tests. We felt the time was ripe to create a solid theory of the subject, to provide the research community with a uniform conceptual framework in which things fit together nicely. How successful we have been in meeting these goals, of course, remains to be seen. We do not try to include all the minute details that are known, nor do we deal with clever tricks that all good programmers would want to use. We do try to convince the reader that there is a mathematical basis consisting of theories of bounds of linear functions and linear diophantine equations, that levels and direction vectors are concepts that arise rather natu­ rally, that different dependence tests are really special cases of some general tests, and so on. Some mathematical maturity is needed for a good understand­ ing of the book: mainly calculus and linear algebra. We have cov­ ered diophantine equations rather thoroughly and given a descrip­ of some matrix theory ideas that are not very widely known. tion A reader familiar with linear programming would quickly recog­ nize several concepts. We have learned a great deal from the works of M. Wolfe, and K. Kennedy and R. Allen. Wolfe's Ph. D. thesis at the University of Illinois and Kennedy & Allen's paper on vectorization of Fortran programs are still very useful sources on this subject.

Dependence Analysis may be considered to be the second edition of the author's 1988 book, Dependence Analysis for Supercomputing. It is, however, a completely new work that subsumes the material of the 1988 publication. This book is the third volume in the series Loop Transformations for Restructuring Compilers. This series has been designed to provide a complete mathematical theory of transformations that can be used to automatically change a sequential program containing FORTRAN-like do loops into an equivalent parallel form. In Dependence Analysis, the author extends the model to a program consisting of do loops and assignment statements, where the loops need not be sequentially nested and are allowed to have arbitrary strides. In the context of such a program, the author studies, in detail, dependence between statements of the program caused by program variables that are elements of arrays. Dependence Analysis is directed toward graduate and undergraduate students, and professional writers of restructuring compilers. The prerequisite for the book consists of some knowledge of programming languages, and familiarity with calculus and graph theory. No knowledge of linear programming is required.

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.

This book precisely formulates and simplifies the presentation of Instruction Level Parallelism (ILP) compilation techniques. It uniquely offers consistent and uniform descriptions of the code transformations involved. Due to the ubiquitous nature of ILP in virtually every processor built today, from general purpose CPUs to application-specific and embedded processors, this book is useful to the student, the practitioner and also the researcher of advanced compilation techniques. With an emphasis on fine-grain instruction level parallelism, this book will also prove interesting to researchers and students of parallelism at large, in as much as the techniques described yield insights that go beyond superscalar and VLIW (Very Long Instruction Word) machines compilation and are more widely applicable to optimizing compilers in general. ILP techniques have found wide and crucial application in Design Automation, where they have been used extensively in the optimization of performanceas well as area and power minimization of computer designs.

This book precisely formulates and simplifies the presentation of Instruction Level Parallelism (ILP) compilation techniques.

This volume contains the proceedings of the Fourth Workshopon Languages andCompilers for Parallel Computing, held inSanta Clara, California, in August1991. The purpose of theworkshop, held every year since 1988, is to bring togetherthe leading researchers on parallel programming languagedesignand compilation techniques for parallel computers. The papers in this book cover several important topicsincluding: (1) languages and structures to representprograms internally in the compiler, (2) techniques toanalyzeand manipulate sequential loops in order to generatea parallel version, (3)techniques to detect and extractfine-grain parallelism, (4) scheduling and memory-managementissues in automatically generated parallel programs, (5)parallel programming language designs, and (6) compilationof explicitly parallel programs. Together, the papers give a good overview of the researchprojects underway in 1991 in this field.

The articles in this volume are revised versions of the bestpapers presented at the Fifth Workshop on Languages andCompilers for Parallel Computing, held at Yale University,August 1992. The previous workshops in this series were heldin Santa Clara (1991), Irvine (1990), Urbana (1989), andIthaca (1988). As in previous years, a reasonablecross-section of some of the best work in the field ispresented. The volume contains 35 papers, mostly by authorsworking in the U. S. or Canada but also by authors fromAustria, Denmark, Israel, Italy, Japan and the U. K.

This book contains papers selected for presentation at theSixth Annual Workshop on Languages and Compilers forParallel Computing. The workshop washosted by the OregonGraduate Institute of Science and Technology. All the majorresearch efforts in parallel languages and compilers arerepresented in this workshop series. The 36 papers in the volume aregrouped under nine headings:dynamic data structures, parallel languages, HighPerformance Fortran, loop transformation, logic and dataflowlanguage implementations, fine grain parallelism, scalaranalysis, parallelizing compilers, and analysis of parallelprograms. The book represents a valuable snapshot of thestate of research in the field in 1993.

This volume presents revised versions of the 32 papers accepted for the Seventh Annual Workshop on Languages and Compilers for Parallel Computing, held in Ithaca, NY in August 1994.The 32 papers presented report on the leading research activities in languages and compilers for parallel computing and thus reflect the state of the art in the field. The volume is organized in sections on fine-grain parallelism, align- ment and distribution, postlinear loop transformation, parallel structures, program analysis, computer communication, automatic parallelization, languages for parallelism, scheduling and program optimization, and program evaluation.

This book presents the refereed proceedings of the Eighth Annual Workshop on Languages and Compilers for Parallel Computing, held in Columbus, Ohio in August 1995.The 38 full revised papers presented were carefully selected for inclusion in the proceedings and reflect the state of the art of research and advanced applications in parallel languages, restructuring compilers, and runtime systems. The papers are organized in sections on fine-grain parallelism, interprocedural analysis, program analysis, Fortran 90 and HPF, loop parallelization for HPF compilers, tools and libraries, loop-level optimization, automatic data distribution, compiler models, irregular computation, object-oriented and functional parallelism.