高效计算模式：结构化并行编程

5星 · 超过95%的资源需积分: 13 40 浏览量更新于2024-07-22 2 收藏 5.02MB PDF 举报

"Structured Parallel Programming - Patterns for Efficient Computation 是一本由Michael McCool、Arch D. Robison和James Reinders合著的书籍，被Intel推荐，主要关注并行编程的模式和高效计算方法。" 该书深入探讨了结构化并行编程的概念，旨在帮助读者理解和应用并行计算的策略，以提高程序的效率。在当今多核处理器和GPU（图形处理单元）普遍存在的时代，了解并行编程已成为提升软件性能的关键。这本书通过介绍一系列的编程模式，使开发者能够有效地利用硬件资源，实现并行计算的优势。作者们在书中详细讲解了以下关键知识点： 1. **并行计算基础**：首先，书中会介绍并行计算的基本概念，包括并行性类型（数据并行、任务并行）、并行计算的挑战（如同步、通信、负载均衡）以及并行计算模型（如OpenMP、MPI和CUDA）。 2. **并行编程模式**：书中将详细阐述各种结构化的并行编程模式，如Map、Reduce、Filter、Scan等，这些模式在并行计算中广泛应用，有助于编写可扩展且易于维护的代码。 3. **并行算法设计**：书中的内容可能涵盖如何将串行算法转化为并行算法，包括分治法、动态调度和流水线等策略，以最大限度地提高计算效率。 4. **并发控制与同步**：书中会讨论如何处理并发中的数据一致性问题，如使用锁、信号量、条件变量等同步机制，以及无锁编程和事务内存等高级技术。 5. **并行性能分析与优化**：读者将学习如何评估并行程序的性能，使用性能分析工具，以及如何根据性能数据进行代码优化。 6. **硬件平台与编程接口**：针对Intel推荐的背景，书可能特别关注多核CPU和Intel的并行编程接口，如Intel Threading Building Blocks (TBB) 和OpenMP。 7. **案例研究与实践**：书中可能会包含实际项目案例，展示如何将所学的并行编程模式应用于实际工程中，帮助读者将理论知识转化为实际技能。通过学习《Structured Parallel Programming》，读者可以掌握并行编程的理论知识和实践经验，为开发高性能计算应用打下坚实基础。这不仅对个人职业发展有益，也是满足现代计算需求的必备技能。

To protect the rights of the author(s) and publisher we inform you that this PDF is an uncorrected proof for internal business use only by the author(s), editor(s),

reviewer(s), Elsevier and typesetter diacriTech. It is not allowed to publish this proof online or in print. This proof copy is the copyright property of the publisher

and is conﬁdential until formal publication.

McCool — 03-lol-xv-xviii-9780124159938 — 2012/6/6 — 12:54 — Page xv — #1

Listings

1.1 Add two vectors in C, with implied serial ordering .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . 17

1.2 Overlapping (aliased) arguments in C. . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 17

1.3 Add two vectors using Cilk Plus array notation . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 17

1.4 An ordered sum creates a dependence in C . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. 18

1.5 A parallel sum, expressed as a reduction operation in Cilk Plus. . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . 18

1.6 Function calls with step-by-step ordering speciﬁed in C ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 18

1.7 Function calls with no required ordering in Cilk Plus . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 19

1.8 Serial vector addition coded as a loop in C . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... 24

1.9 Parallel vector addition using Cilk Plus . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 25

1.10 Parallel vector addition using ArBB ... . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . 25

1.11 Scalar function for addition in C . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 26

1.12 Vectorized function for addition in Cilk Plus . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . 26

1.13 Serial Fibonacci computation in C . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 31

1.14 Parallel Cilk Plus variant of Listing 1.13 ... . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . 31

1.15 Vector computation in ArBB .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . 34

1.16 Elemental function computation in ArBB ... . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . 35

3.1 Serial sequence in pseudocode .. . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . 82

