Parallel Algorithms

ISBN-13: 9781584889458 / Angielski / Twarda / 2008 / 360 str.

Henri Casanova; Armand Legrand; Yves Robert

Opis

Focusing on algorithms for distributed-memory parallel architectures, this book covers theoretical models of parallel computation, parallel algorithm design for homogeneous and heterogeneous platforms, complexity and performance analysis, and essential notions of scheduling.

Spis treści

Preface
Models
PRAM Model
Pointer Jumping
Performance Evaluation of PRAM Algorithms
Comparison of PRAM Models
Sorting Machine
Relevance of the PRAM Model
Sorting Networks
Odd-Even Merge Sort
Sorting on a One-Dimensional Network
Networking
Interconnection Networks
Communication Model
Case Study: The Unidirectional Ring
Case Study: The Hypercube
Peer-to-Peer Computing
Parallel Algorithms
Algorithms on a Ring of Processors
Matrix-Vector Multiplication
Matrix-Matrix Multiplication
A First Look at Stencil Applications
LU Factorization
A Second Look at Stencil Applications
Implementing Logical Topologies
Distributed vs. Centralized Implementations
Summary of Algorithmic Principles
Algorithms on Grids of Processors
Logical Two-Dimensional Grid Topologies
Communication on a Grid of Processors
Matrix Multiplication on a Grid of Processors
Two-Dimensional Block Cyclic Data Distribution
Load Balancing on Heterogeneous Platforms
Load Balancing for One-Dimensional Data Distributions
Load Balancing for Two-Dimensional Data Distributions
Free Two-Dimensional Partitioning on a Heterogeneous Grid
Scheduling
Scheduling
Introduction
Scheduling Task Graphs
Solving Pb(∞)
Solving Pb(p)
Taking Communication Costs into Account
Pb(∞) with Communications
List Heuristics for Pb(p) with Communications
Extension to Heterogeneous Platforms
Advanced Scheduling
Divisible Load Scheduling
Steady-State Scheduling
Workflow Scheduling
Hyperplane Scheduling (or Scheduling at Compile-Time)
Bibliography
Index
Exercises and Answers appear at the end of each chapter.

O autorze

Henri Casanova, Arnaud Legran, Yves Robert