Gustafson-Barsis's Law

• In 1988, Gustafson and Barsis at Sandia Laboratories studied the paradox created by Amdahl's law.
• Then It is the fact that parallel architectures comprised of hundreds of processors were built with substantial improvement in performance.
• In introducing their law, Gustafson recognised 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$.
• 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 speed-up 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$$ (3.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 speed-up formula.
• Speed-up should be measured by scaling the problem to the number of processors, not by fixing the problem size.