3.2 Serial sequence, second example, in pseudocode . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 83

3.3 Serial selection in pseudocode. . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . 84

3.4 Iteration using a while loop in pseudocode .... . . . .. . . ... . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . . 85

3.5 Iteration using a for loop in pseudocode . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 85

3.6 Demonstration of while/for equivalence in pseudocode . . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... 86

3.7 A difﬁcult example in C ... . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . 87

3.8 Another difﬁcult example in C .. . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . 87

3.9 Serial implementation of reduction. . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . 91

3.10 Serial implementation of scan ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . 93

3.11 Superscalar sequence in pseudocode . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . 103

4.1 Serial implementation of SAXPY in C . . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 126

4.2 Tiled implementation of SAXPY in TBB . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 126

4.3 SAXPY in Cilk Plus using cilk_for . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . 127

4.4 SAXPY in Cilk Plus using cilk_for and array notation for explicit vectorization . . .. . . . .. 127

4.5 SAXPY in OpenMP. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . . 128

4.6 SAXPY in ArBB, using a vector expression. . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . 129

To protect the rights of the author(s) and publisher we inform you that this PDF is an uncorrected proof for internal business use only by the author(s), editor(s),

reviewer(s), Elsevier and typesetter diacriTech. It is not allowed to publish this proof online or in print. This proof copy is the copyright property of the publisher

and is conﬁdential until formal publication.

McCool — 03-lol-xv-xviii-9780124159938 — 2012/6/6 — 12:54 — Page xvi — #2

xvi Listings

4.7 SAXPY in ArBB, using binding code for vector expression implementation .... . . ... . . .. . . . 129

4.8 SAXPY in ArBB, using an elemental function . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. 130

4.9 SAXPY in ArBB, call operation ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... 130

4.10 SAXPY in OpenCL kernel language .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . 131

4.11 Serial implementation of Mandelbrot in C . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . 133

4.12 Tiled implementation of Mandelbrot in TBB . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . 133

4.13 Mandelbrot using cilk_for in Cilk Plus . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . 134

4.14 Mandelbrot in Cilk Plus using cilk_for and array notation for explicit vectorization .. . . . 135

4.15 Mandelbrot in OpenMP .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 136

4.16 Mandelbrot elemental function for ArBB map operation ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . 136

4.17 Mandelbrot call code for ArBB implementation ... . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. 137

4.18 Mandelbrot binding code for ArBB implementation . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. 137

4.19 Mandelbrot kernel code for OpenCL implementation. .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. 138

5.1 Serial reduction in C++ for 0 or more elements . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . 146

5.2 Serial reduction in C++ for 1 or more elements . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . 147

5.3 Serial implementation of dot product in C++ . . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . 155

5.4 Vectorized dot product implemented using SSE intrinsics . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . . 156

5.5 Dot product implemented in TBB . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . 157

5.6 Modiﬁcation of Listing 5.5 with double-precision operations ... . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 158

5.7 Dot product implemented in Cilk Plus array notation . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. 159

5.8 Dot product implementation in Cilk Plus using explicit tiling . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. 159

5.9 Modiﬁcation of Listing 5.8 with double-precision operations for multiplication

and accumulation... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. 160

5.10 Dot product implemented in OpenMP . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . 160

5.11 Dot product implemented in ArBB... . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. 161

5.12 Dot product implementation in ArBB, wrapper code . . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . 161

5.13 High-precision dot product implemented in ArBB . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . 162

5.14 Serial implementation of inclusive scan in C++ .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . 163

5.15 Serial implementation of exclusive scan in C++ . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . 164

5.16 Three-phase tiled implementation of a scan in OpenMP .. . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 168

5.17 Serial integrated table preparation in C++ . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . .. 171

5.18 Generic test function for integration ... . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 171

5.19 Concrete instantiation of test function for integration .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . 171

5.20 Serial implementation of integrated table lookup in C++ .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . 172

