The Art of Concurrency

Preface

1. Want to Go Faster? Raise Your Hands if You Want to Go Faster!
-Some Questions You May Have
-Four Steps of a Threading Methodology
-Background of Parallel Algorithms
-Shared-Memory Programming Versus Distributed-Memory Programming
-This Book's Approach to Concurrent Programming

2. Concurrent or Not Concurrent?
-Design Models for Concurrent Algorithms
-What's Not Parallel

3. Proving Correctness and Measuring Performance
-Verification of Parallel Algorithms
-Example: The Critical Section Problem
-Performance Metrics (How Am I Doing?)
-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
-Explicit Threading
-What Else Is Out There?
-Domain-Specific Libraries

6. Parallel Sum and Prefix Scan
-Parallel Sum
-Prefix Scan
-Selection
-A Final Thought

7. MapReduce
-Map As a Concurrent Operation
-Reduce As a Concurrent Operation
-Applying MapReduce
-MapReduce As Generic Concurrency

8. Sorting
-Bubblesort
-Odd-Even Transposition Sort
-Shellsort
-Quicksort
-Radix Sort

9. Searching
-Unsorted Sequence
-Binary Search

10. Graph Algorithms
-Depth-First Search
-All-Pairs Shortest Path
-Minimum Spanning Tree

11. Threading Tools
-Debuggers
-Performance Tools
-Anything Else Out There?
-Go Forth and Conquer

Glossary
Photo Credits
Index