Parallel Scientific Programming
• Definitions
– Speedup: Ts/Tp, where Ts is the sequential time and Tp is the time when using p cores
• “Perfect speedup” is p, which really should be called “linear speedup”
• Typically, speedup is less than p—but it can be larger because of memory hierarchy effects
– Efficiency: Speedup/p
• Intuition: how well am I using my p cores
Picture of Speedup and Efficiency
Parallel Scientific Programming
• Definitions, continued
– Amdahl’s law: if Ts is sequential time, then:
• Tp ≈ Ts * (1-f) + (Ts / p) * f, where f is the fraction of the program that is parallelizable
• Intuition: the non-parallelizable portion doesn’t speed up at all, and the parallelizable part scales linearly
• Of course, this isn’t true in general; one might, for example, have load imbalance in a parallelizable portion—also ignored is process/thread creation, communication, synchronization
Picture of Amdahl’s Law
Example use of Amdahl’s Law
• Suppose program takes 50 seconds sequentially, but of that 50 seconds:
– 5 seconds is initialization that can’t be parallelized
– 5 seconds is finalization that also can’t be parallelized
• Then the maximum speedup possible is 5! – Even if we have an arbitrarily large number of
cores!
– Lesson: try to avoid sequential portions of code
Different parallel programming styles (end of Chapter 3)
• Iterative: SPMD (e.g., Jacobi iteration)
• Recursive: adaptive quadrature
• Task parallel: independent portions of programs
• Bag of tasks: implementation of recursive, generally, but also can be used for iterative
Data Parallel Algorithms
• Execute identical code on different parts of a data structure
– Usually we mean “SPMD algorithms”, which stands for Single Program Multiple Data
– Data Parallel implies barrier after every instruction (arose from programming SIMD architectures; recall SIMD is Single Instruction Multiple Data)
– SPMD allows barriers at arbitrary points (arose from MIMD architectures)
• It is a relaxation of SIMD
Picture: finding the sum of an array in parallel (SPMD program)
Finding the sum of an array in parallel (SPMD program)
int sum[n], old[n], a[n] // Array a initialized to arbitrary values co i := 0 to n-1
int d = 1 sum[i] = a[i] while (d < n) {
old[i] = sum[i] barrier
if (i – d >= 0)
Why?
sum[i] = old[i-d] + sum[i]
barrier Why? d =d * 2
} oc
Picture: Jacobi Iteration