Reinders / Jeffers High Performance Parallelism Pearls Volume One

Multicore and Many-core Programming Approaches
1. Auflage 2014
ISBN: 978-0-12-802199-6
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, 600 Seiten

High Performance Parallelism Pearls shows how to leverage parallelism on processors and coprocessors with the same programming - illustrating the most effective ways to better tap the computational potential of systems with Intel Xeon Phi coprocessors and Intel Xeon processors or other multicore processors. The book includes examples of successful programming efforts, drawn from across industries and domains such as chemistry, engineering, and environmental science. Each chapter in this edited work includes detailed explanations of the programming techniques used, while showing high performance results on both Intel Xeon Phi coprocessors and multicore processors. Learn from dozens of new examples and case studies illustrating 'success stories' demonstrating not just the features of these powerful systems, but also how to leverage parallelism across these heterogeneous systems. - Promotes consistent standards-based programming, showing in detail how to code for high performance on multicore processors and Intel® Xeon Phi? - Examples from multiple vertical domains illustrating parallel optimizations to modernize real-world codes - Source code available for download to facilitate further exploration

James Reinders is a senior engineer who joined Intel Corporation in 1989 and has contributed to projects including the world's first TeraFLOP supercomputer (ASCI Red), as well as compilers and architecture work for a number of Intel processors and parallel systems. James has been a driver behind the development of Intel as a major provider of software development products, and serves as their chief software evangelist. James has published numerous articles, contributed to several books and is widely interviewed on parallelism. James has managed software development groups, customer service and consulting teams, business development and marketing teams. James is sought after to keynote on parallel programming, and is the author/co-author of three books currently in print including Structured Parallel Programming, published by Morgan Kaufmann in 2012.

Autoren/Hrsg.

Reinders, James

Jeffers, James

Inhaltsverzeichnis

