In the case of parallelization, Amdahl's law states that if \(𝑃\) is the…
2015
In the case of parallelization, Amdahl's law states that if \(𝑃\) is the proportion of a program that can be made parallel and \((1−𝑃)\) is the proportion that cannot be parallelized, then the maximum speed-up that can be achieved by using \(𝑁\) processors is:
Answer: C. \(\dfrac{1}{(1-P)+\frac{P}{N}} \\\) — Correct formula: S(N) = 1 / ((1 - P) + P/N) Derivation: Normalize the total work so that execution time on one processor is 1. The serial (non-parallelizable)…
- A.
\(\dfrac{1}{(1-P)+N.P} \\\) - B.
\(\dfrac{1}{(N-1)P+P} \\\) - C.
\(\dfrac{1}{(1-P)+\frac{P}{N}} \\\) - D.
\(\dfrac{1}{P+\frac{(1-P)}{N}}\)
Attempted by 61 students.
Show answer & explanation
Correct answer: C
Correct formula: S(N) = 1 / ((1 - P) + P/N)
Derivation:
Normalize the total work so that execution time on one processor is 1.
The serial (non-parallelizable) portion takes time (1 − P).
The parallelizable portion P is divided evenly across N processors, so its time becomes P/N.
Total execution time with N processors = (1 − P) + P/N.
Speed-up S(N) is the ratio of the original time to the new time, so S(N) = 1 / ((1 − P) + P/N).
Limiting case: As N → ∞ the P/N term goes to 0, so the maximum possible speed-up is 1/(1 − P).
Quick example: If P = 0.9 and N = 10, total time = 0.1 + 0.9/10 = 0.19, so S(10) ≈ 1/0.19 ≈ 5.26.