Miller R. Parallel Algorithms for Regular Architectures. Meshes and Pyramids

MIT Press, 1996. — 238 p.This book is designed for a variety of purposes. As a research monograph, it should be of interest to researchers and practitioners working in the field of parallel computing. It may be used as a text in a graduate course on Parallel Algorithms, as a supplementary text in an undergraduate course on Parallel Algorithms, or as a supplementary text in a course on Analysis of Algorithms, Parallel Computing, Parallel Architectures, Computer Architectures, or VLSI arrays. It is also appropriate to use this book as a supplementary text in an advanced graduate course on Vision, Image Analysis, or Computational Geometry. Excerpts from preliminary versions of this book have been used successfully in senior undergraduate and first year graduate courses on Analysis of Algorithms, advanced graduate courses on Parallel Algorithms, graduate level seminars on Computational Geometry and Parallel Computing, and a first year graduate course on Computer Architecture.
The focus of this book is on developing optimal algorithms to solve problems on sets of processors configured as a mesh or pyramid. Basic algorithms, such as sorting, matrix multiplication, and parallel prefix, are developed, as are algorithms to solve fundamental problems in image processing, computational geometry, and graph theory. The book integrates and synthesizes material from the literature with new concepts, algorithms, and paradigms. The reader has the opportunity to gain insight into developing efficient parallel algorithms by following the design process presented by the authors, who originally developed the vast majority of the algorithms that are presented.OverviewFundamental Mesh Algorithms
Mesh Algorithms for Images and Graphs
Mesh Algorithms for Computational Geometry
Tree-like Pyramid Algorithms
Hybrid Pyramid Algorithms
A: Order Notation
B: Recurrence Equations