并行开发艺术PDF电子书下载

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