Browse Books

Reviewer: Hans J. Schneider

A technique to restructure nested loops for parallel machines is discussed. This monograph focuses on the use of loop tiling for minimizing synchronization and communication cost and maximizing parallelism. The author does not consider other kinds of loop transformation or optimizing for cache locality. The book is organized into three parts. The first part introduces the mathematical background as well as the theory of nonsingular loop transformations. The second deals with rectangular tiling and then addresses the general case of parallelepiped tiling. The last part focuses on minimizing the execution time of a loop nest on a distributed memory machine. Chapter 1 presents some mathematical concepts necessary to understand the subject. The author emphasizes convex cones, which are used to analyze data dependency, loop permutability, legality, and selection of tile size and shape. The next chapter formally introduces the basic concepts of loop transformations. It defines perfectly nested loops, dependence vectors, and their polyhedra, and it treats fully permutable loop nests. Nonsingular transformations, closely related to tiling, are briefly reviewed. Rectangular tiling, covered in chapter 3, uses squares or rectangles of the same size and shape to partition the iteration space; formally, a concrete partitioning is characterized by a tile size vector and a tile offset. In general, the legality of a rectangular tiling can be checked by testing the existence of integer solutions to a system of inequalities; the author also describes a simpler test that is sufficient in practical applications. Finally, he discusses several related transformations, such as strip-mining, loop coalescing, and loop skewing. Chapter 4 extends the investigations to parallelepiped tiling, which offers more opportunities for exposing parallelism, improving locality, and reducing communication overhead. After illustrating this technique with an example and giving the formal definition, the author again discusses how to use integer programming to test legality exactly and then describes a practical test. Finally, he presents an alternative formal model that can clarify the duality between loop tiling and loop partitioning. The final chapters consider implementation on a distributed memory machine. Chapter 5 describes a suite of compiler techniques to generate a single-program, multiple data (SPMD) program to execute a tiled iteration space. Tiles are assigned to processors as atomic units of computation and then data distribution is derived using the computer-owns rule, by which a processor owns the data it computes. A detailed formal discussion of message-passing code generation, local memory management, and global-to-local address translation follows. Some experimental results round out the chapter. Chapter 6 addresses the problem of determining the best tile shape to minimize inter-tile communication if the tile size is given; this analysis assumes constant distance vectors. Conversely, chapter 7 deals with the more difficult problem of finding the best tile size once the shape is known, but restricting discussion to a two-dimensional iteration space. The author writes well and, at the beginning of each chapter, states what that chapter will cover. The book is clearly organized, and “Further Reading” sections are helpful for readers who are entering the field. Overall, the author succeeds in giving a consistent presentation of the state of the art in a specialized topic. The book can be used as a reference by professionals in compiler techniques, but they should be very familiar with the notation and terminology of linear algebra.