5.21 Integrated table preparation in Cilk Plus .... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 173

5.22 Integrated table preparation in TBB. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . 174

5.23 Integrated table preparation in ArBB . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . 175

5.24 Integrated table lookup in ArBB ... . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 176

To protect the rights of the author(s) and publisher we inform you that this PDF is an uncorrected proof for internal business use only by the author(s), editor(s),

reviewer(s), Elsevier and typesetter diacriTech. It is not allowed to publish this proof online or in print. This proof copy is the copyright property of the publisher

and is conﬁdential until formal publication.

McCool — 03-lol-xv-xviii-9780124159938 — 2012/6/6 — 12:54 — Page xvii — #3

Listings xvii

6.1 Serial implementation of gather in pseudocode . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 180

6.2 Serial implementation of scatter in pseudocode . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... 186

6.3 Array of structures (AoS) data organization .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . 194

6.4 Structure of arrays (SoA) data organization ... . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 195

7.1 Serial implementation of stencil . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . . 200

7.2 Serial 2D recurrence . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . 205

8.1 Recursive implementation of the map pattern in Cilk Plus .... . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . 215

8.2 Modiﬁcation of Listing 8.1 that changes tail call into a goto .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . 217

8.3 Cleaned-up semi-recursive map in Cilk Plus . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 217

8.4 Three loop forms illustrating steal-continuation versus steal-child . . . .. . . . .. . . . .. . . . .. . . . .. . . 219

8.5 Flat algorithm for polynomial multiplication using Cilk Plus array notation . . .. . . . .. . . . .. . . . 224

8.6 Karatsuba multiplication in Cilk Plus . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 225

8.7 Type for scratch space . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 227

8.8 Pseudocode for recursive matrix multiplication ... . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . 229

8.9 Code shared by Quicksort implementations . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . 232

8.10 Fully recursive parallel Quicksort using Cilk Plus . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . .. 233

8.11 Semi-recursive parallel Quicksort using Cilk Plus ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 234

8.12 Semi-iterative parallel Quicksort using TBB . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . . 235

8.13 Quicksort in TBB that achieves Cilk Plus space guarantee .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . 236

8.14 Recursive implementation of parallel reduction in Cilk Plus . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . 238

8.15 Using a hyperobject to avoid a race in Cilk Plus . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 239

8.16 Using a local reducer in Cilk Plus .... . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 241

8.17 Top-level code for tiled parallel scan.... . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 243

8.18 Upsweep phase for tiled parallel scan in Cilk Plus . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 244

8.19 Downsweep phase for tiled parallel scan in Cilk Plus. . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 244

8.20 Implementing pack pattern with cilk_scan from Listing 8.17 ... . . ... . . ... . . .. . . . .. . . . .. . . . 245

8.21 Base case for evaluating a diamond of lattice points . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 249

8.22 Code for parallel recursive evaluation of binomial lattice in Cilk Plus. . ... . . .. . . . .. . . . .. . . . .. 250

8.23 Marching over diamonds in Cilk Plus. . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 251

9.1 Serial implementation of a pipeline . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . . 257

9.2 Pipeline in TBB . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . .. 258

9.3 Pipeline in Cilk Plus equivalent to the serial pipeline in Listing 9.1 . .. . . ... . . .. . . . .. . . . .. . . . . 259

9.4 Deﬁning a reducer for serializing consumption of items in Cilk Plus . . .. . . . .. . . . .. . . . .. . . . .. . 260

10.1 Serial code for simulating waveﬁeld .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . . 268

10.2 Code for one-dimensional iterated stencil ... . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 271

10.3 Base case for applying stencil to space–time trapezoid .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . . 273

10.4 Parallel cache-oblivious trapezoid decomposition in Cilk Plus .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . 274

10.5 ArBB code for simulating a waveﬁeld . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 276

