##
**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.

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)

### MSC:

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 |