Introduction to parallel algorithms and architectures: arrays, trees, hypercubes. (English) Zbl 0743.68007

Leighton, F. Thomson

San Mateo, CA: Morgan Kaufmann Publishers. XVII, 831 p. (1992).

This book is a well written introduction to parallel algorithms and the most popular network architectures. It was developed on the basis of seminar papers and lecture notes, and is based on many years of teaching at the MIT. The book contains the latest results and techniques and can well be used for early graduate courses. An overwhelming number of more than 750 exercises contains about 250 designated as the most valuable. Others are posed as difficult or as research problems.
The contents itself is organized in three chapters according to the network architecture: arrays and trees for Chapter 1 (117 pages), meshes of trees for Chapter 2 (117 pages), and hypercubes and related networks for Chapter 3 (388 pages). Within each chapter, the material is organized according to the application domain, starting with the simple algorithms and advancing to the more complicated.
Emphasis is placed on the paradigms and primitives for parallel algorithm design. The whole volume has as much as 811 pages of which 18 are used for the bibliography. The author of this book plans the publication of another volume on PRAM’s that are shortly discussed on 14 pages in section 3.6.

Reviewer: M.Jantzen (Hamburg)

MSC:

68-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68Q80	Cellular automata (computational aspects)
68Q10	Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68W15	Distributed algorithms

Keywords:

parallel algorithms; network architectures; trees; hypercubes; meshes; de Bruijn graphs; shuffle exchange