Parallel Algorithms for Regular Architectures

Meshes and Pyramids

by Russ Miller and Quentin F. Stout

Description

Parallel Algorithms for Regular Architectures offers an extensive collection of optimal and efficient algorithms for solving problems on sets of processors configured as a mesh or a pyramid. In addition, it provides valuable insights into the parallel algorithm design process.

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.

Some Comments from Reviewers

From Computing Reviews, October 1997, review by D. M. Bowen:
... 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
    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

Cover Illustration

Here is what the cover looks like. It is hard to make out, but the structure depicted is a pyramid computer.

Ordering Information

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)