Reading: Parallel Algorithms

Reading¶

• Introduction to Parallel Computing - Sections E & F: Designing Parallel Programs and Parallel Examples.
  • Key concepts:
    • Hotspots & bottlenecks
    • Domain decomposition vs functional decomposition
    • Embarrassingly parallel
    • Communication
      • Overhead; latency vs bandwidth
      • Synchronous vs asynchronous
      • Scope; point-to-point vs collective
    • Synchronization
    • Data dependencies
    • Load balancing
    • Granularity
• Parallel Merge Sort
• Parallel Prefix (aka Parallel Scan, Recursive Doubling, Pointer Jumping):
  • Parallel Prefix Sum (Scan) - up to “39.2.1 A Naive Parallel Scan” and Example 1
  • Prefix Sums and Their Applications - Sections 1.1 and 1.2 are most relevant

Supplemental¶

• A better parallel merge sort: Odd-Even Mergesort