Introduction to Parallel Programming
Publisher: Morgan Kaufman Publishers; Morgan Kaufmann
Published: 2011
Number of pages: 370
ISBN-13: 9780123742605
Table of contents: title: Preface
pagenum: xv; title: Acknowledgments
pagenum: xviii; title: About the Author
pagenum: xix; label: Chapter 1
title: Why Parallel Computing?
pagenum: 1; label: 1.1
title: Why We Need Ever-Increasing Performance
pagenum: 2; label: 1.2
title: Why We're Building Parallel Systems
pagenum: 3; label: 1.3
title: Why We Need to Write Parallel Programs
pagenum: 3; label: 1.4
title: How Do We Write Parallel Programs?
pagenum: 6; label: 1.5
title: What We'll Be Doing
pagenum: 8; label: 1.6
title: Concurrent, Parallel, Distributed
pagenum: 9; label: 1.7
title: The Rest of the Book
pagenum: 10; label: 1.8
title: A Word of Warning
pagenum: 10; label: 1.9
title: Typographical Conventions
pagenum: 11; label: 1.10
title: Summary
pagenum: 12; label: 1.11
title: Exercises
pagenum: 12; label: Chapter 2
title: Parallel Hardware and Parallel Software
pagenum: 15; label: 2.1
title: Some Background
pagenum: 15; label: 2.1.1
title: The von Neumann Architecture
pagenum: 15; label: 2.1.2
title: Processes, Multitasking, and Threads
pagenum: 17; label: 2.2
title: Modifications to the von Neumann Model
pagenum: 18; label: 2.2.1
title: The Basics of Caching
pagenum: 19; label: 2.2.2
title: Cache Mappings
pagenum: 20; label: 2.2.3
title: Caches and Programs: An Example
pagenum: 22; label: 2.2.4
title: Virtual Memory
pagenum: 23; label: 2.2.5
title: Instruction-Level Parallelism
pagenum: 25; label: 2.2.6
title: Hardware Multithreading
pagenum: 28; label: 2.3
title: Parallel Hardware
pagenum: 29; label: 2.3.1
title: SIMD Systems
pagenum: 29; label: 2.3.2
title: MIMD Systems
pagenum: 32; label: 2.3.3
title: Interconnection Networks
pagenum: 35; label: 2.3.4
title: Cache Coherence
pagenum: 43; label: 2.3.5
title: Shared-Memory Versus Distributed-Memory
pagenum: 46; label: 2.4
title: Parallel Software
pagenum: 47; label: 2.4.1
title: Caveats
pagenum: 47; label: 2.4.2
title: Coordinating the Processes/Threads
pagenum: 48; label: 2.4.3
title: Shared-Memory
pagenum: 49; label: 2.4.4
title: Distributed-Memory
pagenum: 53; label: 2.4.5
title: Programming Hybrid Systems
pagenum: 56; label: 2.5
title: Input and Output
pagenum: 56; label: 2.6
title: Performance
pagenum: 58; label: 2.6.1
title: Speedup and Efficiency
pagenum: 58; label: 2.6.2
title: Amdahl's Law
pagenum: 61; label: 2.6.3
title: Scalability
pagenum: 62; label: 2.6.4
title: Taking Timings
pagenum: 63; label: 2.7
title: Parallel Program Design
pagenum: 65; label: 2.7.1
title: An Example
pagenum: 66; label: 2.8
title: Writing and Running Parallel Programs
pagenum: 70; label: 2.9
title: Assumptions
pagenum: 70; label: 2.10
title: Summary
pagenum: 71; label: 2.10.1
title: Serial Systems
pagenum: 71; label: 2.10.2
title: Parallel Hardware
pagenum: 73; label: 2.10.3
title: Parallel Software
pagenum: 74; label: 2.10.4
title: Input and Output
pagenum: 75; label: 2.10.5
title: Performance
pagenum: 75; label: 2.10.6
title: Parallel Program Design
pagenum: 76; label: 2.10.7
title: Assumptions
pagenum: 76; label: 2.11
title: Exercises
pagenum: 77; label: Chapter 3
title: Distributed-Memory Programming With MPI
pagenum: 83; label: 3.1
title: Getting Started
pagenum: 84; label: 3.1.1
title: Compilation and Execution
pagenum: 84; label: 3.1.2
title: MPI Programs
pagenum: 86; label: 3.1.3
title: MPI_Init and MPI_Finalize
pagenum: 86; label: 3.1.4
title: Communicators, MPI_Comm_size and MPI_Comm_rank
pagenum: 87; label: 3.1.5
title: SPMD Programs
pagenum: 88; label: 3.1.6
title: Communication
pagenum: 88; label: 3.1.7
title: MPI_Send
pagenum: 88; label: 3.1.8
title: MPI_Recv
pagenum: 90; label: 3.1.9
title: Message Matching
pagenum: 91; label: 3.1.10
title: The status_p Argument
pagenum: 92; label: 3.1.11
title: Semantics of MPI_Send and MPI_Recv
pagenum: 93; label: 3.1.12
title: Some Potential Pitfalls
pagenum: 94; label: 3.2
title: The Trapezoidal Rule in MPI
pagenum: 94; label: 3.2.1
title: The Trapezoidal Rule
pagenum: 94; label: 3.2.2
title: Parallelizing the Trapezoidal Rule
pagenum: 96; label: 3.3
title: Dealing With I/O
pagenum: 97; label: 3.3.1
title: Output
pagenum: 97; label: 3.3.2
title: Input
pagenum: 100; label: 3.4
title: Collective Communication
pagenum: 101; label: 3.4.1
title: Tree-Structured Communication
pagenum: 102; label: 3.4.2
title: MPI_Reduce
pagenum: 103; label: 3.4.3
title: Collective vs. Point-to-Point Communications
pagenum: 105; label: 3.4.4
title: MPI_Allreduce
pagenum: 106; label: 3.4.5
title: Broadcast
pagenum: 106; label: 3.4.6
title: Data Distributions
pagenum: 109; label: 3.4.7
title: Scatter
pagenum: 110; label: 3.4.8
title: Gather
pagenum: 112; label: 3.4.9
title: Allgather
pagenum: 113; label: 3.5
title: MPI Derived Datatypes
pagenum: 116; label: 3.6
title: Performance Evaluation of MPI Programs
pagenum: 119; label: 3.6.1
title: Taking Timings
pagenum: 119; label: 3.6.2
title: Results
pagenum: 122; label: 3.6.3
title: Speedup and Efficiency
pagenum: 125; label: 3.6.4
title: Scalability
pagenum: 126; label: 3.7
title: A Parallel Sorting Algorithm
pagenum: 127; label: 3.7.1
title: Some Simple Serial Sorting Algorithms
pagenum: 127; label: 3.7.2
title: Parallel Odd-Even Transposition Sort
pagenum: 129; label: 3.7.3
title: Safety in MPI Programs
pagenum: 132; label: 3.7.4
title: Final Details of Parallel Odd-Even Sort
pagenum: 134; label: 3.8
title: Summary
pagenum: 136; label: 3.9
title: Exercises
pagenum: 140; label: 3.10
title: Programming Assignments
pagenum: 147; label: Chapter 4
title: Shared-Memory Programming With Pthreads
pagenum: 151; label: 4.1
title: Processes, Threads, and Pthreads
pagenum: 151; label: 4.2
title: Hello, World
pagenum: 153; label: 4.2.1
title: Execution
pagenum: 153; label: 4.2.2
title: Preliminaries
pagenum: 155; label: 4.2.3
title: Starting the Threads
pagenum: 156; label: 4.2.4
title: Running the Threads
pagenum: 157; label: 4.2.5
title: Stopping the Threads
pagenum: 158; label: 4.2.6
title: Error Checking
pagenum: 158; label: 4.2.7
title: Other Approaches to Thread Startup
pagenum: 159; label: 4.3
title: Matrix-Vector Multiplication
pagenum: 159; label: 4.4
title: Critical Sections
pagenum: 162; label: 4.5
title: Busy-Waiting
pagenum: 165; label: 4.6
title: Mutexes
pagenum: 168; label: 4.7
title: Producer-Consumer Synchronization and Semaphores
pagenum: 171; label: 4.8
title: Barriers and Condition Variables
pagenum: 176; label: 4.8.1
title: Busy-Waiting and a Mutex
pagenum: 177; label: 4.8.2
title: Semaphores
pagenum: 177; label: 4.8.3
title: Condition Variables
pagenum: 179; label: 4.8.4
title: Pthreads Barriers
pagenum: 181; label: 4.9
title: Read-Write Locks
pagenum: 181; label: 4.9.1
title: Linked List Functions
pagenum: 181; label: 4.9.2
title: A Multi-Threaded Linked List
pagenum: 183; label: 4.9.3
title: Pthreads Read-Write Locks
pagenum: 187; label: 4.9.4
title: Performance of the Various Implementations
pagenum: 188; label: 4.9.5
title: Implementing Read-Write Locks
pagenum: 190; label: 4.10
title: Caches, Cache Coherence, and False Sharing
pagenum: 190; label: 4.11
title: Thread-Safety
pagenum: 195; label: 4.11.1
title: Incorrect Programs Can Produce Correct Output
pagenum: 198; label: 4.12
title: Summary
pagenum: 198; label: 4.13
title: Exercises
pagenum: 200; label: 4.14
title: Programming Assignments
pagenum: 206; label: Chapter 5
title: Shared-Memory Programming With OpenMP
pagenum: 209; label: 5.1
title: Getting Started
pagenum: 210; label: 5.1.1
title: Compiling and Running OpenMP Programs
pagenum: 211; label: 5.1.2
title: The Program
pagenum: 212; label: 5.1.3
title: Error Checking
pagenum: 215; label: 5.2
title: The Trapezoidal Rule
pagenum: 216; label: 5.2.1
title: A First OpenMP Version
pagenum: 216; label: 5.3
title: Scope of Variables
pagenum: 220; label: 5.4
title: The Reduction Clause
pagenum: 221; label: 5.5
title: The parallel for Directive
pagenum: 224; label: 5.5.1
title: Caveats
pagenum: 225; label: 5.5.2
title: Data Dependences
pagenum: 227; label: 5.5.3
title: Finding Loop-Carried Dependences
pagenum: 228; label: 5.5.4
title: Estimating I
pagenum: 229; label: 5.5.5
title: More on Scope
pagenum: 231; label: 5.6
title: More About Loops in OpenMP: Sorting
pagenum: 232; label: 5.6.1
title: Bubble Sort
pagenum: 232; label: 5.6.2
title: Odd-Even Transposition Sort
pagenum: 233; label: 5.7
title: Scheduling Loops
pagenum: 236; label: 5.7.1
title: The schedule Clause
pagenum: 237; label: 5.7.2
title: The static Schedule Type
pagenum: 238; label: 5.7.3
title: The dynamic and guided Schedule Types
pagenum: 239; label: 5.7.4
title: The runtime Schedule Type
pagenum: 239; label: 5.7.5
title: Which Schedule?
pagenum: 241; label: 5.8
title: Producers and Consumers
pagenum: 241; label: 5.8.1
title: Queues
pagenum: 241; label: 5.8.2
title: Message-Passing
pagenum: 242; label: 5.8.3
title: Sending Messages
pagenum: 243; label: 5.8.4
title: Receiving Messages
pagenum: 243; label: 5.8.5
title: Termination Detection
pagenum: 244; label: 5.8.6
title: Startup
pagenum: 244; label: 5.8.7
title: The atomic Directive
pagenum: 245; label: 5.8.8
title: Critical Sections and Locks
pagenum: 246; label: 5.8.9
title: Using Locks in the Message-Passing Program
pagenum: 248; label: 5.8.10
title: Critical Directives, Atomic Directives, or Locks?
pagenum: 249; label: 5.8.11
title: Some Caveats
pagenum: 249; label: 5.9
title: Caches, Cache Coherence, and False Sharing
pagenum: 251; label: 5.10
title: Thread-Safety
pagenum: 256; label: 5.10.1
title: Incorrect Programs Can Produce Correct Output
pagenum: 258; label: 5.11
title: Summary
pagenum: 259; label: 5.12
title: Exercises
pagenum: 263; label: 5.13
title: Programming Assignments
pagenum: 267; label: Chapter 6
title: Parallel Program Development
pagenum: 271; label: 6.1
title: Two n-Body Solvers
pagenum: 271; label: 6.1.1
title: The Problem
pagenum: 271; label: 6.1.2
title: Two Serial Programs
pagenum: 273; label: 6.1.3
title: Parallelizing the n-Body Solvers
pagenum: 277; label: 6.1.4
title: A Word About I/O
pagenum: 280; label: 6.1.5
title: Parallelizing the Basic Solver Using OpenMP
pagenum: 281; label: 6.1.6
title: Parallelizing the Reduced Solver Using OpenMP
pagenum: 284; label: 6.1.7
title: Evaluating the OpenMP Codes
pagenum: 288; label: 6.1.8
title: Parallelizing the Solvers Using Pthreads
pagenum: 289; label: 6.1.9
title: Parallelizing the Basic Solver Using MPI
pagenum: 290; label: 6.1.10
title: Parallelizing the Reduced Solver Using MPI
pagenum: 292; label: 6.1.11
title: Performance of the MPI Solvers
pagenum: 297; label: 6.2
title: Tree Search
pagenum: 299; label: 6.2.1
title: Recursive Depth-First Search
pagenum: 302; label: 6.2.2
title: Nonrecursive Depth-First Search
pagenum: 303; label: 6.2.3
title: Data Structures for the Serial Implementations
pagenum: 305; label: 6.2.4
title: Performance of the Serial Implementations
pagenum: 306; label: 6.2.5
title: Parallelizing Tree Search
pagenum: 306; label: 6.2.6
title: A Static Parallelization of Tree Search Using Pthreads
pagenum: 309; label: 6.2.7
title: A Dynamic Parallelization of Tree Search Using Pthreads
pagenum: 310; label: 6.2.8
title: Evaluating the Pthreads Tree-Search Programs
pagenum: 315; label: 6.2.9
title: Parallelizing the Tree-Search Programs Using OpenMP
pagenum: 316; label: 6.2.10
title: Performance of the OpenMP Implementations
pagenum: 318; label: 6.2.11
title: Implementation of Tree Search Using MPI and Static Partitioning
pagenum: 319; label: 6.2.12
title: Implementation of Tree Search Using MPI and Dynamic Partitioning
pagenum: 327; label: 6.3
title: A Word of Caution
pagenum: 335; label: 6.4
title: Which API?
pagenum: 335; label: 6.5
title: Summary
pagenum: 336; label: 6.5.1
title: Pthreads and OpenMP
pagenum: 337; label: 6.5.2
title: MPI
pagenum: 338; label: 6.6
title: Exercises
pagenum: 341; label: 6.7
title: Programming Assignments
pagenum: 350; label: Chapter 7
title: Where to Go From Here
pagenum: 353; title: References
pagenum: 357; title: Index
pagenum: 361