
Art of Concurrency
A Thread Monkey's Guide to Writing Parallel Applications
Clay Breshears(Autor*in)
O'Reilly (Verlag)
1. Auflage
Erschienen am 7. Mai 2009
304 Seiten
978-0-596-55578-8 (ISBN)
Systemvoraussetzungen
für ePUB mit Adobe-DRM
E-Book Einzellizenz
Bei dem Kauf dieses E-Books erwerben Sie eine Einzel-Lizenz für eine natürliche Person, die nicht übertragbar ist. [L]
Als Download verfügbar
Beschreibung
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.
Weitere Details
Sprache
Englisch
Verlagsort
Sebastopol
USA
Dateigröße
3,99 MB
ISBN-13
978-0-596-55578-8 (9780596555788)
Schweitzer Klassifikation
Weitere Ausgaben
Inhalt
- Intro
- The Art of Concurrency
- 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 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: 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 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 Book's 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
- What's 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
- Dekker's 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
- Amdahl's Law
- Gustafson-Barsis's 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
- It's 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 Floyd's Algorithm
- Minimum Spanning Tree
- Kruskal's Algorithm
- Prim's Algorithm
- Which Serial Algorithm Should We Start With?
- Concurrent Version of Prim's 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
- Copyright
Systemvoraussetzungen
Dateiformat: ePUB
Kopierschutz: Adobe-DRM (Digital Rights Management)
Systemvoraussetzungen:
- Computer (Windows; MacOS X; Linux): Installieren Sie bereits vor dem Download die kostenlose Software Adobe Digital Editions (siehe E-Book Hilfe).
- Tablet/Smartphone (Android; iOS): Installieren Sie bereits vor dem Download die kostenlose App Adobe Digital Editions oder die App PocketBook (siehe E-Book Hilfe).
- E-Book-Reader: Bookeen, Kobo, Pocketbook, Sony, Tolino u.v.a.m. (nicht Kindle)
Das Dateiformat ePUB ist sehr gut für Romane und Sachbücher geeignet – also für „fließenden” Text ohne komplexes Layout. Bei E-Readern oder Smartphones passt sich der Zeilen- und Seitenumbruch automatisch den kleinen Displays an.
Mit Adobe-DRM wird hier ein „harter” Kopierschutz verwendet. Wenn die notwendigen Voraussetzungen nicht vorliegen, können Sie das E-Book leider nicht öffnen. Daher müssen Sie bereits vor dem Download Ihre Lese-Hardware vorbereiten.
Bitte beachten Sie: Wir empfehlen Ihnen unbedingt nach Installation der Lese-Software diese mit Ihrer persönlichen Adobe-ID zu autorisieren!
Weitere Informationen finden Sie in unserer E-Book Hilfe.