1;Front Cover;1
2;High Performance Parallelism Pearls: Multicore and Many-core Programming Approaches;4
3;Copyright;5
4;Contents;6
5;Contributors;16
6;Acknowledgments;40
7;Foreword;42
7.1;Humongous computing needs: Science years in the making;42
7.2;Open standards;42
7.3;Keen on many-core architecture;42
7.4;Xeon Phi is born: Many cores, excellent vector ISA ;43
7.5;Learn highly scalable parallel programming;44
7.6;Future demands grow: Programming models matter;44
8;Preface;46
8.1;Inspired by 61 cores: A new era in programming;46
9;Chapter 1: Introduction;48
9.1;Learning from successful experiences;48
9.2;Code modernization;48
9.3;Modernize with concurrent algorithms;49
9.4;Modernize with vectorization and data locality;49
9.5;Understanding power usage;49
9.6;ISPC and OpenCL anyone?;49
9.7;Intel Xeon Phi coprocessor specific;50
9.8;Many-core, neo-heterogeneous;50
9.9;No “Xeon Phi” in the title, neo-heterogeneous programming;50
9.10;The future of many-core;51
9.11;Downloads;51
10;Chapter 2: From “Correct” to “Correct & Efficient”: A Hydro2D Case Study with Godunov’s Scheme;54
10.1;Scientific computing on contemporary computers;54
10.1.1;Modern computing environments;55
10.1.2;CEA’s Hydro2D;56
10.2;A numerical method for shock hydrodynamics;56
10.2.1;Euler’s equation;57
10.2.2;Godunov’s method;57
10.2.3;Where it fits;59
10.3;Features of modern architectures;60
10.3.1;Performance-oriented architecture;60
10.3.2;Programming tools and runtimes;61
10.3.3;Our computing environments;61
10.4;Paths to performance;62
10.4.1;Running Hydro2D;62
10.4.2;Hydro2D’s structure;62
10.4.2.1;Computation scheme;64
10.4.2.2;Data structures;64
10.4.2.3;Measuring performance;67
10.4.3;Optimizations;67
10.4.4;Memory usage;68
10.4.5;Thread-level parallelism;69
10.4.6;Arithmetic efficiency and instruction-level parallelism;77
10.4.7;Data-level parallelism;79
10.5;Summary;86
10.5.1;The coprocessor vs the processor;86
10.5.2;A rising tide lifts all boats;86
10.5.3;Performance strategies;88
11;Chapter 3: Better Concurrency and SIMD on HBM ;90
11.1;The application: HIROMB - BOOS -Model;90
11.2;Key usage: DMI ;91
11.3;HBM execution profile;91
11.4;Overview for the optimization of HBM ;92
11.5;Data structures: Locality done right;93
11.6;Thread parallelism in HBM ;97
11.7;Data parallelism: SIMD vectorization;102
11.7.1;Trivial obstacles;102
11.7.2;Premature abstraction is the root of all evil;105
11.8;Results;108
11.9;Profiling details;109
11.10;Scaling on processor vs. coprocessor;109
11.11;Contiguous attribute;111
11.12;Summary;113
11.13;References;113
12;Chapter 4: Optimizing for Reacting Navier-Stokes Equations;116
12.1;Getting started;116
12.2;Version 1.0: Baseline;117
12.3;Version 2.0: ThreadBox ;120
12.4;Version 3.0: Stack memory;124
12.5;Version 4.0: Blocking;124
12.6;Version 5.0: Vectorization;127
12.7;Intel Xeon Phi coprocessor results;130
12.8;Summary;131
13;Chapter 5: Plesiochronous Phasing Barriers;134
13.1;What can be done to improve the code?;136
13.2;What more can be done to improve the code?;138
13.3;Hyper-Thread Phalanx;138
13.4;What is nonoptimal about this strategy?;140
13.5;Coding the Hyper-Thread Phalanx;140
13.5.1;How to determine thread binding to core and HT within core?;141
13.5.2;The Hyper-Thread Phalanx hand-partitioning technique;142
13.5.3;A lesson learned;144
13.6;Back to work;146
13.7;Data alignment;146
13.7.1;Use aligned data when possible;147
13.7.2;Redundancy can be good for you;147
13.8;The plesiochronous phasing barrier;150
13.9;Let us do something to recover this wasted time;152
13.10;A few “left to the reader” possibilities;156
13.11;Xeon host performance improvements similar to Xeon Phi;157
13.12;Summary;162
14;Chapter 6: Parallel Evaluation of Fault Tree Expressions;164
14.1;Motivation and background;164
14.1.1;Expressions;164
14.1.2;Expression of choice: Fault trees;164
14.1.3;An application for fault trees: Ballistic simulation;165
14.2;Example implementation;165
14.2.1;Syntax and parsing results;166
14.2.2;Creating evaluation arrays;166
14.2.3;Evaluating the expression array;168
14.2.4;Using ispc for vectorization;168
14.3;Other considerations;173
14.4;Summary;175
15;Chapter 7: Deep-Learning Numerical Optimization;176
15.1;Fitting an objective function;176
15.2;Objective functions and principle components analysis;181
15.3;Software and example data;182
15.4;Training data;183
15.5;Runtime results;186
15.6;Scaling results;188
15.7;Summary;188
16;Chapter 8: Optimizing Gather/Scatter Patterns;190
16.1;Gather/scatter instructions in Intel® architecture;192
16.2;Gather/scatter patterns in molecular dynamics;192
16.3;Optimizing gather/scatter patterns;195
16.3.1;Improving temporal and spatial locality;195
16.3.2;Choosing an appropriate data layout: AoS versus SoA ;197
16.3.3;On-the-fly transposition between AoS and SoA ;198
16.3.4;Amortizing gather/scatter and transposition costs;201
16.4;Summary;203
17;Chapter 9: A Many-Core Implementation of the Direct N-Body Problem;206
17.1;N-Body simulations;206
17.2;Initial solution;206
17.3;Theoretical limit;209
17.4;Reduce the overheads, align your data;211
17.5;Optimize the memory hierarchy;214
17.6;Improving our tiling;217
17.7;What does all this mean to the host version?;219
17.8;Summary;221
18;Chapter 10: N -Body Methods;222
18.1;Fast N -body methods and direct N -body kernels;222
18.2;Applications of N -body methods;223
18.3;Direct N -body code;224
18.4;Performance results;226
18.5;Summary;229
19;Chapter 11: Dynamic Load Balancing Using OpenMP 4.0;232
19.1;Maximizing hardware usage;232
19.2;The N-Body kernel;234
19.3;The offloaded version;238
19.4;A first processor combined with coprocessor version;240
19.5;Version for processor with multiple coprocessors;243
20;Chapter 12: Concurrent Kernel Offloading;248
20.1;Setting the context;248
20.1.1;Motivating example: particle dynamics;249
20.1.2;Organization of this chapter;250
20.2;Concurrent kernels on the coprocessor;251
20.2.1;Coprocessor device partitioning and thread affinity;251
20.2.1.1;Offloading from OpenMP host program;252
20.2.1.2;Offloading from MPI host program;254
20.2.1.3;Case study: concurrent Intel MKL dgemm offloading;255
20.2.1.4;Persistent thread groups and affinities on the coprocessor;257
20.2.2;Concurrent data transfers;257
20.2.2.1;Case study: concurrent MKL dgemm offloading with data transfers;258
20.3;Force computation in PD using concurrent kernel offloading;260
20.3.1;Parallel force evaluation using Newton’s 3rd law;260
20.3.2;Implementation of the concurrent force computation;262
20.3.3;Performance evaluation: before and after;267
20.4;The bottom line;268
21;Chapter 13. Heterogeneous Computing with MPI ;272
21.1;MPI in the modern clusters;272
21.2;MPI task location;273
21.2.1;Single-task hybrid programs;276
21.3;Selection of the DAPL providers;278
21.3.1;The first provider ofa-v2-mlx4_0-1u ;278
21.3.2;The second provider ofa-v2-scif0 and the impact of the intra-node fabric;279
21.3.3;The last provider, also called the proxy;279
21.3.4;Hybrid application scalability;281
21.3.5;Load balance;283
21.3.6;Task and thread mapping;283
21.4;Summary;284
21.5;Acknowledgments;285
22;Chapter 14: Power Analysis on the Intel® Xeon Phi™ Coprocessor;286
22.1;Power analysis 101;286
22.2;Measuring power and temperature with software;288
22.2.1;Creating a power and temperature monitor script;290
22.2.2;Creating a power and temperature logger with the micsmc tool;290
22.2.3;Power analysis using IPMI ;292
22.3;Hardware-based power analysis methods;293
22.3.1;A hardware-based coprocessor power analyzer;296
22.4;Summary;299
23;Chapter 15: Integrating Intel Xeon Phi Coprocessors into a Cluster Environment;302
23.1;Early explorations;302
23.2;Beacon system history;303
23.3;Beacon system architecture;303
23.3.1;Hardware;303
23.3.2;Software environment;303
23.4;Intel MPSS installation procedure;305
23.4.1;Preparing the system;305
23.4.2;Installation of the Intel MPSS stack;306
23.4.3;Generating and customizing configuration files;308
23.4.4;MPSS upgrade procedure;312
23.5;Setting up the resource and workload managers;312
23.5.1;Torque ;312
23.5.2;Prologue;313
23.5.3;Epilogue;315
23.5.4;TORQUE /coprocessor integration;315
23.5.5;Moab;316
23.5.6;Improving network locality;316
23.5.7;Moab/coprocessor integration;316
23.6;Health checking and monitoring;316
23.7;Scripting common commands;318
23.8;User software environment;320
23.9;Future directions;321
23.10;Summary;322
23.11;Acknowledgments;322
24;Chapter 16: Supporting Cluster File Systems on Intel® Xeon Phi™ Coprocessors;324
24.1;Network configuration concepts and goals;325
24.1.1;A look at networking options;325
24.1.2;Steps to set up a cluster enabled coprocessor;327
24.2;Coprocessor file systems support;328
24.2.1;Support for NFS ;329
24.2.2;Support for Lustre® file system;329
24.2.3;Support for Fraunhofer BeeGFS ® (formerly FHGFS) file system;331
24.2.4;Support for Panasas® PanFS ® file system;332
24.2.5;Choosing a cluster file system;332
24.3;Summary;332
25;Chapter 17. NWChem: Quantum Chemistry Simulations at Scale;334
25.1;Introduction;334
25.2;Overview of single-reference CC formalism;335
25.3;NWChem software architecture;338
25.3.1;Global Arrays;338
25.3.2;Tensor Contraction Engine;339
25.4;Engineering an offload solution;340
25.5;Offload architecture;344
25.6;Kernel optimizations;345
25.7;Performance evaluation;348
25.8;Summary;351
25.9;Acknowledgments;352
26;Chapter 18: Efficient Nested Parallelism on Large-Scale Systems;354
26.1;Motivation;354
26.2;The benchmark;354
26.3;Baseline benchmarking;356
26.4;Pipeline approach—flat_arena class;357
26.5;Intel® TBB user-managed task arenas;358
26.6;Hierarchical approach—hierarchical_arena class;360
26.7;Performance evaluation;361
26.8;Implication on NUMA architectures;363
26.9;Summary;364
27;Chapter 19: Performance Optimization of Black-Scholes Pricing;366
27.1;Financial market model basics and the Black-Scholes formula;367
27.1.1;Financial market mathematical model;367
27.1.2;European option and fair price concepts;368
27.1.3;Black-Scholes formula;369
27.1.4;Options pricing;369
27.1.5;Test infrastructure;370
27.2;Case study;370
27.2.1;Preliminary version—Checking correctness;370
27.2.2;Reference version—Choose appropriate data structures;370
27.2.3;Reference version—Do not mix data types;372
27.2.4;Vectorize loops;373
27.2.5;Use fast math functions: erff() vs. cdfnormf();376
27.2.6;Equivalent transformations of code;378
27.2.7;Align arrays;378
27.2.8;Reduce precision if possible;380
27.2.9;Work in parallel;381
27.2.10;Use warm-up;381
27.2.11;Using the Intel Xeon Phi coprocessor—“No effort” port;383
27.2.12;Use Intel Xeon Phi coprocessor: Work in parallel;384
27.2.13;Use Intel Xeon Phi coprocessor and streaming stores;385
27.3;Summary;385
28;Chapter 20: Data Transfer Using the Intel COI Library;388
28.1;First steps with the Intel COI library;388
28.2;COI buffer types and transfer performance;389
28.3;Applications;393
28.4;Summary;395
29;Chapter 21: High-Performance Ray Tracing;396
29.1;Background;396
29.2;Vectorizing ray traversal;398
29.3;The Embree ray tracing kernels;399
29.4;Using Embree in an application;399
29.5;Performance;401
29.6;Summary;404
30;Chapter 22: Portable Performance with OpenCL ;406
30.1;The dilemma;406
30.2;A brief introduction to OpenCL ;407
30.3;A matrix multiply example in OpenCL ;411
30.4;OpenCL and the Intel Xeon Phi Coprocessor;413
30.5;Matrix multiply performance results;415
30.6;Case study: Molecular docking;416
30.7;Results: Portable performance;420
30.8;Related work;421
30.9;Summary;422
31;Chapter 23: Characterization and Optimization Methodology Applied to Stencil Computations;424
31.1;Introduction;424
31.2;Performance evaluation;425
31.2.1;AI of the test platforms;426
31.2.2;AI of the kernel;427
31.3;Standard optimizations;429
31.3.1;Automatic application tuning;433
31.3.2;The auto-tuning tool;439
31.3.3;Results;440
31.4;Summary;442
32;Chapter 24: Profiling-Guided Optimization;444
32.1;Matrix transposition in computer science;444
32.2;Tools and methods;446
32.3;"Serial”: Our original in-place transposition;447
32.4;"Parallel”: Adding parallelism with OpenMP ;452
32.5;"Tiled”: Improving data locality;452
32.6;"Regularized”: Microkernel with multiversioning;458
32.7;"Planned”: Exposing more parallelism;464
32.8;Summary;468
33;Chapter 25: Heterogeneous MPI application optimization with ITAC ;472
33.1;Asian options pricing;472
33.2;Application design;473
33.3;Synchronization in heterogeneous clusters;475
33.4;Finding bottlenecks with ITAC ;476
33.5;Setting up ITAC ;477
33.6;Unbalanced MPI run;478
33.7;Manual workload balance;481
33.8;Dynamic “Boss-Workers” load balancing;483
33.9;Conclusion;486
34;Chapter 26: Scalable Out-of-Core Solvers on a Cluster;490
34.1;Introduction;490
34.2;An OOC factorization based on ScaLAPACK;491
34.2.1;In-core factorization;492
34.2.2;OOC factorization;493
34.3;Porting from NVIDIA GPU to the Intel Xeon Phi coprocessor;494
34.4;Numerical results;496
34.5;Conclusions and future work;501
34.6;Acknowledgments;501
35;Chapter 27: Sparse Matrix-Vector Multiplication: Parallelization and Vectorization;504
35.1;Background;504
35.2;Sparse matrix data structures;505
35.3;Algorithm 1:. COO- based S p MV multiplication ;505
35.3.1;Compressed data structures;506
35.3.2;Algorithm 2:. CRS- based S p MV multiplication ;507
35.3.3;Algorithm 3:. BICRS- based S p MV multiplication ;508
35.3.4;Blocking;509
35.4;Parallel SpMV multiplication;509
35.4.1;Partially distributed parallel SpMV;509
35.4.2;Algorithm 4:. P artially distributed parallel S p MV multiplication ;510
35.4.3;Fully distributed parallel SpMV;510
35.5;Vectorization on the Intel Xeon Phi coprocessor;512
35.5.1;Implementation of the vectorized SpMV kernel;514
35.6;Evaluation;517
35.6.1;On the Intel Xeon Phi coprocessor;518
35.6.2;On Intel Xeon CPUs;519
35.6.3;Performance comparison;521
35.7;Summary;521
36;Chapter 28: Morton Order Improves Performance;524
36.1;Improving cache locality by data ordering;524
36.2;Improving performance;524
36.3;Matrix transpose;525
36.4;Matrix multiply;529
36.5;Summary;535
37;Author Index;538
38;Subject Index;542

