Table of Contents

Chapter 1 The Concurrent Computing Landscape

1.1 The Essence of Concurrent Programming
1.2 Hardware Architectures

Single Processor Machines
Shared-Memory Multiprocessors
Multicomputers Networks
1.3 Applications and Programming Styles
1.4 Iterative Parallelism: Matrix Multiplication
1.5 Recursive Parallelism: Adaptive Quadrature
1.6 Producers and Consumers: Unix Pipes
1.7 Clients and Servers: Remote Files
1.8 Peers: Distributed Matrix Multiplication
1.9 Summary of Programming Notation
Declarations Sequential Statements
Concurrent Statements and Process Declarations
Comments

PART I: Shared Variable Programming

Chapter 2 Processes and Synchronization

2.1 States, Actions, Histories, and Properties
2.2 Parallelization: Finding Patterns in Files
2.3 Synchronization: The Maximum of an Array
2.4 Atomic Actions and Await Statements

Fine-Grained Atomicity
Specifying Synchronization: The Await Statement
2.5 Finding Patterns in a File Revisited
2.6 A Synopsis of Axiomatic Semantics
Formal Logical Systems
A Programming Logic
Semantics of Concurrent Execution
2.7 Techniques for Avoiding Interference
Disjoint Variables Weakened Assertions
Global Invariants
Synchronization
An Example: The Array Copy Problem Revisited
2.8 Safety and Liveness Properties
Proving Safety Properties
Scheduling Policies and Fairness

Chapter 3 Locks and Barriers

3.1 The Critical Section Problem
3.2 Critical Sections: Spin Locks

Test and Set
Test and Test and Set
Implementing Await Statements
3.3 Critical Sections: Fair Solutions
The Tie-Breaker Algorithm
The Ticket Algorithm
The Bakery Algorithm
3.4 Barrier Synchronization
Shared Counter
Flags and Coordinators
Symmetric Barriers
3.5 Data Parallel Algorithms
Parallel Prefix Computations
Operations on Linked Lists
Grid Computations: Laplace's Equation
Synchronous Multiprocessors
3.6 Parallel Computing with a Bag of Tasks
Matrix Multiplication
Adaptive Quadrature

Chapter 4 Semaphores

4.1 Syntax and Semantics
4.2 Basic Problems and Techniques

Critical Sections: Mutual Exclusion
Barriers: Signaling Events
Producers and Consumers: Split Binary Semaphores
Bounded Buffers: Resource Counting
4.3 The Dining Philosophers
4.4 Readers and Writers
Readers/Writers as an Exclusion Problem
Readers/Writers Using Condition Synchronization
The Technique of Passing the Baton
Alternative Scheduling Policies
4.5 Resource Allocation and Scheduling
Problem Definition and General Solution Pattern
Shortest-Job-Next Allocation
4.6 Case Study: Pthreads
Thread Creation
Semaphores
Example: A Simple Producer and Consumer

Chapter 5 Monitors

5.1 Syntax and Semantics

Mutual Exclusion
Condition Variables
Signaling Disciplines
Additional Operations on Condition Variables
5.2 Synchronization Techniques
Bounded Buffers: Basic Condition Synchronization
Readers and Writers: Broadcast Signal
Shortest-Job-Next Allocation: Priority Wait
Interval Timer: Covering Conditions
The Sleeping Barber: Rendezvous
5.3 Disk Scheduling: Program Structures
Scheduler as a Separate Monitor
Scheduler as an Intermediary
Scheduler as a Nested Monitor
5.4 Case Study: Java
The Threads Class
Synchronized Methods
Parallel Readers/Writers
Exclusive Readers/Writers
True Readers/Writers
5.5 Case Study: Pthreads
Locks and Condition Variables
Example: Summing the Elements of a Matrix

Chapter 6 Implementations

6.1 A Single-Processor Kernel
6.2 A Multiprocessor Kernel
6.3 Implementing Semaphores in a Kernel
6.4 Implementing Monitors in a Kernel
6.5 Implementing Monitors Using Semaphores

PART II: Distributed Programming

Chapter 7 Message Passing

7.1 Asynchronous Message Passing
7.2 Filters: A Sorting Network
7.3 Clients and Servers

Active Monitors
A Self-Scheduling Disk Driver
File Servers: Conversational Continuity
7.4 Interacting Peers: Exchanging Values
7.5 Synchronous Message Passing
7.6 Case Study: CSP
Communication Statements
Guarded Communication
Example: The Sieve of Eratosthenes
7.7 Case Study: Linda
Tuple Space and Process Interaction
Example: Prime Numbers with a Bag of Tasks
7.8 Case Study: MPI
Basic Functions
Global Communication and Synchronization
7.9 Case Study: Java
Networks and Sockets
Example: A Remote File Reader

Chapter 8 RPC and Rendezvous

8.1 Remote Procedure Call

Synchronization in Modules
A Time Server Caches in a Distributed File System
A Sorting Network of Merge Filters
Interacting Peers: Exchanging Values
8.2 Rendezvous
Input Statements
Client/Server Examples
A Sorting Network of Merge Filters
Interacting Peers: Exchanging Values
8.3 A Multiple Primitives Notation
Invoking and Servicing Operations
Examples
8.4 Readers/Writers Revisited
Encapsulated Access
Replicated Files
8.5 Case Study: Java
Remote Method Invocation
Example: A Remote Database
8.6 Case Study: Ada
Tasks
Rendezvous
Protected Types
Example: The Dining Philosophers
8.7 Case Study: SR
Resources and Globals
Communication and Synchronization
Example: Critical Section Simulation

Chapter 9 Paradigms for Process Interaction

9.1 Managers/Workers (Distributed Bag of Tasks)

Sparse Matrix Multiplication
Adaptive Quadrature Revisited
9.2 Heartbeat Algorithms
Image Processing: Region Labeling
Cellular Automata: The Game of Life
9.3 Pipeline Algorithms
A Distributed Matrix Multiplication Pipeline
Matrix Multiplication by Blocks
9.3 Probe/Echo Algorithms
Broadcast in a Network
Computing the Topology of a Network
9.4 Broadcast Algorithms
Logical Clocks and Event Ordering
Distributed Semaphores
9.5 Token-Passing Algorithms
Distributed Mutual Exclusion
Termination Detection in a Ring
Termination Detection in a Graph
9.6 Replicated Servers
Distributed Dining Philosophers
Decentralized Dining Philosophers

Chapter 10 Implementations

10.1 Asynchronous Message Passing

Shared-Memory Kernel
Distributed Kernel
10.2 Synchronous Message Passing
Direct Communication Using Asynchronous Messages
Guarded Communication Using a Clearing House
10.3 RPC and Rendezvous
RPC in a Kernel
Rendezvous Using Asynchronous Message Passing
Multiple Primitives in a Kernel
10.4 Distributed Shared Memory
Implementation Overview
Page Consistency Protocols

PART III Parallel Programming:

Speedup and Efficiency
Overheads and Challenges

Chapter 11 Scientific Computing

11.1 Grid Computations

Laplace's Equation
Sequential Jacobi Iteration
Shared Variable Program
Message Passing Program
Red/Black Successive Over Relaxation
Multigrid Methods
11.2 Particle Computations
The Gravitational #N-Body Problem
Shared Variable Program
Message Passing Programs
Approximate Methods
11.3 Matrix Computations
Gaussian Elimination
LU Decomposition
Shared Variable Program
Message Passing Program

Chapter 12 Languages, Compilers, Libraries, and Tools

12.1 Parallel Programming Libraries

Case Study: Pthreads
Case Study: MPI
Case Study: OpenMP
12.2 Parallelizing Compilers
Dependence Analysis
Program Transformations
12.3 Other Programming Models
Imperative Languages
Coordination Languages Data Parallel Languages
Functional Languages
Abstract Models
Case Study: High Performance Fortran (HPF)
12.3 Parallel Programming Tools
Performance Measurement and Visualization
Metacomputers and Metacomputing
Case Study: The Globus Toolkit