Gustafson-Barsis's Law

• In 1988, Gustafson and Barsis at Sandia Laboratories studied the paradox created by Amdahl's law and the fact that parallel architectures comprised of hundreds of processors were built with substantial improvement in performance.
• In introducing their law, Gustafson recognized that the fraction of indivisible tasks in a given algorithm might not be known a priori. They argued that in practice, the problem size scales with the number of processors, $n$. This contradicts the basis of Amdahl's law.
• Recall that Amdahl's law assumes that the amount of time spent on the parts of the program that can be done in parallel, $(1-f)$, is independent of the number of processors, $n$.
• Gustafson and Brasis postulated that when using a more powerful processor, the problem tends to make use of the increased resources. They found that to a first approximation the parallel part of the program, not the serial part, scales up with the problem size.
• They postulated that if $s$ and $p$ represent respectively the serial and the parallel time spent on a parallel system, then $s+p*n$ represents the time needed by a serial processor to perform the computation.
• They therefore, introduced a new factor, called the scaled speedup factor, $SS(n)$, which can be computed as:
  

  $$SS(n)=\frac{s+p*n}{s+p}=s+p*n=s+(1-s)*n=n+(1-n)*s$$ (8)

  
  

• This equation shows that the resulting function is a straight line with a $slope=(1-n)$.
• This shows clearly that it is possible, even easier, to achieve efficient parallel performance than is implied by Amdahl's speedup formula. Speedup should be measured by scaling the problem to the number of processors, not by fixing the problem size.