Parallel Algorithms, which focuses on algorithms for distributed-memory parallel architectures, provides a thorough yet approachable treatment of theoretical models of parallel computation, parallel algorithm design for homogeneous and heterogeneous platforms, complexity and performance analysis, and fundamental scheduling concepts.
From the wealth of knowledge and practical implementations of parallel algorithms that have been generated over the past few decades, the book distills essential concepts and algorithmic principles.
The authors discuss two traditional theoretical models of parallel computation (PRAMs and sorting networks), provide network models for topology and performance, and define a number of traditional communication primitives in the first section of the paper.
The following section addresses load balancing on heterogeneous computing systems as well as parallel methods on ring and grid logical topologies.
The final section provides fundamental findings and solutions for typical scheduling issues that occur when creating parallel algorithms. Additionally, it covers more complex scheduling subjects including steady-state scheduling and scheduling with divisible loads.
This text covers both the theoretical underpinnings of parallel algorithms and actual parallel algorithm design, with several examples and exercises in each chapter.