多線程、并行與分布式程序設計基礎（影印版）

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