To protect the rights of the author(s) and publisher we inform you that this PDF is an uncorrected proof for internal business use only by the author(s), editor(s),

reviewer(s), Elsevier and typesetter diacriTech. It is not allowed to publish this proof online or in print. This proof copy is the copyright property of the publisher

and is conﬁdential until formal publication.

McCool — 03-lol-xv-xviii-9780124159938 — 2012/6/6 — 12:54 — Page xviii — #4

xviii Listings

11.1 K-means clustering in Cilk Plus . . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 282

11.2 Type sum_and_count for computing mean of points in a cluster . . . . .. . . . .. . . . .. . . . .. . . ... . . 283

11.3 Deﬁning a hyperobject for summing an array elementwise in Cilk Plus . . . .. . . . .. . . . .. . . . .. . . 284

11.4 Declaring a type tls_type for thread-local views in TBB . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 285

11.5 Walking local views to detect changes . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . . 286

11.6 Walking local views to accumulate a global sum... . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 286

11.7 Routine for ﬁnding index of centroid closest to a given point . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . 287

11.8 K-means clustering in TBB . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . 288

12.1 Declarations for bzip2 pipeline .... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . . 294

12.2 Use of TBB parallel_pipeline to coordinate bzip2 actions . ... . . .. . . . .. . . . .. . . . .. . . . .. . . 295

12.3 Sketch of bzip2 pipeline in Cilk Plus using a consumer reducer ... . . . .. . . . .. . . ... . . ... . . .. . . . 297

13.1 Serial merge . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. 300

13.2 Parallel merge in Cilk Plus ... . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . 301

13.3 Converting parallel merge from Cilk Plus to TBB . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . 302

13.4 Parallel merge sort in Cilk Plus. .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . . 304

14.1 Top-level code for parallel sample sort ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... 308

14.2 Code for mapping keys to bins . .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . 310

14.3 Parallel binning of keys using Cilk Plus . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . . 311

14.4 Repacking and subsorting using Cilk Plus . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 312

14.5 Using Cilk Plus to move and destroy a sequence, without an explicit loop! . . .. . . . .. . . . .. . . .. 313

15.1 Recursive Cholesky decomposition . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . 318

15.2 Parallel triangular solve in Cilk Plus . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . 320

15.3 Parallel symmetric rank update in Cilk Plus . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . . 321

15.4 Converting parallel symmetric rank update from Cilk Plus to TBB .. . . . .. . . . .. . . . .. . . . .. . . ... 322

B.1 Simple example use of cilk_for ... . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 332

B.2 Examples of using cilk_spawn and cilk_sync .. . . . .. . . . .. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . . 333

B.3 Serial reduction in C++ and equivalent Cilk Plus code . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . 336

B.4 Serial reduction in C and equivalent Cilk Plus code .... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 338

B.5 Example of using __sec_reduce to reduce over string concatenation ... . . . .. . . . .. . . ... . . .. 342

B.6 Deﬁning an elemental function ... . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . 344

B.7 Calling an elemental function from a vectorizable loop... . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . 345

C.1 Example of affinity_partitioner . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . 353

C.2 Using task_group . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . 355

C.3 Example of using atomic<int> as a counter . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . 356

C.4 Using atomic operations on a list. . . . .. . . . .. . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . 357

D.1 Using a manually written functor comparator .... . . ... . . ... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 362

D.2 Using a lambda expression lets Listing D.1 be rewritten more concisely . . . . .. . . . .. . . . .. . . . .. 363

D.3 Mixed capture with handwritten functor . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . 364

D.4 Mixed capture modes.... . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . ... . . .. . . . .. . . . .. . . . .. 364

To protect the rights of the author(s) and publisher we inform you that this PDF is an uncorrected proof for internal business use only by the author(s), editor(s),

reviewer(s), Elsevier and typesetter diacriTech. It is not allowed to publish this proof online or in print. This proof copy is the copyright property of the publisher

and is conﬁdential until formal publication.

