CS420 Quiz

 Excess Computation  The best existing serial algorithm may not be readily or efficiently parallelizable  -perhaps, can’t just evenly divide serial algorithm into p parallel pieces.  Each parallel task may require addition computation (relative to the corresponding work in the serial algorithm) – recall: redundant computation  = Excess computation = overhead  Serial Runtime = total lapsed time (wall time) from the beginning to the end of execution for the serial program on a single PE.  Parallel Runtime = total lapsed time (wall time) from the beginning of the parallel computation to the end of the parallel computation.  Ts = Serial Runtime  Tp = Parallel Runtime  As a baseline….from a theoretical perspective  Ts is often based on the best available serial algorithm to solution a given problem  … not necessarily based on the serial version of the parallel algorithm.

 From a practical perspective…

 Sometimes the serial and parallel algorithms are based on the same algorithm  Sometimes you want to know the parallel algorithm compares to it serial couterpart.