Browse Books

Reviewer: Gowri Ramanathan

Quinn's previous books include Designing efficient algorithms for parallel computers , published in 1987 [1]. This book is primarily a revision of the 1987 book with a number of new topics and updates of the older material. Anyone observing the growth of parallel processing will know how much has changed in the past seven years; the author has updated the contents to reflect the new lessons learned in this area. He has also deleted topics such as logic programming and pipelined vector processors and included the new topics parallel random access machine (PRAM) algorithms, mapping and scheduling, and parallel imperative programming languages. This book includes some recent findings in parallel computing, so it is a good source of information, especially if you have the older edition. This book is intended as a textbook for the fourth-year and graduate curriculum in parallel computing. Quinn introduces interconnection networks, programming models, parallel programming languages, mapping, and scheduling as important components of the design of parallel algorithms. As each topic is intended to serve as an introduction to algorithm design, a few vital aspects of some of the topics are omitted, for example, the role of communication primitives of interconnection networks. The first five chapters contain introductory material for the eight later chapters of numerical and nonnumerical algorithms. The algorithms included are prefix sums, matrix multiplication, fast Fourier transform, solving linear systems of equations, sorting, dictionary operations, graph algorithms (searching a graph, connected components, all-pairs shortest path, single-source shortest path, and minimum-cost spanning tree) and combinatorial search (branch-and-bound and alpha-beta search). Each chapter is followed by a summary and bibliographical notes. The bibliography at the end of the book spans 43 pages and includes important publications dating back to Jacobi's work in 1845. The glossary lists all the terms and phrases used in the text. Exercises appear at the end of each chapter, and the difficult ones are marked. As no solution manual accompanies the book, peeking at these problems quickly is impossible. Some subtle features of this book help the reader in many ways; for instance, unusually wide margins provide space to write down elaborate notes, and the list of Library of Congress call numbers of major journals saves time in skimming through voluminous library catalogues. In the introduction, the author presents the humble beginning of parallel computation and quickly moves on to present control and data parallelism, illustrating their faster performance using the Sieve of Eratosthenes algorithm for prime numbers. Chapter 2 presents the PRAM model with all three of its categories and discussion of their practical implications. Following the programming models, theoretical parallel system models, such as mesh, binary tree, hypertree pyramid, butterfly, hypercube, cube-connected cycles, shuffle-exchange, and de Bruijn are included as part of chapter 3. The second part of chapter 3 covers the architectural details of the commercially available parallel systems: Connection Machine CM-200, Sequent Symmetry, BBN Butterfly TC2000, nCUBE-2, Thinking Machines CM-5, and the Intel Paragon XP/S. This chapter concludes with Flynn's taxonomy and definitions of the common parallel algorithm performance measures: speedup, scaled speedup, and parallelizability. In chapter 4, the author presents parallel programmers with the available programming languages and their nuances. The content of this chapter is important for algorithm designers to go from designing to coding their algorithms. This chapter distinguishes this book from any other book on parallel algorithms, as the theme of this book includes practical aspects of algorithm design. The calculation of &pgr; illustrates how programming differs in Fortran 90, C*, Sequent C, nCUBE C, OCCAM, and C-Linda. In chapter 5, Quinn draws attention to the mapping and scheduling issues of running parallel programs. Though mapping or embedding is part of almost any parallel algorithm book, the discussion of scheduling issues is unique to this book. Before presenting any application algorithms, the author shares his experience in algorithm design strategies and enumerates them in four steps, which can be found in the appendix. Reduction, broadcast, and prefix sums are identified as frequent operations in parallel algorithms. Efficient algorithms to implement these operations using the author's own algorithm design strategies are developed and presented in chapter 6. Four more design strategies involving load balancing, memory latency, and contention for shared resources are illustrated using the matrix multiplication algorithm. The algorithms for matrix operations are explained in all the parallel algorithm books, but no previous presentation has reflected earlier parallel programming experiences as this book does. The other numerical algorithms that are covered in all parallel algorithm books, namely fast Fourier transform and solving linear systems of equations, are the subjects of chapters 8 and 9. For each of these problems, adequate mathematical backgrounds, discussion on occurrences of these problems in practice, sequential algorithms to solve these problems, a parallel algorithm for a hypercube or uniform memory access, and sometimes speedup curves are presented. The nonnumerical algorithms included are sorting, parallel search, and graph algorithms. Finally, the implementation details of branch-and-bound algorithms are discussed, using the traveling salesperson algorithm as an example. Another book that comes close to this work in its goals is by Kumar et al. [2]. The two books are almost identical in their selection of topics; the major differences are in the depth of the presentation, the number of algorithms discussed for each problem, and the number of parallel pseudocodes included. Quinn's book has enough introductory material to help a student or anyone who is impatient to start writing parallel programs, but for more in-depth issues of parallel programming, the reader will have to consult other books. Authors of books of this kind have to strike a delicate balance between the required exposure to the theory and its intended practical value; in this respect, Quinn has done a superb job. While this book can serve as an excellent textbook for introductory parallel programming classes, it can also be considered as a supplementary text for advanced topics courses on this subject.