The Art of Concurrency. A Thread Monkey's Guide to Writing Parallel Applications Clay Breshears

Spis treści książki

• The Art of Concurrency
  • SPECIAL OFFER: Upgrade this ebook with OReilly
  • A Note Regarding Supplemental Files
  • Preface
    • Why 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

pokaż cały spis treści

ukryj recenzje