Leighton F.T. Introduction to Parallel Algorithms and Architectures. Arrays, Trees, Hypercubes

Morgan Kaufmann, 1992. — 847 p.This book is designed to serve as an introduction to the exciting and rapidly expanding field of parallel algorithms and architectures. The text is specifically directed towards parallel computation involving the most popular network architectures: arrays, trees, hypercubes, and some closely related networks.
The text covers the structure and relationships between the dominant network architectures, as well as the fastest and most efficient parallel algorithms for a wide variety of problems. Throughout, emphasis is placed on fundamental results and techniques and on rigorous analysis of algorithmic performance. Most of the material covered in the text is directly applicable to many of the parallel machines that are now commercially available. Those portions of the text that are of primarily theoretical interest are identified as such and can be passed without interrupting the flow of the text.
The book is targeted for a reader with a general technical background, although some previous familiarity with algorithms or programming will prove to be helpful when reading the text. No previous familiarity with parallel algorithms or networks is expected or assumed.Arrays and Trees.
Elementary Sorting and Counting.
Integer Arithmetic.
Matrix Algorithms.
Retiming and Systolic Conversion.
Graph Algorithms.
Sorting Revisited.
Packet Routing.
Image Analysis and Computational Geometry.
Higher-Dimensional Arrays.
Meshes of Trees.
The Two-Dimensional Mesh of Trees.
Elementary O(log N)-Step Algorithms.
Integer Arithmetic.
Matrix Algorithms.
Graph Algorithms.
Fast Evaluation of Straight-Line Code.
Higher-Dimensional Meshes of Trees.
Hypercubes and Related Networks.
The Hypercube.
The Butterfly, Cube-Connected-Cycles, and Beneš Network.
The Shuffle-Exchange and de Bruijn Graphs.
Packet-Routing Algorithms.
Sorting.
Simulating a Parallel Random Access Machine.
The Fast Fourier Transform.
Other Hypercubic Networks.