多线程、并行与分布式程序设计基础（影印版）

Preface

Chapter 1: The Concurrent Computing Landscape

1.1 The Essence of Concurrent Programming

1.2 Hardware Architectures

1.2.1 Processors and Caches

1.2.2 Shared-Memory Multiprocessors

1.2.3 Distributed-Memory Multicomputers and 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: File Systems

1.8 Peers: Distributed Matrix Multiplication

1.9 Summary of Programming Notation

1.9.1 Declarations

1.9.2 Sequential Statements

1.9.3 Concurrent Statements, Processes, and Procedures

1.9.4 Comments

Historical Notes

References

Exercises

Part 1: Shared-Variable Programming

Chapter 2: Processes and Synchronization

2.1 States, Actions, Histories, and Properties

2.2 Parallelization: Finding Patterns in a File

2.3 Synchronization: The Maximum of an Array

2.4 Atomic Actions and Await Statements

2.4.1 Fine-Grained Atomicity

2.4.2 Specifying Synchronization: The Await Statement

2.5 Producer/Consumer Synchronization

2.6 A Synopsis of Axiomatic Semantics

2.6.1 Formal Logical Systems

2.6.2 A Programming Logic

2.6.3 Semantics of Concurrent Execution

2.7 Techniques for Avoiding Interference

2.7.1 Disjoint Variables

2.7.2 Weakened Assertions

2.7.3 Global Invariants

2.7.4 Synchronization

2.7.5 An Example: The Array Copy ProbIem Revisited

2.8 Safety and Liveness Properties

2.8.1 Proving Safety Propertes

2.8.2 Scheduling Policies and Fairness

Historical Notes

References

Exercises

Chapter 3: Locks and Barriers

3.1 The Critical Section Problem

3.2 Critical Sections: Spin Locks

3.2.1 Test and Set

3.2.2 Test and Test and Set

3.2.3 Implementing Await Statements

3.3 Critical Sections: Fair Solutions

3.3.1 The Tie-Breaker Algorithm

3.3.2 The Ticket Algorithm

3.3.3 The Bakery Algorithm

3.4 Barrier Synchronization

3.4.1 Shared Counter

3.4.2 Flags and Coordinators

3.4.3 Symmetric Barriers

3.5 Data Parallel Algorithms

3.5.1 Parallel Prefix Computations

3.5.2 Operations on Linked Lists

3.5.3 Grid Computations: Jacobi Iteration

3.5.4 Synchronous Multiprocessors

3.6 Parallel Computing with a Bag of Tasks

3.6.1 Matrix Multiplication

3.6.2 Adaptive Quadrature

Historical Notes

References

Exercises

Chapter 4: Semaphores

4.1 Syntax and Semantics

4.2 Basic Problems and Techniques

4.2.1 Critical Sections' Mutual Exclusion

4.2.2 Barriers: Signaling Events

4.2.3 Producers and Consumers: Split Binary Semaphores

4.2.4 Bounded Buffers: Resource Counting

4.3 The Dining Philosophers

4.4 Readers and Writers

4.4.1 Readers/Writers as an Exclusion Problem

4.4.2 Readers/Writers Using Condition Synchrnization

4.4.3 The Technique of Passing the Baton

4.4.4 Alternative Scheduling Policies

4.5 Resource Allocation and Scheduling

4.5.1 Problem Definition and General Solution Pattern

4.5.2 Shortest-Job-Next Allocation

4.6 Case Study: Pthreads

4.6.1 Wad Creation

4.6.2 Semaphores

4.6.3 Example: A Simple Producer and Consumer

Historical Notes

References

Exercises

Chapter 5: Monitors

5.1 Syntax and Semantics

5.1.1 Mutual Exclusion

5.1.2 Condition Variables

5.1.3 Signaling Disciplines

5.1.4 Additional Operations on Condition Variables

5.2 Synchroulzation Techniques

5.2.1 Bounded Buffers: Basic Condition Synchronization

5.2.2 Reades and Writers: Broadcast Signal

5.2.3 Shortest-Job-Next Allocation: Priority Wait

5.2.4 Interval Timer: Covering Conditions

5.2.5 The Sleeping Barber: Rendezvous

5.3 Disk Scheduling: Program Structures

5.3.1 Using a Separate Monitor

5.3.2 Using an Intermediary

5.3.3 Using a Nested Monitor

5.4 Case Study: Java

5.4.1 The Threads Class

5.4.2 Synchronized Methods

5.4.3 Parallel Reades/Writers

5.4.4 Exclusive Reades/Writers

5.4.5 True Readers/Writers

5.5 Case Study: Pthrads

5.5.1 Locks and Condition Variables

5.5.2 Example: Summing the Elements of a Matrix

Historical Notes

References

Exercises

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

Historical Notes

References

Exercises

Part 2: Distributed Programming

Chapter 7: Message Passing

7.1 Asynchronous Message Passing

7.2 Filters' A Sorting Network

7.3 Clients and Servers

7.3.1 Active Monitors

7.3.2 A Self Scheduling Disk Server

7.3.3 File Servers: Conversational Continuity

7.4 Interating Peers: Exchanging VaIues

7.5 Synchronous Message Passing

7.6 Case Study: CSP

7.6.1 Cornmunication Statements

