Cover image for Foundations of multithreaded, parallel, and distributed programming
Foundations of multithreaded, parallel, and distributed programming
Andrews, Gregory R.
Personal Author:
Publication Information:
Reading, Mass. : Addison-Wesley, [2000]

Physical Description:
xx, 664 pages : illustrations ; 24 cm
Format :


Call Number
Material Type
Home Location
Item Holds
QA76.58 .A57 2000 Adult Non-Fiction Central Closed Stacks

On Order



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

Author Notes

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.


Table of Contents

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
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
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 al.gorithm
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
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 Proc