book

The Art of Concurrency

Name: The Art of Concurrency
Author: Clay Breshears
ISBN: 9780596521530

by Clay Breshears

May 2009

Intermediate to advanced

302 pages

10h 15m

English

O'Reilly Media, Inc.

Read now

Unlock full access

Dedication
A Note Regarding Supplemental Files
Preface
Why Should You Read This Book?Who Is This Book For?What’s in This Book?Conventions Used in This BookUsing Code ExamplesComments and QuestionsSafari® Books OnlineAcknowledgments
1. Want to Go Faster? Raise Your Hands if You Want to Go Faster!
Some Questions You May HaveWhat Is a Thread Monkey?Parallelism and Concurrency: What’s the Difference?Why Do I Need to Know This? What’s in It for Me?Isn’t Concurrent Programming Hard?Aren’t Threads Dangerous?Four Steps of a Threading MethodologyStep 1. Analysis: Identify Possible ConcurrencyStep 2. Design and Implementation: Threading the AlgorithmStep 3. Test for Correctness: Detecting and Fixing Threading ErrorsStep 4. Tune for Performance: Removing Performance BottlenecksThe testing and tuning cycleWhat About Concurrency from Scratch?Background of Parallel AlgorithmsTheoretical ModelsDistributed-Memory ProgrammingParallel Algorithms LiteratureShared-Memory Programming Versus Distributed-Memory ProgrammingCommon FeaturesRedundant workDividing workSharing dataStatic/dynamic allocation of workFeatures Unique to Shared MemoryLocal declarations and thread-local storageMemory effectsCommunication in memoryMutual exclusionProducer/consumerReaders/writer locksThis Book’s Approach to Concurrent Programming
2. Concurrent or Not Concurrent?
Design Models for Concurrent AlgorithmsTask DecompositionWhat are the tasks and how are they defined?What are the dependencies between tasks and how can they be satisfied?How are the tasks assigned to threads?Example: numerical integrationData DecompositionHow should you divide the data into chunks?How can you ensure that the tasks for each chunk have access to all data required for updates?How are the data chunks (and tasks) assigned to threads?Example: Game of Life on a finite gridConcurrent Design Models Wrap-UpWhat’s Not ParallelAlgorithms with StateRecurrencesInduction VariablesReductionLoop-Carried DependenceNot-so-typical loop-carried dependence
3. Proving Correctness and Measuring Performance
Verification of Parallel AlgorithmsExample: The Critical Section ProblemFirst AttemptSecond AttemptThird AttemptFourth AttemptDekker’s AlgorithmCase 1Case 2a: T0 is the favored threadCase 2b: T1 is the favored threadCase 3What about indefinite postponement?What Did You Learn?There Are No Evil Threads, Just Threads Programmed for EvilPerformance Metrics (How Am I Doing?)SpeedupAmdahl’s LawGustafson-Barsis’s LawEfficiencyOne Final Note on Speedup and EfficiencyReview of the Evolution for Supporting Parallelism in Hardware
4. Eight Simple Rules for Designing Multithreaded Applications
Rule 1: Identify Truly Independent ComputationsRule 2: Implement Concurrency at the Highest Level PossibleRule 3: Plan Early for Scalability to Take Advantage of Increasing Numbers of CoresRule 4: Make Use of Thread-Safe Libraries Wherever PossibleRule 5: Use the Right Threading ModelRule 6: Never Assume a Particular Order of ExecutionRule 7: Use Thread-Local Storage Whenever Possible or Associate Locks to Specific DataRule 8: Dare to Change the Algorithm for a Better Chance of ConcurrencySummary
5. Threading Libraries
Implicit ThreadingOpenMPIntel Threading Building BlocksExplicit ThreadingPthreadsWindows ThreadsWhat Else Is Out There?Domain-Specific Libraries
6. Parallel Sum and Prefix Scan
Parallel SumPRAM AlgorithmA dash of realityA More Practical AlgorithmDesign Factor ScorecardEfficiencySimplicityPortabilityScalabilityPrefix ScanPRAM AlgorithmA less heavy dash of realityA More Practical AlgorithmWhat the main thread doesWhat the spawned threads are doingDesign Factor ScorecardEfficiencySimplicityPortabilityScalabilitySelectionThe Serial AlgorithmThe Concurrent AlgorithmFinding the medians of subsequencesCounting and marking elements for partitionsThe ArrayPack() functionSome Design NotesA Final Thought
7. MapReduce
Map As a Concurrent OperationImplementing a Concurrent MapReduce As a Concurrent OperationHandcoded ReductionA Barrier Object ImplementationDesign Factor ScorecardEfficiencySimplicityPortabilityScalabilityApplying MapReduceFriendly Numbers Example SummaryMapReduce As Generic Concurrency