7.6.2 Guarded Communication

7.6.3 Example: The Sieve of Eratosthenes

7.6.4 Occam and Modern CSP

7.7 Case Study: Linda

7.7.1 Tuple Space and Process Interaction

7.7.2 Example: Prime Numbers with a Bag of Tasks

7.8 Case Study: MPI

7.8.1 Basic Functions

7.8.2 Global Commnication and Synchronization

7.9 Case Study: Java

7.9.1 Networks and Sockets

7.9.2 Example: A Remote File Reader

Historical Notes

References

Exercises

Chapter 8: RPC and Rendezvous

8.1 Remote Procedur Call

8.1.1 Synchronization in Modules

8.1.2 A Time Server

8.1.3 Caches in a Distributed File System

8.1.4 A Sorting Network of Merge Filters

8.1.5 Interacting Peers: Exchanging Values

8.2 Rendezvous

8.2.1 Input Statements

8.2.2 Client/Server Examples

8.2.3 A Sorting Network of Merge Filters

8.2.4 Interachng Peers: Exchanging Values

8.3 A Multiple Primitives Notation

8.3.1 Invoking and Servicing Operations

8.3.2 Examples

8.4 Readers/Writers Revisited

8.4.1 Encapsulated Access

8.4.2 Replicated Files

8.5 Case Study: Java

8.5.1 Remote Method Invocation

8.5.2 Example: A Remote Database

8.6 Case Study: Ada

8.6.1 Tasks

8.6.2 Rendezvous

8.6.3 Protected Types

8.6.4 Example: The Dining Philosophers

8.7 Case Study: SR

8.7.1 Resources and Globals

8.7.2 Commnication and Synchroinzation

8.7.3 Example' Critical Section Simulation

Historical Notes

References

Exercises

Chapter 9: Paradigms for Process Interaction

9.1 Manager/Workers (Distributed Bag of Tasks)

9.1.1 Sparse Matrix Multiplication

9.1.2 Adaptive Quadrature Revisited

9.2 Heartbeat Algorithms

9.2.1 Image Processing: Region Labeling

9.2.2 Cellular Automata: The Game of Life

9.3 Pipeline Algorithms

9.3.1 A Distributed Matrix Multiplication Pipeline

9.3.2 Matrix Multiplication by Blocks

9.4 Probe/Echo Algorithms

9.4.1 Broadcast in a Network

9.4.2 Computing the Topology of a Network

9.5 Broadcast Algorithms

9.5.1 Logical Clocks and Event Ordering

9.5.2 Distributed Semaphores

9.6 Token-Passing Algorithms

9.6.1 Distributed Mutual Exclusion

9.6.2 Termination Detection in a Ring

9.6.3 Termination Detection in a Graph

9.7 Replicated Servers

9.7.1 Distributed Dining Philosophers

9.7.2 Decentralized Dining Philosophers

Historical Notes

References

Exercises

Chapter 10: lmpIementations

10.1 Asynchronous Message Passing

10.1.1 Shared-Memory Kernel

10.1.2 Distributed Kernel

10.2 Synchronous Message Passing

10.2.1 Direct Communication Using Asynchronous Messages

10.2.2 Guarded Communication Using a Clearinghouse

10.3 RPC and Rendezvous

10.3.1 RPC in a Kernel

10.3.2 Rendezvous Using Asynchronous Message Passing

10.3.3 Multiple Primitives in a Kernel

10.4 Distributed Shared Memory

10.4.1 Implementation Overview

10.4.2 Page Consistency Protocols

Historical Notes

References

Exercises

Part 3: ParalleI Programming

Chapter 11: Scientific Computing

11.1 Grid Computations

11.1.1 Laplace's Equation

11.1.2 Sequential Jacobi Iteration

11.1.3 Jacobi Iteration Using Shared Variables

11.1.4 Jacobi Iteration Using Message Passing

11.1.5 Red/Black Successive Over-Relaxation (SOR)

11.1.6 Multigrid Methods

11.2 Particle Computations

11.2.1 The Gravitational N-Body Problem

11.2.2 Shared-Variable Program

11.2.3 Message-Passing Programs

11.2.4 Approximate Methods

11.3 Matrix Computations

11.3.1 Gaussian Elimination

11.3.2 LU Decomposition

11.3.3 Shared-Variable Program

11.3.4 Message-Passing Program

Historical Notes

References

Exercises

Chapter 12: Languages, Compilers,Libraries, and TooIs

12.1 Parallel Programming Libraries

12.1.1 Case Study: Pthreads

12.1.2 Case Study' MPI

12.1.3 Case Study: OpenMP

12.2 Parallelizing Compilers

12.2.1 Dependence Analysis

12.2.2 Program Transformations

12.3 Languagps and Models

12.3.1 Imperative Languages

12.3.2 Coordination Languages

12.3.3 Data Parallel Languages

12.3.4 Functional Languages

12.3.5 Abstract Models

12.3.6 Case Study: High-Performance Fortran (HPF)

12.4 Parallel Programming Tools

12.4.1 Performance Measurement and Visualization

12.4.2 Metacomputers and Metacomputing

12.4.3 Case Study: The Globus Toolkit

Historical Notes

References

Exercises

Glossary

Index