IsParallelProgrammingHardAndIfSoWhatCanYouDoAboutIt资源-CSDN文库

需积分: 10 69 浏览量 2018-05-05 14:54:12 上传评论收藏 3.51MB PDF 举报

并行编程难度及其对策，是一篇由Paul E. McKenney编辑，发布于2011年1月2日的文档，它来源于互联网，该文档主要探讨了并行编程的困难点以及面对这些困难时可以采取的相应策略。并行编程作为一种技术，它允许程序员将程序的执行任务拆分成可以同时运行的多个子任务，以利用多核处理器或多处理器系统的能力，从而提高程序的执行效率。但是，随着计算机硬件的多核化，如何有效地进行并行编程变得越来越重要，同时也越来越具有挑战性。并行编程之所以困难，主要是因为它需要考虑诸多因素，例如任务之间的依赖关系、资源竞争以及数据一致性问题。文档提到，为了实现并行化，必须对程序进行重构，并使用专门的并行算法来处理这些子任务。此外，程序的并行化还需要程序员对硬件架构有深入的理解，从而能够设计出高效的并行算法，避免不必要的同步和通信开销。并行编程的目标主要包括以下几点： 1. 性能：并行编程最直观的目标是提高程序性能，通过将计算任务分散到多个处理单元上来实现更快的处理速度。 2. 生产力：尽管提高程序性能是并行编程的主要目标之一，但实现这一点的过程中不能牺牲开发者的生产力，即开发效率。一个成功的并行编程模型应当是易于理解和使用的，这样开发者可以更高效地编写、测试和维护程序。 3. 通用性：并行编程模型应具有一定的通用性，以便于在不同的硬件架构和不同的应用场景下都能得到有效的应用。并行编程的替代方法主要包括： 1. 多个顺序应用程序的实例：这是最简单的并行方法之一，指的是在不同的核心或处理器上运行多个实例的顺序程序。 2. 利用现有的并行软件：使用那些已经为并行环境优化过的软件库和应用程序，开发者无需从头开始编写并行代码。 3. 性能优化：通过优化算法和数据结构，使用编译器和运行时系统的优化技术，有时也可以在不涉及并行处理的情况下实现性能提升。面对并行编程的难度，文档中提出了以下几点应对策略： 1. 提高抽象级别：通过使用高级抽象，如任务并行库，开发者可以避免直接管理底层线程和同步机制。 2. 自动化并行化：自动并行化工具可以帮助开发者将顺序代码转换为并行代码，尽管这种方法目前尚不成熟。 3. 利用硬件特性：充分利用现代硬件的特性，例如多级缓存系统、多线程指令集和异步I/O，可以帮助编写出更为高效的并行程序。文档也强调了对知识产权的尊重，提到文档中非源代码文本和图片是根据Creative Commons Attribution-Share Alike 3.0 United States License提供的，这意味着任何用途下，只要保持对原作者的归属，都可以自由使用这些内容。为了更好地理解并行编程，该文档还提供了源代码实例，这些代码是从GPL许可证的Linux内核中导出的，文档中指明了相关代码的许可情况，强调如果对某段代码的许可有疑问，应假设其为仅限GPLv2许可。文档最后以Paul E. McKenney的综述结束，讨论了历史并行编程的难题，并为并行编程的目标提供了明确的方向。在现代IT行业中，对并行编程有深入的了解将是一个开发者成功与否的关键因素之一，而这份文档为我们提供了深入的见解和宝贵的实践经验。

资源推荐

资源详情

资源评论

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

About It?

Edited by:

Paul E. McKenney

Linux Technology Center

IBM Beaverton

paulmck@linux.vnet.ibm.com

January 2, 2011

Contents

1 Intro d uc ti on 1

1.1 Historic Parallel Programming Diﬃculties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Parallel Programming Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2.1 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2.2 Productivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.3 Generality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Alternatives to Parallel Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1 Multiple Instances of a Sequential Application . . . . . . . . . . . . . . . . . . . . . . 6

1.3.2 Make Use of Existing Parallel Software . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3.3 Performance Opt imiz ation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 What Makes Parallel Programming Hard? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.1 Work Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.2 Parallel Acces s Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4.3 Resource Partitioning and Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4.4 Interacting W it h Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4.5 Composite Capabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4.6 How Do Languages and Environments Assist Wi th These Tasks? . . . . . . . . . . . . 9

1.5 Guide to This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.5.1 Quick Quizze s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.5.2 Sample Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Hard ware and its Habits 11

2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.1 Pipelined CPUs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.2 Memory References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.3 Atomic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.4 Memory Barriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.5 Cache Misses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.6 I/O Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2 Overheads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.1 Hardware System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.2 Costs of Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3 Hardware Free Lunch? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3.1 3D Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3.2 Novel Materials and Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.3 Special-Purpose Accelerators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.4 Existing Parallel Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4 Software Design Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

