Foundations of Multithreaded, Parallel, and Distributed Programming

✍ Scribed by Gregory R. Andrews

• Publisher: Pearson
• Year: 1999
• Tongue: English
• Leaves: 690
• Edition: 1
• Category: Library

✦ Synopsis

Greg Andrews teaches the fundamental concepts of multithreaded, parallel and distributed computing and relates them to the implementation and performance processes. He presents the appropriate breadth of topics and supports these discussions with an emphasis on performance. Features Emphasizes how to solve problems, with correctness the primary concern and performance an important, but secondary, concern Includes a number of case studies which cover such topics as pthreads, MPI, and OpenMP libraries, as well as programming languages like Java, Ada, high performance Fortran, Linda, Occam, and SR Provides examples using Java syntax and discusses how Java deals with monitors, sockets, and remote method invocation Covers current programming techniques such as semaphores, locks, barriers, monitors, message passing, and remote invocation Concrete examples are executed with complete programs, both shared and distributed Sample applications include scientific computing and distributed systems

✦ Table of Contents

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-VariableProgramming
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 Problem Revisited
2.8 Safety and Liveness Properties
2.8.1 Proving Safety Properties
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 Synchronization
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 Thread 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 Synchronization Techniques
5.2.1 Bounded Buffers: Basic Condition Synchronization
5.2.2 Readers 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 Readers/Writers
5.4.4 Exclusive Readers/Writers
5.4.5 True Readers/Writers
5.5 Case Study: Pthreads
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 Interacting Peers: Exchanging Values
7.5 Synchronous Message Passing
7.6 Case Study: CSP
7.6.1 Communication 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 Communication 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 Procedure 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 Interacting Peers: Exchanging Values
8.3 A Multiple Primitives Notation
8.3.1 Invoking and Servicing Operations
8.3.2 Examples
8.4 ReadersA/Vriters 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 Communication and Synchronization
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: Implementations
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: Parallel 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 Tools
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 Languages 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