Leseproben

Contributors
Mustafa AbdulJabbar     King Abdullah University of Science and Technology, Saudi Arabia
Mustafa is a PhD candidate in the Extreme Computing Research Center at KAUST. He works on optimization of high-scale algorithms such as FMM and is interested in closing the gap between RMI-based execution models and real applications in molecular dynamics and fluid mechanics. Jefferson Amstutz     SURVICE Engineering Company, USA
Jefferson is a Software Engineer in the Applied Technology Operation of SURVICE. He explores interactive visualization and high-performance computing in support of applications for the Army Research Laboratory; he works to solve a variety of physics-based simulation problems in domains such as ballistic vulnerability analysis, radio frequency propagation, and soft-body simulation. Cédric Andreolli     Intel Corporation, France
Cédric is an application engineer in the Energy team at Intel Corporation. He helps optimize applications running on Intel platforms for the Oil and Gas industry. Edoardo Aprà     Pacific Northwest National Laboratory, USA
Edoardo is a Chief Scientist at the Environmental Molecular Sciences Laboratory within PNNL. His research focus is on high-performance computational algorithm and software development especially for chemical applications. He is the main developer of the molecular density functional theory (DFT) module in the NWChem package. Nikita Astafiev     Intel Corporation, Russia
Nikita is a senior software engineer in the Numerics team at Intel. He works on highly optimized math functions. His key areas of interest include automated floating-point error analysis and low-level optimizations. Troy Baer     National Institute for Computational Sciences, The University of Tennessee and Oak Ridge National Laboratory, USA
Troy leads the HPC systems team for the NICS Systems and Operations group. He has been involved large system deployments including Beacon, Nautilus, and Kraken. In April 2014, Troy received the Adaptive Computing Lifetime Achievement award for contributions in scheduling and resource management using Moab. Carsten Benthin     Intel Corporation, Germany
Carsten is a Graphics Research Scientist at Intel Corporation. His research interests include all aspects of ray tracing and high-performance rendering, throughput and high-performance computing, low-level code optimization, and massively parallel hardware architectures. Per Berg     Danish Meteorological Institute, Denmark
Per applies his mathematical modeling and scientific computing education to develop modeling software for applications in water environments (estuaries, ocean). Working for both private companies and public institutes, Per has been involved in numerous projects that apply models to solve engineering and scientific problems. Vincent Betro     National Institute for Computational Sciences, The University of Tennessee and Oak Ridge National Laboratory, USA
Vincent focuses his research on porting and optimizing applications for several architectures, especially the Intel Xeon Phi, and developing Computational Fluid Dynamics codes. He is also the training manager for the XSEDE project, and he has emphasized Xeon Phi Coprocessor training material development for Stampede and Beacon in this role. Leonardo Borges     Intel Corporation, USA
Leo is a Senior Staff Engineer and has been engaged with the Intel Many Integrated Core program from its early days. He specializes in HPC applying his background in numerical analysis and in developing parallel numerical math libraries. Leo is focused on optimization work related to the Oil & Gas industry. Ryan Braby     Joint Institute for Computational Sciences, The University of Tennessee and Oak Ridge National Laboratory, USA
Ryan is the Chief Cyberinfrastructure Officer for JICS. Ryan has been directly involved in the administration and/or deployment of 2 systems that ranked #1 on the Top 500 list, one system that ranked #1 on the Green 500 list, and 18 systems that were ranked in the top 50 on the Top 500 list. Glenn Brook     Joint Institute for Computational Sciences, The University of Tennessee and Oak Ridge National Laboratory, USA
Glenn currently directs the Application Acceleration Center of Excellence (AACE) and serves as the Chief Technology Officer at JICS. He is the principal investigator for the Beacon Project, which is funded by NSF and UT to explore the impact of emerging computing technologies such as the Intel Xeon Phi coprocessor on computational science and engineering. Ilya Burylov     Intel Corporation, Russia
Ilya is a senior software engineer in the Numerics team at Intel Corporation. His background is in computation optimizations for statistical, financial, and transcendental math functions algorithms. Ilya focuses on optimization of computationally intensive analytics algorithms and data manipulation steps for Big Data workflows within distributed systems. Ki Sing Chan     The Chinese University of Hong Kong, Hong Kong
Ki Sing is an undergraduate student at the Chinese University of Hong Kong majoring in Mathematics and Information Engineering with a minor in Computer Science. His first research experience took place in the Oak Ridge National Laboratory in Tennessee during the summer break in 2013. His research focuses on the implementation of a Cholesky Factorization algorithm for large dense matrix. Gilles Civario     Irish Centre for High-End Computing (ICHEC), Ireland
Gilles is a Senior Software Architect focused on designing and implementing tailored hardware and software solutions to users of the National Service and to ICHEC’s technology transfer client companies. Guillaume Colin de Verdière     Commissariat à l’Energie Atomique et aux Energies Alternatives (CEA), France
Guillaume is a senior expert at CEA. His current focus is on novel architectures especially the Intel Xeon Phi, a very promising technology that might potentially get us to an exascale machine. As a direct consequence of this focus, he is actively studying the impact of such novel technologies on legacy code evolution. Eduardo D’Azevedo     Computational Mathematics Group at the Oak Ridge National Laboratory, USA
Eduardo is a staff scientist with research interests that include developing highly scalable parallel solvers. He contributes to projects in materials science and fusion in the Scientific Discovery through Advanced Computing (SciDAC) program. He has developed out-of-core and compact storage extensions for the ScaLAPACK library and made fundamental contributions in optimal mesh generation. Jim Dempsey     QuickThread Programming, LLC, USA
Jim is a consultant specializing in high-performance computing (HPC) and optimization of embedded systems. Jim is the President of QuickThread Programming, LLC. Jim’s expertise includes high efficiency programming and optimization for Intel Xeon and Intel Xeon Phi processors. Alejandro Duran     Intel Corporation, Spain
Alejandro is an Application Engineer working with customers to help optimize their codes. He has been part of the OpenMP Language committee since 2005. Manfred Ernst     Intel Corporation, now at Google Incorporated, USA
Manfred is a member of the Chromium team at Google. Prior to joining Google, he was a Research Scientist at Intel Labs, where he developed the Embree Ray Tracing Kernels. His primary research interests are photorealistic rendering, acceleration structures for ray tracing, sampling, and data compression. Kerry Evans     Intel Corporation, USA
Kerry is a software engineer working primarily with customers on optimization of medical imaging software on Intel Xeon processors and Intel Xeon Phi coprocessors. Rob Farber     TechEnablement.com, USA
Rob is a consultant with an extensive background in HPC and a long history of...