The Design and analysis of parallel algorithms. (English) Zbl 0754.68053

Englewood Cliffs, NJ: Prentice Hall, Inc. XIII, 401 p. (1989).
The need for faster computers is increasingly recognized all over the world. The majority of computers which exist today are conceptually very similar to one another. Their architecture and mode of operations follow, more or less, the same basic design principles formulated by John von Neumann in the late 1940s. However parallelism is sure to change the way we think about and use computers. A parallel computer is one that consists of a collection of processing units that cooperate to solve a problem by working simultaneously on different parts of the problem.
The primary ingredient insolving a computational problem on any computer is the solution method or the algorithm. This book is about algorithms for parallel computations. It describes how to go about designing algorithms that exploit both the parallelism inherent in the problem and that available on the computer. It also shows how to analyse these algorithms in order to evaluate their speed and cost. The computational problems studied in this book are spread over fourteen chapters in mainly three groups of subject:
(1) sorting, searching and related problems,
(2) combinatorial and numerical problems and
(3) problems arising in a number of application areas. It is shown how a parallel algorithms is derived and analysed to solve each problem.
Chapter I is of introductory nature. The need for parallel computation as well as different parallel computer architectures are discussed. The primary characteristics of parallel algorithms like running time, number of processors and cost are also covered. The operations of selections merging, sorting and searching are given in chapters 2 to 5 respectively. Several computations of either a combinatorial or numerical nature are then examined, namely, generating permutations and combinations (Chapter 6), matrix operations (Chapter 7), numerical problems (Chapter 8), and computing Fourier transforms (Chapter 9). Four application areas are treated in Chapters 10 ( graph theory), 11 ( computational geometry), 12 ( traversing combinatorial spaces) and 13 ( decision and optimization). Finally Chapter 14 addresses a number of basic problems for which the definition of a time unit is interpreted as the time required to perform an operation on a pair of bits. Each chapter concludes with a set of problems, bibliographical remarks and a list of references.
This book is well written and may serve as a textbook for a graduate course on parallel algorithms. This book should also be useful to all those who are interested in design and analysis of parallel algorithms.
Reviewer: T.C.Mohan (Madras)


68W15 Distributed algorithms
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science