book

High Performance Parallel Runtimes

Name: High Performance Parallel Runtimes
ISBN: 9783110632897

by Michael Klemm, Jim Cownie

February 2021

Intermediate to advanced

356 pages

10h 55m

English

De Gruyter Oldenbourg

Read now

Unlock full access

1 Setting the stage
1.1 Structure of the book1.2 Design space exploration1.2.1 Parallelism as a library1.2.2 Parallelism as a language1.3 Code samples1.4 Machine configurations
2 Parallel programming models and concepts
2.1 Multi-processing and multi-threading2.1.1 Threading basics2.1.2 Thread affinity2.1.3 The OpenMP API for thread-based programming2.1.4 Worksharing2.1.5 OpenMP thread affinity2.2 Task-based parallel programming2.3 Synchronization constructs2.3.1 Mutual exclusion with locks2.3.2 Barriers, reductions, and latches2.3.3 Task barriers2.3.4 Task dependences2.4 Amdahl’s law2.4.1 Presenting performance results2.4.2 Effect on performance2.4.3 Mapping overheads to Amdahl2.4.4 Other variants of Amdahl’s law2.5 Conclusions
3 Many-core and multi-core computer architectures
3.1 Execution mechanisms3.1.1 Von Neumann architecture and in-order execution3.1.2 In-order pipelined execution3.1.3 Out-of-order execution3.1.4 Branch prediction3.1.5 Superscalar execution3.1.6 Simultaneous multi-threading3.1.7 Single-instruction multiple-data3.2 The modern memory subsystem3.2.1 Memory hierarchy3.2.2 Memory models and memory consistency3.2.3 Caches3.2.4 Cache coherence: overview3.2.5 Cache coherence: the MESI protocol3.2.6 Performance implications3.2.7 Non-uniform memory architectures3.3 Conclusions
4 Compiler and runtime interaction
4.1 Compiler basics4.2 Implementing a task-based parallel model4.2.1 Lambda functions and closures4.2.2 Enqueuing tasks in TBB4.3 Compilers for parallel programming languages4.4 Parallel code-generation patterns4.4.1 Code generation for parallel regions4.4.2 Code generation for thread-parallel loops4.4.3 Code generation for SIMD-parallel loops4.4.4 Code generation for sequential constructs4.4.5 Code generation for static tasking4.4.6 Code generation for dynamic tasking4.5 Example OpenMP implementations4.5.1 GNU compiler collection4.5.2 Intel compilers and the LLVM compiler4.6 Conclusions
5 Fundamental parallel runtime mechanisms
5.1 Managing parallelism5.1.1 Spawning parallelism5.1.2 Waiting5.2 Management of parallelism and hardware structure5.2.1 Detecting the hardware structure5.2.2 Thread pinning5.3 Memory management in parallel runtime systems5.3.1 Memory efficiency and cache usage5.3.2 Single-threaded memory allocators5.3.3 Multi-threaded memory allocators5.3.4 Specialized memory allocators for parallel runtime systems5.3.5 Thread-local storage5.3.6 Data layout of the thread objects5.4 Conclusions
6 Mutual exclusion and atomicity
6.1 The mutual exclusion problem6.1.1 Hardware support for locks: atomic instructions6.1.2 The ABA problem6.2 Should we be writing locking code?6.3 Classes of locks6.4 Properties of lock algorithms6.4.1 Lock-performance metrics6.5 Lock algorithms6.5.1 Test-and-Set locks6.5.2 Test and Test-and-Set locks6.5.3 Ticket lock6.5.4 Queuing locks6.6 Actual code performance6.6.1 Uncontended lock overhead6.6.2 Contended lock throughput6.6.3 Performance conclusions6.7 How to wait6.7.1 Backoff strategies6.8 Transactional synchronization6.8.1 Transactional semantics6.8.2 Implementation in the MESI protocol6.8.3 Transactional instructions6.8.4 Transactional locks6.8.5 Comparison of mutual exclusion and speculation6.9 Other serializing operations6.9.1 The master and masked constructs6.9.2 The single construct6.10 Atomic operations6.10.1 Mapping of atomic instructions6.10.2 Atomic implementation of minimum and maximum6.11 Conclusions6.11.1 Conclusions: locks6.11.2 Conclusions: atomic operations
7 Barriers and reductions
7.1 Barrier fundamentals7.2 Barrier performance measurement7.2.1 Barrier micro-benchmark7.2.2 Barrier performance modeling7.3 Barrier components7.3.1 Counters and flags7.3.2 Broadcast7.4 Categorization of barrier algorithms7.5 Barrier algorithms7.5.1 Counting barrier7.5.2 All-to-All barrier7.5.3 Butterfly/hypercube barrier7.5.4 Dissemination barrier7.5.5 Tree check-in barriers7.6 Reductions7.6.1 Piggy-backing reductions7.7 Additional optimizations7.7.1 Hierarchical barriers7.8 Conclusions
8 Scheduling parallel loops
8.1 Aims of scheduling8.2 Theoretical limits on scheduling efficiency8.3 Fundamental scheduling approaches8.3.1 Static loop scheduling8.3.2 Dynamic loop scheduling8.4 Mapping to canonical form8.5 Compiler loop transformations8.6 Monotonicity of loop scheduling8.7 Static-schedule implementation8.7.1 Blocked loop schedules8.7.2 Block-cyclic loop scheduling8.8 Dynamic loop schedule implementation8.8.1 Guided scheduling8.8.2 monotonic:dynamic8.8.3 nonmonotonic:dynamic8.9 Evaluation of loop schedules8.10 Other loop-scheduling approaches8.10.1 Using history8.10.2 Exposing scheduling to the user8.11 Conclusions
9 Runtime support for task-parallel models
9.1 Task descriptors9.2 Task pool implementation9.2.1 Single task pool9.2.2 Multi task pool9.3 Task synchronization9.3.1 Waiting for a subset of tasks9.3.2 Waiting for immediate child tasks9.3.3 Task dependences9.4 Task scheduling concepts9.4.1 Task-scheduling points9.4.2 Breadth-first scheduling and depth-first scheduling9.4.3 Task stealing9.5 Task scheduling constraints9.5.1 Stack scheduling9.5.2 Cyclic scheduling9.6 Miscellaneous task topics9.6.1 Task priorities9.6.2 Task affinity9.7 Conclusions
10 Summary and final thoughts
BibliographyList of acronyms

Subject Index

Overview

This book focuses on the theoretical and practical aspects of parallel programming systems for today's high performance multi-core processors and discusses the efficient implementation of key algorithms needed to implement parallel programming models. Such implementations need to take into account the specific architectural aspects of the underlying computer architecture and the features offered by the execution environment.

This book briefly reviews key concepts of modern computer architecture, focusing particularly on the performance of parallel codes as well as the relevant concepts in parallel programming models. The book then turns towards the fundamental algorithms used to implement the parallel programming models and discusses how they interact with modern processors.

While the book will focus on the general mechanisms, we will mostly use the Intel processor architecture to exemplify the implementation concepts discussed but will present other processor architectures where appropriate. All algorithms and concepts are discussed in an easy to understand way with many illustrative examples, figures, and source code fragments.

The target audience of the book is students in Computer Science who are studying compiler construction, parallel programming, or programming systems. Software developers who have an interest in the core algorithms used to implement a parallel runtime system, or who need to educate themselves for projects that require the algorithms and concepts discussed in this book will also benefit from reading it.

You can find the source code for this book at https://github.com/parallel-runtimes/lomp.

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

What Successful Brick-and-Mortar Retailers Get Right

Publisher Resources

ISBN: 9783110632897

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills