Foundations of Multithreaded, Parallel, and Distributed Programming

Gregory Andrews received a B.S. degree in Mathematics from Stanford University in 1969 and a Ph.D. degree in Computer Science from the University of Washington in 1974. From 1974-79 he was an Assistant Professor at Cornell University. Since 1979 he has been at The University of Arizona, where he is currently Professor of Computer Science. From 1986-93 he chaired the department; in 1986 he received a distinguished teaching award. Greg has been on the editorial board of Information Processing Letters since 1979. He was the general chair of the Twelfth ACM Symposium on Operating Systems Principles in 1989 and has been on the program committees of numerous conferences. From 1988-92 he was on advisory committees for the computing directorate of the National Science Foundation. Since 1991 he has been on the Board of Directors of the Computing Research Association (CRA). Greg's research interests include all aspects of concurrent programming. A long-term project has been the design and implementation of the SR programming language. Current work focuses on the development of Filaments, a software package that provides efficient fine-grain parallelism on a variety of parallel machines. 0201357526AB04062001

• 1. The Concurrent Computing Landscape. The Essence of Concurrent Programming. Hardware Architectures. Single Processor Machines. Shared-Memory Multiprocessors. Multicomputers Networks. Applications and Programming Styles. Iterative Parallelism: Matrix Multiplication. Recursive Parallelism: Adaptive Quadrature. Producers and Consumers: Unix Pipes. Clients and Servers: Remote Files. Peers: Distributed Matrix Multiplication. Summary of Programming Notation. Declarations Sequential Statements. Concurrent Statements and Process Declarations. Comments. I. SHARED VARIABLE PROGRAMMING. 2. Processes and Synchronization. States, Actions, Histories, and Properties. Parallelization: Finding Patterns in Files. Synchronization: The Maximum of an Array. Atomic Actions and Await Statements. Fine-Grained Atomicity. Specifying Synchronization: The Await Statement. Finding Patterns in a File Revisited. A Synopsis of Axiomatic Semantics. Formal Logical Systems. A Programming Logic. Semantics of Concurrent Execution. Techniques for Avoiding Interference. Disjoint Variables Weakened Assertions. Global Invariants. Synchronization. An Example: The Array Copy Problem Revisited. Safety and Liveness Properties. Proving Safety Properties. Scheduling Policies and Fairness. 3. Locks and Barriers. The Critical Section Problem. Critical Sections: Spin Locks. Test and Set. Test and Test and Set. Implementing Await Statements. Critical Sections: Fair Solutions. The Tie-Breaker Algorithm. The Ticket Algorithm. The Bakery Algorithm. Barrier Synchronization. Shared Counter. Flags and Coordinators. Symmetric Barriers. Data Parallel Algorithms. Parallel Prefix Computations. Operations on Linked Lists. Grid Computations: Laplace's Equation. Synchronous Multiprocessors. Parallel Computing with a Bag of Tasks. Matrix Multiplication. Adaptive Quadrature. 4. Semaphores. Syntax and Semantics. Basic Problems and Techniques. Critical Sections: Mutual Exclusion. Barriers: Signaling Events. Producers and Consumers: Split Binary Semaphores. Bounded Buffers: Resource Counting. The Dining Philosophers. Readers and Writers. Readers/Writers as an Exclusion Problem. Readers/Writers Using Condition Synchronization. The Technique of Passing the Baton. Alternative Scheduling Policies. Resource Allocation and Scheduling. Problem Definition and General Solution Pattern. Shortest-Job-Next Allocation. Case Study: Pthreads. Thread Creation. Semaphores. Example: A Simple Producer and Consumer. 5. Monitors. Syntax and Semantics. Mutual Exclusion. Condition Variables. Signaling Disciplines. Additional Operations on Condition Variables. 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. Disk Scheduling: Program Structures. Scheduler as a Separate Monitor. Scheduler as an Intermediary. Scheduler as a Nested Monitor. Case Study: Java. The Threads Class. Synchronized Methods. Parallel Readers/Writers. Exclusive Readers/Writers. True Readers/Writers. Case Study: Pthreads. Locks and Condition Variables. Example: Summing the Elements of a Matrix. 6. Implementations. A Single-Processor Kernel. A Multiprocessor Kernel. Implementing Semaphores in a Kernel. Implementing Monitors in a Kernel. Implementing Monitors Using Semaphores. II. DISTRIBUTED PROGRAMMING. 7. Message Passing. Asynchronous Message Passing. Filters: A Sorting Network. Clients and Servers. Active Monitors. A Self-Scheduling Disk Driver. File Servers: Conversational Continuity. Interacting Peers: Exchanging Values. Synchronous Message Passing. Case Study: CSP. Communication Statements. Guarded Communication. Example: The Sieve of Eratosthenes. Case Study: Linda. Tuple Space and Process Interaction. Example: Prime Numbers with a Bag of Tasks. Case Study: MPI. Basic Functions. Global Communication and Synchronization. Case Study: Java. Networks and Sockets. Example: A Remote File Reader. 8. RPC and Rendezvous. 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. Rendezvous. Input Statements. Client/Server Examples. A Sorting Network of Merge Filters. Interacting Peers: Exchanging Values. A Multiple Primitives Notation. Invoking and Servicing Operations. Examples. Readers/Writers Revisited. Encapsulated Access. Replicated Files. Case Study: Java. Remote Method Invocation. Example: A Remote Database. Case Study: Ada. Tasks. Rendezvous. Protected Types. Example: The Dining Philosophers. Case Study: SR. Resources and Globals. Communication and Synchronization. Example: Critical Section Simulation. 9. Paradigms for Process Interaction. Managers/Workers (Distributed Bag of Tasks). Sparse Matrix Multiplication. Adaptive Quadrature Revisited. Heartbeat Algorithms. Image Processing: Region Labeling. Cellular Automata: The Game of Life. Pipeline Algorithms. A Distributed Matrix Multiplication Pipeline. Matrix Multiplication by Blocks. Probe/Echo Algorithms. Broadcast in a Network. Computing the Topology of a Network. Broadcast Algorithms. Logical Clocks and Event Ordering. Distributed Semaphores. Token-Passing Algorithms. Distributed Mutual Exclusion. Termination Detection in a Ring. Termination Detection in a Graph. Replicated Servers. Distributed Dining Philosophers. Decentralized Dining Philosophers. 10. Implementations. Asynchronous Message Passing. Shared-Memory Kernel. Distributed Kernel. Synchronous Message Passing. Direct Communication Using Asynchronous Messages. Guarded Communication Using a Clearing House. RPC and Rendezvous. RPC in a Kernel. Rendezvous Using Asynchronous Message Passing. Multiple Primitives in a Kernel. Distributed Shared Memory. Implementation Overview. Page Consistency Protocols. III. PARALLEL PROGRAMMING: Speedup and Efficiency. Overheads and Challenges. 11. Scientific Computing. Grid Computations. Laplace's Equation. Sequential Jacobi Iteration. Shared Variable Program. Message Passing Program. Red/Black Successive Over Relaxation. Multigrid Methods. Particle Computations. The Gravitational #N-Body Problem. Shared Variable Program. Message Passing Programs. Approximate Methods. Matrix Computations. Gaussian Elimination. LU Decomposition. Shared Variable Program. Message Passing Program. 12. Languages, Compilers, Libraries, and Tools. Parallel Programming Libraries. Case Study: Pthreads. Case Study: MPI. Case Study: OpenMP. Parallelizing Compilers. Dependence Analysis. Program Transformations. Other Programming Models. Imperative Languages. Coordination Languages Data Parallel Languages. Functional Languages. Abstract Models. Case Study: High Performance Fortran (HPF). Parallel Programming Tools. Performance Measurement and Visualization. Metacomputers and Metacomputing. Case Study: The Globus Toolkit. 0201357526T04062001