Upper bounds on speedup

Assume that almost all parts of a code are perfectly parallelizable (fraction \( f \)). The remainder, fraction \( (1-f) \) cannot be parallelized at all.

That is, there is work that takes time \( W \) on one process; a fraction \( f \) of that work will take time \( Wf/p \) on \( p \) processors.

  • What is the maximum possible speedup as a function of \( f \)?