McCool — 04-pre-xix-xxii-9780124159938 — 2012/6/6 — 22:35 — Page xix — #1

Preface

All computers are now parallel computers, so we assert that all programmers are, or should be, parallel

programmers. With parallel programming now mainstream, it simply needs to be included in the def-

inition of “programming” and be part of the skill set of all software developers. Unfortunately, many

existing texts on parallel programming are overspecialized, with too much emphasis given to particular

programming models or particular computer architectures. At the other extreme, several existing texts

approach parallel computing as an abstract ﬁeld of study and provide the reader with insufﬁcient infor-

mation to actually write real applications. We saw a need for a text on parallel programming treating

the topic in a mainstream, pragmatic fashion, so that readers can immediately use it to write real appli-

cations, but at a level of abstraction that still spans multiple computer architectures and programming

models.

We feel that teaching parallel programming as an advanced topic, with serial programming as the

default basis, is not the best approach. Parallel programming should be taught from the beginning to

avoid over-learning of serial assumptions and thought patterns. Unfortunately, at present the default

teaching style is based on the serial code and algorithms. Serialization has become excessively woven

into our teaching, our programs, and even the tools of our trade: our programming languages. As a

result, for many programmers parallel programming seems more difﬁcult than it should be. Many pro-

grams are serial not because it was natural to solve the problem serially, but because the programming

tools demanded it and the programmer was trained to think that way.

Despite the fact that computer hardware is naturally parallel, computer architects chose 40 years ago

to present a serial programming abstraction to programmers. Decades of work in computer architecture

have focused on maintaining the illusion of serial execution. Extensive efforts are made inside modern

processors to translate serial programs into a parallel form so they can execute efﬁciently using the

ﬁne-grained parallel hardware inside the processor. Unfortunately, driven by the exponential increase

in the number of transistors provided by Moore’s Law, the need for parallelism is now so great that it

is no longer possible to maintain the serial illusion while continuing to scale performance. It is now

necessary for programmers to explicitly specify parallel algorithms if they want their performance to

scale. Parallelism is everywhere, and it is the path to performance on modern computer architectures.

Parallelism, even within a single desktop (or laptop!) computer, is available in many ways, including

vector (SIMD) instructions, multicore processors, GPUs, co-processors, and many-core processors.

Programming today needs to address all these forms of hardware parallelism in a manner that is abstract

enough to avoid limiting the implementation to a particular style of hardware.

We also saw a need for a structured approach to parallel programming. In this book, we explain and

illustrate essential strategies needed for writing efﬁcient, scalable programs using a set of patterns. We

have found that patterns are highly effective both for learning this subject and for designing efﬁcient,

structured, and maintainable programs. Using standard names for patterns is also a tremendous aid

to communication. Because vocabulary is important, we have assembled an extensive glossary. This

should help limit the need to read the book sequentially. The glossary also points to key discussions or

explanations of a term within a section of the book when appropriate.

To ensure that the book is useful in practice, we combine patterns with a set of examples showing

their use. Since there are many parallel programming models, the question arose: Which programming

model(s) should we use for examples? We wanted to show enough examples to allow the reader to write

xix

剩余432页未读，继续阅读

lcljesse

粉丝: 0
资源: 2

高效计算模式：结构化并行编程

Structured Parallel Programming - Patterns for Efficient

Structured Parallel Programming Patterns for Efficient Computation 无水印pdf

structured parallel programming

What are the most significant differences among structured, object-oriented, and agile methods? What do they have in common?

spark(55) -- structuredstreaming -- continuous processing

编程语言中有哪些常用的英文单词缩写？

请分别说明C++11中的range-based for循环，结构化绑定（structured bindings）和引用折叠（reference collapsing）特性

说出至少6个Hadoop生态系统组件 及其作用

a structured self-attentive sentence embedding

最新资源

说出至少6个Hadoop生态系统组件及其作用