Performance metrics

1. Sources of overhead in parallel programming
interprocess interaction (e.g., communication), idling (load imbalancing and synchronization)


2. Execution time and total parallel overhead

• serial runtime (Ts): the time elapsed between the beginning and the end of its execution.
• parallel runtime (Tp): the time elapsed from the moment a parallel computation starts to the moment the last processing element finishes execution.
• overhead function/total overhead (To) = p * Tp - Ts             
  (p: the number of processing elements)

3. Speedup (S)
Speedup is a measure for the relative performance benefit from a parallel algorithm compared to a sequential algorithm. It is defined as
      S = Ts / Tp

Amdahl's law, which is used to find the theoretical maximum speedup, defines the speedup as
      S = 1 / ((1-f) + f / p),
      where f is the portion of the execution time perfectly parallelizable and p is the number of processing
      elements

4. Efficiency (E)
     E = S / p = Ts/ (p*Tp)

References

• Grama et al. Introduction to Parallel computing
• Amdahl's Law in the Multicore Era at Google tech talk in 2009
• Amdahl's law in Wikipedia