High Performance Parallel Computing

CSE 6230 -- High Performance Parallel Computing

• class webpage

• weak scaling - maximizing work performed per unit time
• strong scaling - minimizing time-to-solution

Measures of parallel algorithms

• Cost: proccount * exectime
• Overhead: Cost(P) - Cost(1)
• Speedup: exectime(1) / exectime(p)
• Efficiency: Speedup / p
• Scalable if
  • Efficiency is O(1) as p approaches infinity (*not* 0)
  • Work(p) is linear in p
  • Fixed work per processor is O(1) as p approaches infinity (*not* 0)
• Isoefficiency: How fast must our working set grow to maintain constant efficiency as processors are added?

Papers

• Amdahl's Law in the Multicore Era by MD Hill
• Lock-free algorithms page