Shared-Memory Parallel Programming

Exerted from "The Art of Parallel Programming, 2E by Bruce Lester"

1. Data Parallelism
    1.1 Process Creation
    1.2 Process Granularity
    1.3 Optimal Group Size
    1.4 The Fork Operator
        1.4.1 Process Termination
        1.4.2 The Join Statement
        1.4.3 Parallel List Processing
    1.5 Amdahl's Law
        1.5.1 Effects of Sequential Code on Speedup
        1.5.2 Overcoming Initialization Overhead

2. Multiprocessor Architecture
    2.1 Bus-oriented systems
    2.2 Cache Memory
    2.3 Processor-Memory Interconnection Networks

3. Process Communication
    3.1 Process Communication Streams
    3.2 Pipeline Parallelism

4. Data Sharing
    4.1 Atomic Operations
    4.2 Spinlocks
    4.3 Contention for Shared Data
    4.4 Comparing Spinlocks and Streams

5. Synchronous Parallelism
    5.1 Solving a Differential Equation
    5.2 Parallel Jacobi Relaxation
        5.2.1 Synchronization by Process Termination
        5.2.2 Barrier Synchronization
    5.3 Linear Barrier Implementation
    5.4 Binary Tree Implementation of Barriers
        5.4.1 Tournament Technique
        5.4.2 Tree Creation Algorithm
        5.4.3 Performance
    5.5 Local Synchronization
    5.6 Broadcasting and Aggregation
        5.6.1 Convergence Testing
        5.6.2 Implementing Parallel Aggregation

6. Replicated Workers
    6.1 Work Pools
    6.2 Implementation of Work Pools
    6.3 Eliminating Contention
        6.3.1 Load Balancing
        6.3.2 Termination Algorithm
        6.3.2 Performance  

Algorithm Design

I. Fundamental Tools

1. Algorithm Analysis
    1.1 Methodologies for Analyzing Algorithms
    1.2 Asymptotic Notation
    1.3 A Quick Mathematical Review
    1.5 Amortization
    1.6 Experimentation
2. Basic Data Structures
    2.1 Stacks and Queues
    2.2 Vectors, Lists, and Sequences
    2.3 Trees
    2.4 Priority Queues and Heaps
    2.5 Dictionaries and Hash Tables
3. Search Trees and Skip Lists
    3.1 Ordered Dictionaries and Binary Search Trees
    3.2 AVL Trees
    3.3 Bounded-Depth Search Trees
    3.4 Splay Trees
    3.5 Skip Lists
4. Sorting, Sets, and Selection
    4.1 Merge-Sort
    4.2 The Set Abstract Data Type
    4.3 Quick-Sort
    4.4 A Lower Bound on Comparision-Based Sorting
    4.5 Bucket-Sort and Radix-Sort
    4.6 Comparision of Sorting Algorithms
    4.7 Selection
5. Fundamental Techniques
    5.1 The Greedy Method
    5.2 Divide-and-Conquer
    5.3 Dynamic Programming

II. Graph Algorithms

6. Graphs
    6.1 The Graph Abstract Data Type
    6.2 Data Structures for Graphs
    6.3 Graph Traversal
    6.4 Directed Graphs
7. Weighted Graphs
    7.1 Single-Source Shortest Paths
    7.2 All-Pairs Shortest Paths
    7.3 Minimum Spanning Trees
8. Network Flow and Matching
    8.1 Flows and Cuts
    8.2 Maximum Flow
    8.3 Maximum Bipartite Matching
    8.4 Minimum-Cost Flow

III. Additional

9. Text Processing
    9.1 Strings and Pattern Matching Algorithms
    9.2 Tries
    9.3 Text Compression
    9.4 Text Similarity Testing
13. NP-Completeness
    13.1 P and NP
    13.2 NP-Completeness
    13.3 Important NP-Complete Problems
    13.4 Approximation Algorithms
    13.5 Backtracking and Branch-and-Bound
14. Algorithmic Frameworks
    14.1 External-Memory Algorithms
    14.2 Parallel Algorithms
    14.3 Online Algorithms