- Description of the Book
- Reviewers' Comments
- Table of Contents
- Cover Illustration
- Ordering Information

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, on special-purpose parallel machines, on intermediate-size machines, or on large parallel computers, such as the IBM SP2, Cray T3D/T3E, Intel Paragon, or MasPar MP1/MP2, that are routinely used for solving complex scientific and engineering problems.

Basic algorithms, such as sorting, matrix multiplication, and parallel prefix, 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.

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

- List of Figures
- Preface

**Overview**- Introduction
- Models of Computation
- Forms of Input
- Problems
- Data Movement Operations
- Sample Algorithms
- Further Remarks

**Fundamental Mesh Algorithms**- Introduction
- Definitions
- Lower Bounds
- Primitive Mesh Algorithms
- Matrix Algorithms
- Algorithms Involving Ordered Data
- Further Remarks

**Mesh Algorithms**- Introduction
- Fundamental Graph Algorithms
- Connected Components
- Internal Distances
- Convexity
- External Distances
- Further Remarks

**Mesh Algorithms for Computational Geometry**- Introduction
- Preliminaries
- The Convex Hull
- Smallest Enclosing Figures
- Nearest Point Problems
- Line Segments and Simple Polygons
- Intersection of Convex Sets
- Diameter
- Iso-oriented Rectangles and Polygons
- Voronoi Diagram
- Further Remarks

**Tree-like Pyramid Algorithms**- Introduction
- Definitions
- Lower Bounds
- Fundamental Algorithms
- Image Algorithms
- Further Remarks

**Hybrid Pyramid Algorithms**- Introduction
- Graphs as Unordered Edges
- Graphs as Adjacency Matrices
- Digitized Pictures
- Convexity
- Data Movement Operations
- Optimality
- Further Remarks

**Order Notation****Recurrence Equations****Bibliography**

MIT Press, September 1996 | Order online
from MIT Press |

ISBN 0-262-13233-8 | Order online
from Amazon/Borders |

336 pp. -- 60 illus. | $40.00 (US) (cloth) |

Russ Miller (miller@cse.buffalo.edu)