8. Sorting
BubblesortWill It Work?Design Factor ScorecardEfficiencySimplicityPortabilityScalabilityOdd-Even Transposition SortA Concurrent Code for Odd-Even Transposition SortTrying to Push the Concurrency HigherKeeping threads awake longer without caffeineDesign Factor ScorecardEfficiencySimplicityPortabilityScalabilityShellsortQuick Review of Insertion SortSerial ShellsortConcurrent ShellsortDesign Factor ScorecardEfficiencySimplicityPortabilityScalabilityQuicksortConcurrency Within RecursionConcurrency Within an Iterative VersionIterative QuicksortConcurrent iterative versionLetting threads know the work is doneFinding work for threadsGiving threads their pink slipsFinal Threaded VersionDesign Factor ScorecardEfficiencySimplicityPortabilityScalabilityRadix SortRadix Exchange SortStraight Radix SortUsing prefix scan to gather keysKeeping data movement stableReducing the number of data touchesThe Concurrent Straight Radix Sort SolutionDesign Factor ScorecardEfficiencySimplicityPortabilityScalability
9. Searching
Unsorted SequenceCurtailing the SearchDesign Factor ScorecardEfficiencySimplicityPortabilityScalabilityBinary SearchBut First, a Serial VersionAt Last, the Concurrent SolutionDesign Factor ScorecardEfficiencySimplicityPortabilityScalability
10. Graph Algorithms
Depth-First SearchA Recursive SolutionAn Iterative SolutionNot the Concurrent Solution, YetHow many locks do we need?Locking a conditional expression evaluationNow for the Concurrent SolutionA little interleaving analysisSpawning the depth-first search threadsDesign Factor ScorecardEfficiencySimplicityPortabilityScalabilityBreadth-First SearchIt’s all in the queueStatic Graphs Versus Dynamic GraphsAll-Pairs Shortest PathWhat About the Data Race on the kth Row?Design Factor ScorecardEfficiencySimplicityPortabilityScalabilityAlternatives to Floyd’s AlgorithmMinimum Spanning TreeKruskal’s AlgorithmPrim’s AlgorithmWhich Serial Algorithm Should We Start With?Concurrent Version of Prim’s AlgorithmDesign Factor ScorecardEfficiencySimplicityPortabilityScalability
11. Threading Tools
DebuggersThread-Aware DebuggerThread Issue Debugger: Thread CheckerPerformance ToolsProfilingThread Profiling: Standard Profile Tool (Sample Over Time), Thread ProfilerAnything Else Out There?Go Forth and Conquer
Glossary
A. Photo Credits
Index
About the Author
Colophon
Copyright

Overview

If you're looking to take full advantage of multi-core processors with concurrent programming, this practical book provides the knowledge and hands-on experience you need. The Art of Concurrency is one of the few resources to focus on implementing algorithms in the shared-memory model of multi-core processors, rather than just theoretical models or distributed-memory architectures. The book provides detailed explanations and usable samples to help you transform algorithms from serial to parallel code, along with advice and analysis for avoiding mistakes that programmers typically make when first attempting these computations.

Written by an Intel engineer with over two decades of parallel and concurrent programming experience, this book will help you:

Understand parallelism and concurrency
Explore differences between programming for shared-memory and distributed-memory
Learn guidelines for designing multithreaded applications, including testing and tuning
Discover how to make best use of different threading libraries, including Windows threads, POSIX threads, OpenMP, and Intel Threading Building Blocks
Explore how to implement concurrent algorithms that involve sorting, searching, graphs, and other practical computations

The Art of Concurrency shows you how to keep algorithms scalable to take advantage of new processors with even more cores. For developing parallel code algorithms for concurrent programming, this book is a must.

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

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems

Publisher Resources

ISBN: 9780596802424Errata Page

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills