Synthesis of Parallel Algorithms

This landmark collaboration will enhance the knowledge and abilities of anyone interested in parallel algorithms and in developing programs for parallel computers. Many problems currently solved with sequential algorithms are themselves highly parallelizable when designers use the powerful parallel techniques now available. These thorough but introductory presentations demonstrate the most important algorithmic techniques and their use in exposing the hidden parallelism within problems. Beginning with familiar sequential algorithms, the authors provide a careful description of the fundamental problem, its solution, and analysis--complete with examples and exercises. Each of the 22 chapters then synthesizes a more sophisticated parallel algorithm using the simpler sequential and parallel techniques used to introduce the problem. The PRAM shared-memory model of computing provides a unifying framework. This model has been used extensively for designing parallel algorithms and can be efficiently simulated on many of the parallel architectures now in use. Applying the methods in this book will offer designers a substantial advantage when solving problems for parallel computation.