iii

iv CONTENTS

3 Tools of the Trade 19

3.1 Scripting Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 POSIX Multiprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2.1 POSIX Process Creation and Destruction . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2.2 POSIX Thread Creation and Destruction . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.2.3 POSIX Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.2.4 POSIX Reader-Writer Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.3 Atomic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.4 Linux-Kernel Equivalents to POSIX Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.5 The Right Tool for the Job: How to Choose? . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4 Counting 29

4.1 Why Isn’t Concurrent Counting Trivial? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.2 Statistical Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2.2 Array-Based Imple mentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2.3 Eventually Cons is te nt Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.2.4 Per-Thread-Variable- Base d Implementation . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.3 Approximate Limi t Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.3.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.3.2 Simple Limit Counter Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.3.3 Simple Limit Counter Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.3.4 Approximate Limi t Counter Implementation . . . . . . . . . . . . . . . . . . . . . . . 37

4.3.5 Approximate Limi t Counter Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.4 Exact Limit Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.4.1 Atomic Limit Counter Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.4.2 Atomic Limit Counter Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.4.3 Signal-Theft Limit Counter Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.4.4 Signal-Theft Limit Counter Implementation . . . . . . . . . . . . . . . . . . . . . . . . 42

4.4.5 Signal-Theft Limit Counter Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.5 Applying Specialized Parallel Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.6 Parallel Counting Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5 Partitioning and Synchronization Design 47

5.1 Partitioning Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.1.1 Dining Philosophers Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.1.2 Double-Ended Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.1.3 Partitioning Example Discu s s ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.2 Design Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.3 Synchronization Granularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.3.1 Sequential Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.3.2 Code Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.3.3 Data Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.3.4 Data Ownership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.3.5 Locking Granularity and Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.4 Parallel Fastpath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.4.1 Reader/Writer Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.4.2 Read-Copy Update Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.4.3 Hierarchical Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.4.4 Resource Allocator Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.5 Performance Su mmary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

CONTENTS v

6 L ocking 67

6.1 Staying Alive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.1.1 Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.1.2 Livelock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.1.3 Starvation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.1.4 Unfairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.1.5 Ineﬃciency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.2 Types of Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.2.1 Exclusive Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.2.2 Reader-Writer Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.2.3 Beyond Reader-Writer Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.2.4 While Waiting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.2.5 Sleeping Safely . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.3 Lock-Based Existence Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7 D ata Ownership 69

8 D eferred Processing 71

8.1 Barriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

8.2 Reference Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

8.2.1 Implementation of Reference-Counting Categories . . . . . . . . . . . . . . . . . . . . 72

8.2.2 Linux Primitives Supporting Reference Counting . . . . . . . . . . . . . . . . . . . . . 75

8.2.3 Counter Optimizati ons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

8.3 Read-Copy Update (RCU) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

8.3.1 RCU Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

8.3.2 RCU Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

8.3.3 RCU Linux-Kernel API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

8.3.4 “Toy” RCU Imple mentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

8.3.5 RCU Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

9 Ap pl y i n g RCU 109

9.1 RCU and Per-Thread-Variable-Based Statistical Counters . . . . . . . . . . . . . . . . . . . . 109

9.1.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

9.1.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

9.1.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

9.2 RCU and Counters for Removable I/O Devices . . . . . . . . . . . . . . . . . . . . . . . . . . 111

10 Validation: Debugging and Analysis 113

10.1 Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

10.2 Assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

10.3 Static Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

10.4 Probability and Heisenbugs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

10.5 Proﬁling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

10.6 Diﬀerential Proﬁling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

10.7 Performance Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

11 Data Structures 115

11.1 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

11.2 Computational Complexity and Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

11.3 Design Tradeoﬀs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

11.4 Protection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

11.5 Bits and Bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

11.6 Hardware Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

剩余357页未读，继续阅读

评论收藏

内容反馈

吉祥水

粉丝: 18
资源: 110

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

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

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

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

parallel_programming_Chinese:翻译并行编程的一本书

Is.Parallel.Programming.Hard

Learning+Concurrent+Programming+in+Scala,+2nd+Edition-2017.mobi

Reactive Android Programming

BobBuilder_app

并行编程技术(linux)

java并发编程（好文）

The Indispensable PC Hardware Book - rar - part1. (1/7)

多线程编程

The Art of Assembly Language Programming

The Algorithm Design Manual (2rd Edition)

Writing Testbenches using System Verilog

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

XCP协议的规范文档

GD32替换STM32注意事项.pdf

NPPJSONViewer.zip

蓝牙BLE协议中文版.pdf

CANoe通过CAPL脚本实现自动测试

AD20官方中文教程.pdf

完整版 Microsoft.ACE.OLEDB.12.0 驱动下载.rar

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）