IsParallelProgrammingHard,And,IfSo,WhatCanYou.pd

Parallel

Programming

需积分: 9 85 浏览量更新于2023-03-16 评论收藏 6.97MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Is Parallel Programming Hard, And, If So, What Can You Do

About It?

First Print Edition

Edited by:

Paul E. McKenney

Linux Technology Center

IBM Beaverton

paulmck@linux.vnet.ibm.com

April 3, 2014

Contents

1 How To Use This Book 1

1.1 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Quick Quizzes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Alternatives to This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.4 Sample Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.5 Whose Book Is This? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Introduction 5

2.1 Historic Parallel Programming Difﬁculties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Parallel Programming Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2.1 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2.2 Productivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2.3 Generality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3 Alternatives to Parallel Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3.1 Multiple Instances of a Sequential Application . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3.2 Use Existing Parallel Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3.3 Performance Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 What Makes Parallel Programming Hard? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.1 Work Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.2 Parallel Access Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4.3 Resource Partitioning and Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4.4 Interacting With Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4.5 Composite Capabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4.6 How Do Languages and Environments Assist With These Tasks? . . . . . . . . . . . . . . . . 13

2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Hardware and its Habits 15

3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.1.1 Pipelined CPUs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.1.2 Memory References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.1.3 Atomic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1.4 Memory Barriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1.5 Cache Misses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1.6 I/O Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.2 Overheads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2.1 Hardware System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2.2 Costs of Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3 Hardware Free Lunch? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

iii

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

CONTENTS v

6.3.3 Data Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.3.4 Data Ownership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.3.5 Locking Granularity and Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.4 Parallel Fastpath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.4.1 Reader/Writer Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.4.2 Hierarchical Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.4.3 Resource Allocator Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.5 Beyond Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.5.1 Work-Queue Parallel Maze Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6.5.2 Alternative Parallel Maze Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6.5.3 Performance Comparison I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.5.4 Alternative Sequential Maze Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6.5.5 Performance Comparison II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6.5.6 Future Directions and Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

6.6 Partitioning, Parallelism, and Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

7 Locking 87

7.1 Staying Alive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

7.1.1 Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

7.1.2 Livelock and Starvation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

7.1.3 Unfairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

7.1.4 Inefﬁciency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

7.2 Types of Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

7.2.1 Exclusive Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

7.2.2 Reader-Writer Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

7.2.3 Beyond Reader-Writer Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

7.2.4 Scoped Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

7.3 Locking Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

7.3.1 Sample Exclusive-Locking Implementation Based on Atomic Exchange . . . . . . . . . . . . 98

7.3.2 Other Exclusive-Locking Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

7.4 Lock-Based Existence Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

7.5 Locking: Hero or Villain? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

7.5.1 Locking For Applications: Hero! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

7.5.2 Locking For Parallel Libraries: Just Another Tool . . . . . . . . . . . . . . . . . . . . . . . . 101

7.5.3 Locking For Parallelizing Sequential Libraries: Villain! . . . . . . . . . . . . . . . . . . . . . 104

7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

8 Data Ownership 107

8.1 Multiple Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

8.2 Partial Data Ownership and pthreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

8.3 Function Shipping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

8.4 Designated Thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

8.5 Privatization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

8.6 Other Uses of Data Ownership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

9 Deferred Processing 111

9.1 Reference Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

9.1.1 Implementation of Reference-Counting Categories . . . . . . . . . . . . . . . . . . . . . . . 112

9.1.2 Hazard Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

9.1.3 Linux Primitives Supporting Reference Counting . . . . . . . . . . . . . . . . . . . . . . . . 116

剩余520页未读，继续阅读

phenix_lord

粉丝: 23
资源: 1

会员权益专享

Is Parallel Programming Hard, And, If So, What Can You.pd

评论0

会员权益专享

最新资源

Is Parallel Programming Hard, And, If So, What Can You.pd

评论0

并行编程技术(linux)

Is Parallel Programming Hard, And, If So, What Can You Do About It

Is Parallel Programming Hard And If So What Can You Do About It

parallel programming: concepts and practice pdf

NotImplementedError: Cuda is not availabel

jetson nano CUDA

Optimize Live Editor Task

parallel mode only supports posix system

jmeter Parallel Controller

What is mapreduce ? Explain the functions of mapper and reducer with example

查询以下文献的GB/T 7713.1-2006的标准格式，包含期、卷和起止页码： MA Z, CHEN X, MA T, et al. Deep Deterministic Policy Gradient Based Resource Allocation in Internet of Vehicles[C].PAAP 2020: Parallel Architectures, Algorithms and Programming ,2020,pp. 295–306.

pragma omp parallel for

Could not run command: cat \/hwfssz1\/ST_HEALTH\/P19Z10200N0314\/renhongzhen\/test\/T2210300965\/T2210300965\.IS\.tmp\.37099\.faa | parallel

stream.parallel()

Error(s) in loading state_dict for DataParallel:

parallel programming in c with mpi and openmp solution manual

cv-cuda c++

会员权益专享

最新资源