iv CONTENTS
3.3.1 3D Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.2 Novel Materials and Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.3 Light, Not Electrons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.4 Special-Purpose Accelerators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.5 Existing Parallel Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4 Software Design Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 Tools of the Trade 25
4.1 Scripting Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 POSIX Multiprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.1 POSIX Process Creation and Destruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.2 POSIX Thread Creation and Destruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.3 POSIX Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.4 POSIX Reader-Writer Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.3 Atomic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.4 Linux-Kernel Equivalents to POSIX Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.5 The Right Tool for the Job: How to Choose? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5 Counting 35
5.1 Why Isn’t Concurrent Counting Trivial? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2 Statistical Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2.2 Array-Based Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2.3 Eventually Consistent Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2.4 Per-Thread-Variable-Based Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3 Approximate Limit Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3.2 Simple Limit Counter Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3.3 Simple Limit Counter Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.3.4 Approximate Limit Counter Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.3.5 Approximate Limit Counter Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.4 Exact Limit Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.4.1 Atomic Limit Counter Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.4.2 Atomic Limit Counter Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4.3 Signal-Theft Limit Counter Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.4.4 Signal-Theft Limit Counter Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.4.5 Signal-Theft Limit Counter Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.5 Applying Specialized Parallel Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.6 Parallel Counting Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6 Partitioning and Synchronization Design 59
6.1 Partitioning Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.1.1 Dining Philosophers Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.1.2 Double-Ended Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.3 Partitioning Example Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2 Design Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3 Synchronization Granularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.3.1 Sequential Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.3.2 Code Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
zanjun2019-01-14并行编程领域不可多得的好书，作者功力深厚
