Introduction to Parallel Computing

Introduction to Parallel Computing

Ananth Grama Purdue University. (ayg@cs.purdue.edu)
Anshul Gupta IBM T.J. Watson Research Center, (anshul@watson.ibm.com)
George Karypis University of Minnesota. (karypis@cs.umn.edu)
Vipin Kumar, University of Minnesota. (kumar@cs.umn.edu)

Authors Note:

These postscripts are preprint versions of chapters that will appear as a text book published by Addison Wesley. These chapters are not for general distribution and are copyrighted by Addison Wesley.

PART I: BASIC CONCEPTS

1. Introduction

Motivating Parallelism
Scope of Parallel Computing
Organization and Contents of the Text

2. Parallel Programming Platforms

Motivating Parallelism
Implicit Parallelism: Trends in Microprocessor Architectures
Limitations of Memory System Performance
Dichotomy of Parallel Computing Platforms
Communication Model of Parallel Platforms
Physical Organization of Parallel Platforms
Communication Costs in Parallel Machines
Case Studies
Bibliographic Remarks

3. Principles of Parallel Algorithm Design

Introduction to Parallel Algorithm Design
Decomposition Techniques
Characteristics of Tasks and Interactions
Mapping Techniques for Load Balancing
Methods for Containing Interaction Overheads
Parallel Algorithm Models
Bibliographic Remarks

4. Basic Communication Operations

Broadcast Operations
Personalized Communication Operations
Data Shift Operations
Faster Methods for Some Communication Operations
Bibliographic Remarks

5. Analytical Modeling of Parallel Programs

Performance Metrics for Parallel Systems
Effect of Granularity and Data Mapping on Performance
Scalability of Parallel Systems
Minimum Execution Time and Minimum Cost-Optimal Execution Time
Bibliographic Remarks

PART II: PARALLEL PROGRAMMING

6. Programming Shared Address Space Platforms

Thread Basics
Why Threads?
The POSIX Thread Application Programmer Interface
Synchronization Primitives in POSIX
Controlling Thread and Synchronization Attributes
Composite Synchronization Constructs
Tips for Designing Asynchronous Programs
OpenMP: A Standard for Directive Based Parallel Programming
Bibliographic Remarks

7. Programming Message Passing Platforms

Message Passing Interface (MPI) Basics
Topologies and Embedding
Overlapping Communication with Computation
Collective Communication and Computation Operations
Groups and Communicators
Static Distributions: Block, Cyclic, and Block-Cyclic
Unstructured Communication
Bibliographic Remarks

PART III: PARALLEL ALGORITHMS AND APPLICATIONS

8. Dense Matrix Algorithms

Mapping Matrices onto Processors
Matrix Transposition
Matrix-Vector Multiplication
Matrix Multiplication
Solving a System of Linear Equations
Bibliographic Remarks

Issues in Sorting on Parallel Computers
Sorting Networks
Bubble Sort and its Variants
Quicksort
Other Sorting Algorithms
Bibliographic Remarks

10. Graph Algorithms

Definitions and Representation
Minimum Spanning Tree: Prim's Algorithm
Single-Source Shortest Paths: Dijkstra's Algorithm
All-Pairs Shortest Paths
Transitive Closure
Connected Components
Algorithms for Sparse Graphs
Bibliographic Remarks

11. Discrete Optimization Problems

Definitions and Examples
Sequential Search Algorithms
Search Overhead Factor
Parallel Depth-First Search
Parallel Best-First Search
Speedup Anomalies in Parallel Search Algorithms
Bibliographic Remarks

12. Dynamic Programming

Serial Monadic DP Formulations
Nonserial Monadic DP Formulations
Serial Polyadic DP Formulations
Nonserial Polyadic DP Formulations
Summary and Discussion
Bibliographic Remarks

13. Fast Fourier Transform

The Serial Algorithm
The Binary-Exchange Algorithm
The Transpose Algorithm
Cost-Effectiveness of Parallel FFT Algorithms
Bibliographic Remarks