CSC 456 Spring 2012/ch4b

Gustafson's Law

In 1985, IBM scientist Alan Karp issued a challenge to anyone who could produce a speedup of over 200 times. "Karp's Challenge", as it became known, highlighted the limitations of Amdahl's Law. Prevailing speedups at the time were less than tenfold, and were for applications with little real-world value. C. Gordon Bell decided to up the ante, offering a $1000 award for the same challenge, issued annually to the winner, but only if the speedup was at least twice that of the previous award. He initially expected the first winner to have a speedup close to ten times, and that it would be difficult to advance beyond that.

John Gustafson won the 1988 Gordon Bell prize by demonstrating a 1000x speedup on a parallel program. He noticed the flaw in Amdahl's Law, which assumed a constant serial fraction of the problem, regardless of problem size. Gustafson realized that when you scale the problem size up proportional to the number of processors, the non-parallelizable fraction of work decreases. This provided the basis of what became known as "Gustafson's Law".

speedup(p) = p - s(p-1)

Superlinear Speedup