REVIEW - Parallel Algorithms for Regular Architectures - Meshes and Pyramids


Parallel Algorithms for Regular Architectures - Meshes and Pyramids


Russ Miller, Quentin F. Stout




MIT Press (1996)




Brian Bramer


April 1998


2 out of 5

Although sequential computer systems are becoming more powerful the problems to be solved are becoming more complex. Consider multimedia systems requiring real-time video compression/decom- pression, image manipulation, etc. There is great research activity in the areas of parallel computation from new hardware configurations (e.g. chips containing custom ASIC and RISC and DSP processors) to algorithms and their implementation.

This text considers the implementation of efficient algorithms to solve problems on sets of parallel processors arranged in mesh or pyramid configurations. It starts with an introductory chapter defining basic terms and considering how to design machine independent parallel algorithms in terms of abstract data movements (analogous to designing for sequential machines using ADTs). There are then three chapters on the mesh configuration presenting algorithms for matrix multiplication, transitive closure, sorting, graphs and image processing, etc. Two chapters follow on the pyramid configuration, discussing algorithms for solving complex problems for applications such as graphs and images.

A research monograph which would be required reading for researchers (algorithm designers through to hardware or software designers) working in the area of parallel computing. For example, although my own area of research is parallel DSPs and FPGAs many of the concepts discussed in this book are very relevant. Also useful as a text for final year undergraduate or postgraduate modules in parallel computing, parallel architectures, parallel algorithms and as supplementary reading for modules on image processing, multimedia systems (I don't mean writing web pages!), digital signal processing, etc.

Book cover image courtesy of Open Library.