• Description of the Book
• Reviewers' Comments
• Table of Contents
• How to Get a Copy (free, if you want)

Description

The algorithms can be adapted to multiprocessor machines with varying degrees of granularity and a variety of processor configurations. They can be utilized inside a single VLSI chip, GPUs, on special-purpose parallel machines, on intermediate-size machines, or on large parallel computers, such as the IBM BlueGene or Cray T series, that are routinely used for solving complex scientific and engineering problems.

Basic algorithms, such as sorting and matrix multiplication, are described, as are algorithms to solve fundamental problems in image processing, computational geometry, and graph theory. A consistent approach, based on algorithmic techniques, shows how to apply paradigms such as divide-and-conquer and how to exploit the use of data movement operations. Since many of the algorithms were originally created by the authors using these techniques, the reader can actually see how efficient parallel algorithms are developed by following the design process.

Parallel Algorithms for Regular Architectures will be useful to researchers as well as practitioners who need to implement efficient parallel programs. The algorithms and operations can be incorporated into a variety of applications, and the design and analysis techniques can be exploited in an even greater range. Researchers and practitioners working in the areas of parallel computing, supercomputing, and high-performance computing will find useful information.

Some Comments from Reviewers

... I would rate this book as a must-buy for researchers and practitioners in parallel algorithms. It is a one-stop shopping guide to the current state of the art.

From the newsletter of the IEEE Technical Committee on Parallel Processing, February 1997, review by Hussein Alnumeiri:

... It also provides useful insight into how careful design of data partitioning and movement schemes can affect the performance and efficiency of algorithms ... the authors have been successful in simplifying and organizing the exposition of material so as to reduce the burden on the reader. ... The emphasis on detail distinguishes this book from other similar parallel processing books that often provide highly simplified versions of complex algorithms or provide sketchy details only.

From The American Mathematical Monthly, October 1997:

Good presentation of parallel algorithms for mesh and pyramid parallel computers. Considers sorting and matrix multiplication as well as many problems from image processing, computational geometry, and graph theory.

Table of Contents

• List of Figures
• Preface

1. Overview
   1. Introduction
   2. Models of Computation
   3. Forms of Input
   4. Problems
   5. Data Movement Operations
   6. Sample Algorithms
   7. Further Remarks
2. Fundamental Mesh Algorithms
   1. Introduction
   2. Definitions
   3. Lower Bounds
   4. Primitive Mesh Algorithms
   5. Matrix Algorithms
   6. Algorithms Involving Ordered Data
   7. Further Remarks
3. Mesh Algorithms
   1. Introduction
   2. Fundamental Graph Algorithms
   3. Connected Components (note: an important algorithm we refer to but didn't include is here)
   4. Internal Distances
   5. Convexity
   6. External Distances
   7. Further Remarks
4. Mesh Algorithms for Computational Geometry
   1. Introduction
   2. Preliminaries
   3. The Convex Hull
   4. Smallest Enclosing Figures
   5. Nearest Point Problems
   6. Line Segments and Simple Polygons
   7. Intersection of Convex Sets
   8. Diameter
   9. Iso-oriented Rectangles and Polygons
   10. Voronoi Diagram
   11. Further Remarks
5. Tree-like Pyramid Algorithms
   1. Introduction
   2. Definitions
   3. Lower Bounds
   4. Fundamental Algorithms
   5. Image Algorithms
   6. Further Remarks
6. Hybrid Pyramid Algorithms
   1. Introduction
   2. Graphs as Unordered Edges
   3. Graphs as Adjacency Matrices
   4. Digitized Pictures
   5. Convexity
   6. Data Movement Operations
   7. Optimality
   8. Further Remarks

• Order Notation
• Recurrence Equations
• Bibliography

How To Get a Copy

• You can buy a bound copy from MIT Press, ISBN 0-262-13233-8
• You can download a free copy here or through Research Gate, where Russ uploaded a copy.

Copyright © 2000-2017 Quentin F. Stout