1 WANT TO GO FASTER?RAISE YOUR HANDS IF YOU WANT TO GO FASTER! 1
Some Questions You May Have 2
Four Steps of a Threading Methodology 7
Background of Parallel Algorithms 12
Shared-Memory Programming Versus Distributed-Memory Programming 15
This Book's Approach to Concurrent Programming 19
2 CONCURRENT OR NOT CONCURRENT? 21
Design Models for Concurrent Algorithms 22
What's Not Parallel 42
3 PROVING CORRECTNESS AND MEASURING PERFORMANCE 49
Verification of Parallel Algorithms 50
Example:The Critical Section Problem 53
Performance Metrics(How Am I Doing?) 66
Review of the Evolution for Supporting Parallelism in Hardware 71
4 EIGHT SIMPLE RULES FOR DESIGNING MULTITHREADED APPLICATIONS 73
Rule 1:Identify Truly Independent Computations 74
Rule 2:Implement Concurrency at the Highest Level Possible 74
Rule 3:Plan Early for Scalability to Take Advantage of Increasing Numbers of Cores 75
Rule 4:Make Use of Thread-Safe Libraries Wherever Possible 76
Rule 5:Use the Right Threading Model 77
Rule 6:Never Assume a Particular Order of Execution 77
Rule 7:Use Thread-Local Storage Whenever Possible or Associate Locks to Specific Data 78
Rule 8:Dare to Change the Algorithm for a Better Chance of Concurrency 79
Summary 80
5 THREADING LIBRARIES 81
Implicit Threading 82
Explicit Threading 88
What Else Is Out There? 92
Domain-Specific Libraries 92
6 PARALLEL SUM AND PREFIX SCAN 95
Parallel Sum 96
Prefix Scan 103
Selection 112
A Final Thought 123
7 MAPREDUCE 125
Map As a Concurrent Operation 127
Reduce As a Concurrent Operation 129
Applying MapReduce 138
MapReduce As Generic Concurrency 143
8 SORTING 145
Bubblesort 146
Odd-Euen Transposition Sort 153
Shellsort 162
Quicksort 169
Radix Sort 182
9 SEARCHING 201
Unsorted Sequence 202
Binary Search 210
10 GRAPH ALGORITHMS 221
Depth-First Search 224
All-Pairs Shortest Path 240
Minimum Spanning Tree 245
11 THREADING TOOLS 257
Debuggers 258
Performance Tools 260
Anything Else Out There? 262
Go Forth and Conquer 263
GLOSSARY 265
PHOTO CREDITS 275
INDEX 277