The Art of Concurrency. A Thread Monkey's Guide to Writing Parallel Applications (e-book)

The Art of Concurrency. A Thread Monkey's Guide to Writing Parallel Applications (e-book) - Opis

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 concurrencyExplore differences between programming for shared-memory and distributed-memoryLearn guidelines for designing multithreaded applications, including testing and tuningDiscover how to make best use of different threading libraries, including Windows threads, POSIX threads, OpenMP, and Intel Threading Building BlocksExplore how to implement concurrent algorithms that involve sorting, searching, graphs, and other practical computationsThe 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. Spis treści:
The Art of Concurrency
SPECIAL OFFER: Upgrade this ebook with OReilly
A Note Regarding Supplemental Files
Preface
Why (...) więcej Should You Read This Book?
Who Is This Book For?
Whats in This Book?
Conventions Used in This Book
Using Code Examples
Comments and Questions
Safari Books Online
Acknowledgments
1. Want to Go Faster? Raise Your Hands if You Want to Go Faster!
Some Questions You May Have
What Is a Thread Monkey?
Parallelism and Concurrency: Whats the Difference?
Why Do I Need to Know This? Whats in It for Me?
Isnt Concurrent Programming Hard?
Arent Threads Dangerous?
Four Steps of a Threading Methodology
Step 1. Analysis: Identify Possible Concurrency
Step 2. Design and Implementation: Threading the Algorithm
Step 3. Test for Correctness: Detecting and Fixing Threading Errors
Step 4. Tune for Performance: Removing Performance Bottlenecks
The testing and tuning cycle
What About Concurrency from Scratch?
Background of Parallel Algorithms
Theoretical Models
Distributed-Memory Programming
Parallel Algorithms Literature
Shared-Memory Programming Versus Distributed-Memory Programming
Common Features
Redundant work
Dividing work
Sharing data
Static/dynamic allocation of work
Features Unique to Shared Memory
Local declarations and thread-local storage
Memory effects
Communication in memory
Mutual exclusion
Producer/consumer
Readers/writer locks
This Books Approach to Concurrent Programming
2. Concurrent or Not Concurrent?
Design Models for Concurrent Algorithms
Task Decomposition
What 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 integration
Data Decomposition
How 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 grid
Concurrent Design Models Wrap-Up
Whats Not Parallel
Algorithms with State
Recurrences
Induction Variables
Reduction
Loop-Carried Dependence
Not-so-typical loop-carried dependence
3. Proving Correctness and Measuring Performance
Verification of Parallel Algorithms
Example: The Critical Section Problem
First Attempt
Second Attempt
Third Attempt
Fourth Attempt
Dekkers Algorithm
Case 1
Case 2a: T0 is the favored thread
Case 2b: T1 is the favored thread
Case 3
What about indefinite postponement?
What Did You Learn?
There Are No Evil Threads, Just Threads Programmed for Evil
Performance Metrics (How Am I Doing?)
Speedup
Amdahls Law
Gustafson-Barsiss Law
Efficiency
One Final Note on Speedup and Efficiency
Review of the Evolution for Supporting Parallelism in Hardware
4. Eight Simple Rules for Designing Multithreaded Applications
Rule 1: Identify Truly Independent Computations
Rule 2: Implement Concurrency at the Highest Level Possible
Rule 3: Plan Early for Scalability to Take Advantage of Increasing Numbers of Cores
Rule 4: Make Use of Thread-Safe Libraries Wherever Possible
Rule 5: Use the Right Threading Model
Rule 6: Never Assume a Particular Order of Execution
Rule 7: Use Thread-Local Storage Whenever Possible or Associate Locks to Specific Data
Rule 8: Dare to Change the Algorithm for a Better Chance of Concurrency
Summary
5. Threading Libraries
Implicit Threading
OpenMP
Intel Threading Building Blocks
Explicit Threading
Pthreads
Windows Threads
What Else Is Out There?
Domain-Specific Libraries
6. Parallel Sum and Prefix Scan
Parallel Sum
PRAM Algorithm
A dash of reality
A More Practical Algorithm
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
Prefix Scan
PRAM Algorithm
A less heavy dash of reality
A More Practical Algorithm
What the main thread does
What the spawned threads are doing
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
Selection
The Serial Algorithm
The Concurrent Algorithm
Finding the medians of subsequences
Counting and marking elements for partitions
The ArrayPack() function
Some Design Notes
A Final Thought
7. MapReduce
Map As a Concurrent Operation
Implementing a Concurrent Map
Reduce As a Concurrent Operation
Handcoded Reduction
A Barrier Object Implementation
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
Applying MapReduce
Friendly Numbers Example Summary
MapReduce As Generic Concurrency
8. Sorting
Bubblesort
Will It Work?
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
Odd-Even Transposition Sort
A Concurrent Code for Odd-Even Transposition Sort
Trying to Push the Concurrency Higher
Keeping threads awake longer without caffeine
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
Shellsort
Quick Review of Insertion Sort
Serial Shellsort
Concurrent Shellsort
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
Quicksort
Concurrency Within Recursion
Concurrency Within an Iterative Version
Iterative Quicksort
Concurrent iterative version
Letting threads know the work is done
Finding work for threads
Giving threads their pink slips
Final Threaded Version
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
Radix Sort
Radix Exchange Sort
Straight Radix Sort
Using prefix scan to gather keys
Keeping data movement stable
Reducing the number of data touches
The Concurrent Straight Radix Sort Solution
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
9. Searching
Unsorted Sequence
Curtailing the Search
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
Binary Search
But First, a Serial Version
At Last, the Concurrent Solution
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
10. Graph Algorithms
Depth-First Search
A Recursive Solution
An Iterative Solution
Not the Concurrent Solution, Yet
How many locks do we need?
Locking a conditional expression evaluation
Now for the Concurrent Solution
A little interleaving analysis
Spawning the depth-first search threads
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
Breadth-First Search
Its all in the queue
Static Graphs Versus Dynamic Graphs
All-Pairs Shortest Path
What About the Data Race on the kth Row?
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
Alternatives to Floyds Algorithm
Minimum Spanning Tree
Kruskals Algorithm
Prims Algorithm
Which Serial Algorithm Should We Start With?
Concurrent Version of Prims Algorithm
Design Factor Scorecard
Efficiency
Simplicity
Portability
Scalability
11. Threading Tools
Debuggers
Thread-Aware Debugger
Thread Issue Debugger: Thread Checker
Performance Tools
Profiling
Thread Profiling: Standard Profile Tool (Sample Over Time), Thread Profiler
Anything Else Out There?
Go Forth and Conquer
Glossary
A. Photo Credits
Index
About the Author
Colophon
SPECIAL OFFER: Upgrade this ebook with OReilly mniej