Multithreaded, Parallel, and Distributed Programming: 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