An introduction to parallel algorithms. (English) Zbl 0781.68009

Amsterdam etc.: Addison-Wesley. X, 566 p. (1992).
The book is an introduction to the design and analysis of parallel algorithms. It covers the most important techniques and paradigms for parallel algorithm design. A wide range of topics is discussed in depth, including lists and trees, searching and sorting, graphs, computational geometry, pattern matching, arithmetic computations, and randomized algorithms. The book also provides insights into the theory of parallel computations.
The formal model used is the shared-memory model, which allows the establishment of optimal results. All the algorithms are described at a higher level called the work-time presentation framework, which is architecture-independent. The performance of parallel algorithm is measured in terms of two parameters: the total number of operations and the parallel time. This framework is closely related to the data-parallel programming environment, which has been shown to be effective on both SIMD or MIMD, shared memory or distributed memory architectures. The book also includes a wide range of exercises from routine to nontrivial extensions of the material, for each chapter.
Reviewer: S.Pavel (Kingston)


68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68W15 Distributed algorithms
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q25 Analysis of algorithms and problem complexity