Darte A., Robert Y., Vivien F. Scheduling and Automatic Parallelization

Springer, 2000. — 275 p.This book is devoted to the study of compiler transformations that are needed to expose the parallelism hidden in a program. This book is not an introductory book to parallel processing, nor is it an introductory book to parallelizing compilers. We assume that readers are familiar with the books High Performance Compilers for Parallel Computing by Wolfe and Supercompilers for Parallel and Vector Computers by Zima and Chapman, and that they want to know more about scheduling transformations.
In this book we describe both task graph scheduling and loop nest scheduling. Task graph scheduling aims at executing tasks linked by precedence constraints; it is a run-time activity. Loop nest scheduling aims at executing statement instances linked by data dependences; it is a compile-time activity. We are mostly interested in loop nest scheduling, but we also deal with task graph scheduling for two main reasons: (i) Beautiful algorithms and heuristics have been reported in the literature recently; and (ii) Several techniques used in task graph scheduling, like list scheduling, are the basis of the loop transformations implemented in loop nest scheduling.
As for loop nest scheduling our goal is to capture in a single place the fantastic developments of the last decade or so. Dozens of loop transformations have been introduced (loop interchange, skewing, fusion, distribution, etc.) before a unifying theory emerged. The theory builds upon the pioneering papers of Karp, Miller, and Winograd and of Lamport, and it relies on sophisticated mathematical tools (unimodular transformations, parametric integer linear programming, Hermite decomposition, Smith decomposition, etc.).
This book is intended for graduate or postgraduate students who want to understand the foundations of automatic parallelization techniques. It will be very useful to researchers interested in scheduling, compilers, and program transformations.
The book is self-contained, in that all proofs are included. Readers will need some basic mathematical skills and some familiarity with standard graph and linear programming algorithms, all of which can be found in Introduction to Algorithms by Cormen, Leiserson, and Rivest and in Theory of Linear and Integer Programming by Schrijver.Part I Unidimensional Problems
Scheduling DAGs without Communications
Scheduling DAGs with Communications
Cyclic Scheduling
Part II Multidimensional Problems
Systems of Uniform Recurrence Equations
Parallelism Detection in Nested Loops