Casanova / Legrand / Robert Parallel Algorithms

1. Auflage 2011
ISBN: 978-1-58488-946-5
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 360 Seiten

Reihe: Chapman & Hall/CRC Numerical Analysis and Scientific Computing Series

Focusing on algorithms for distributed-memory parallel architectures, Parallel Algorithms presents a rigorous yet accessible treatment of theoretical models of parallel computation, parallel algorithm design for homogeneous and heterogeneous platforms, complexity and performance analysis, and essential notions of scheduling. The book extracts fundamental ideas and algorithmic principles from the mass of parallel algorithm expertise and practical implementations developed over the last few decades. In the first section of the text, the authors cover two classical theoretical models of parallel computation (PRAMs and sorting networks), describe network models for topology and performance, and define several classical communication primitives. The next part deals with parallel algorithms on ring and grid logical topologies as well as the issue of load balancing on heterogeneous computing platforms. The final section presents basic results and approaches for common scheduling problems that arise when developing parallel algorithms. It also discusses advanced scheduling topics, such as divisible load scheduling and steady-state scheduling. With numerous examples and exercises in each chapter, this text encompasses both the theoretical foundations of parallel algorithms and practical parallel algorithm design.

Zielgruppe

Advanced undergraduate and graduate students taking parallel algorithm courses; computer scientists, electrical engineers, and applied mathematicians.

Autoren/Hrsg.

Casanova, Henri

Legrand, Arnaud

Robert, Yves

Fachgebiete

• Mathematik | Informatik Mathematik Mathematik Allgemein Zahlensysteme
• Mathematik | Informatik EDV | Informatik EDV & Informatik Allgemein

Inhaltsverzeichnis

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(8)

Solving Pb(p)

Taking Communication Costs into Account

Pb(8) 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.