Because of the universal nature of parallelism, it has the potential of becoming a concern of virtually every area of computer science. Hence, an increasing number of books have been published on topics amenable to parallelism, from computer architecture to programming languages to numerical algorithms. A number of them have attempted to provide some sort of overview of a broad range of topics, as this work does.
The book is a collection of survey papers on a potpourri of topics that are grouped under the umbrella of parallel algorithms. The chapters are written by different authors, mostly from the UK, giving the book the flavor of a conference proceedings. Where appropriate, however, each chapter includes tutorial material to introduce the uninitiated reader to the fundamentals of the topic before getting into the relevant parallelism. Since it is not a textbook, no exercises are provided.
The material in the book falls roughly into three sections: software paradigms, general methods, and applications. It consists of 15 chapters:
Parallel Software Paradigms
The Divide-and-conquer Paradigm as a Basis for Parallel Language Design
The Neural Network Paradigm
Problem-driven versus Hardware-driven Approaches to the Design of Concurrent Programs
Parallel Branch-and-bound
Algebraic Transformation Approach for Parallelism
Discrete Event Simulation in Parallel
Genetic Algorithms in Optimization and Adaptation
Randomized Algorithms for Packet Routing on the Mesh
Asynchronous Iterative Algorithms: Models and Convergence
Parallel Dynamic Programming
Parallel Derandomisation Techniques
Parallel Algorithms for Matrix Operations and Their Performance on Multiprocessor Systems
Neural Networks for Robot Control
Computational Complexity of Parallel Algorithms
The chapter titles are reasonable descriptions of the content and reflect parallelism’s broad applicability to algorithm design. The chapters are of a high quality and appear to be written specifically for this collection. They are as up to date as can be expected. The coverage of topics is generally good, but while chapter 3 provides a nice tutorial on neural nets, it gives only a token discussion of parallelism. Chapter 14 includes no discussions of parallelism and should not have been included in this book.
The purpose of the book is to “provide a clear description and state of the art overview of current concepts and work on parallel algorithms.” The editors have met this purpose. They have done a good job of representing the pervasive nature of parallelism with an interesting choice of topics. The book should interest students and professionals who want an overview of the uses, impact, and potential of parallel algorithms.
