Browse Books

Reviewer: Maurice W. Benson

This book is organized as a text for use at the advanced undergraduate or graduate level (to follow an undergraduate course on design and analysis of algorithms). It is well suited to this purpose with clear descriptions of algorithms (in English and in a pseudocode equipped with parallel features), numerous examples to clarify concepts, and a large selection of problems at the end of each chapter. The extensive use of effective diagrams further strengthens the presentation. Akl starts with a discussion of models of parallel computation: the well-known single instruction stream, single data stream (SISD), multiple instruction stream, single data stream (MISD), single instruction stream, multiple data stream (SIMD), and multiple instruction stream, multiple data stream (MIMD) models. Further specialization is made as necessary for shared memory with exclusive read, concurrent read, exclusive write, or concurrent write. This is essentially a book on the analysis of parallel algorithms. As such, it presents a wide set of algorithms, as is indicated by the chapter headings: Selection, Merging, Sorting, Searching, Generating Permutations and Combinations, Matrix Operations, Numerical Problems, Computing Fourier Transforms, Graph Theory, Computational Geometry, Traversing Combinatorial Spaces, and Decision and Optimization. Some fairly elaborate algorithms are included (such as one for searching game trees, in the chapter on combinatorial search). Various architectures are considered: interconnection networks in the form of linear arrays, two-dimensional arrays (meshes), trees, multidimensional cubes, meshes of trees, as well as more specialized configurations. Of necessity, a book of this nature must select a representative set of algorithms. For example, the numerical section covers the solution of partial differential equations using a mesh of processors with each processor corresponding to a grid point in the discretization, but does not deal with the use of hypercubes and multigrid algorithms for the solution of these problems. Akl ends with a chapter on the bit complexity of parallel computations where problems such as parallel addition and multiplication of n-bit integers using trees and meshes of very simple processors are considered. One measure used for the analysis of parallel algorithms is the cost, defined to be the parallel running time multiplied by the number of processors employed by the algorithm. When the cost is proportional to a lower bound on the number of operations for a general sequential solution to the problem, the parallel method is called “cost optimal.” Thus information concerning an optimal sequential algorithm is required in order to determine if a parallel algorithm is cost optimal. When the understanding of sequential solutions is not adequate, a parallel algorithm can be judged by its efficiency, given by the running time of the best sequential algorithm divided by the parallel algorithm cost. Algorithms are also examined in terms of adaptability—the ability to exploit (within limits) however many processors are present on a given parallel computer. Except for MIMD machines where experiment is the recommended way of determining running time, Akl analyzes the algorithms he presents in detail according to the above criteria. Consideration is also given to other factors such as interconnection lengths for different connection schemes (e.g., trees versus meshes). This is a valuable reference as well as a text. It covers a wide range of topics, and an extensive bibliography is provided at the end of each chapter. The algorithms presented range from simple to complex. Each area presented is briefly motivated, and sufficient background is given for all algorithms to make the book self-contained. The material is presented with a clarity that makes it a good reference or learning tool for anyone interested in parallel computing.