Let f be the fraction of a computation (in terms of time) that is…
2012
Let f be the fraction of a computation (in terms of time) that is parallelizable, P the number of processors in the system, and sp the speed up achievable in comparison with sequential execution – then the sp can be calculated using the relation:
Answer: C. \(\frac{1}{1-f+f/P}\) — Concept. Amdahl's law measures how much a computation can be accelerated by adding processors. If a fraction f of the total sequential running time is…
- A.
\(\frac{1}{1-f-f/P}\)
- B.
\(\frac{P}{P-f(P+1)}\)
- C.
\(\frac{1}{1-f+f/P}\)
- D.
\(\frac{P}{P+f(P-1)}\)
Attempted by 2 students.
Show answer & explanation
Correct answer: C
Concept. Amdahl's law measures how much a computation can be accelerated by adding processors. If a fraction f of the total sequential running time is parallelizable, the remaining fraction \(1-f\) must still run serially, and extra processors shorten only the parallelizable part. Speed up is defined as the ratio of the running time on a single processor to the running time on P processors.
Application. Normalise the sequential running time to 1 unit and split it:
The serial part takes \(1-f\) time and is unaffected by how many processors are available.
The parallelizable part takes f time on a single processor; shared ideally across P processors it takes \(f/P\).
The running time on P processors is therefore \(T_P=(1-f)+f/P\), while the running time on a single processor is \(T_1=1\).
Hence \(sp=\dfrac{T_1}{T_P}=\dfrac{1}{(1-f)+f/P}=\dfrac{1}{1-f+f/P}\).
Cross-check. Test the boundary cases. With \(f=0\) nothing is parallelizable and the expression gives \(1/1=1\), that is, no gain at all. With \(f=1\) everything is parallelizable and it gives \(1/(1/P)=P\), that is, linear speed up. As \(P\to\infty\) it tends to \(\dfrac{1}{1-f}\), the ceiling Amdahl's law predicts. Multiplying numerator and denominator by P gives the equivalent form \(\dfrac{P}{P-f(P-1)}\).
So the speed up is \(sp=\dfrac{1}{1-f+f/P}\).