In the standard work-conservation model, where p processors together deliver…
2012
In the standard work-conservation model, where p processors together deliver at most p times the work of one processor, what are the tightest bounds that the efficiency (E) and the speed-up (sp) of a multiprocessor with p processors always satisfy?
Answer: B. E ≤ 1 and sp ≤ p — ConceptFor a program run on p processors, two standard performance metrics are defined from run times. Speed-up is the single-processor run time divided by…
- A.
E ≤ p and sp ≤ p
- B.
E ≤ 1 and sp ≤ p
- C.
E ≤ p and sp ≤ 1
- D.
E ≤ 1 and sp ≤ 1
Attempted by 3 students.
Show answer & explanation
Correct answer: B
Concept
For a program run on p processors, two standard performance metrics are defined from run times. Speed-up is the single-processor run time divided by the p-processor run time; efficiency is the speed-up delivered per processor, which measures how well each individual processor is used on average.
sp = T1 / Tp E = sp / p
The bounds come from a work-conservation model, which is the model these metrics are defined against: in a given time p processors together deliver at most p times the work of one processor, so the p-processor run time can never fall below a p-th of the single-processor run time.
Tp ≥ T1 / p
Applying it to this question
Start from the work ceiling on the p-processor run time:
Tp ≥ T1 / pSubstitute that bound into the definition of speed-up:
sp = T1 / Tp ≤ T1 / (T1 / p) = pSpeed-up is therefore bounded by the processor count. Divide this bound by p to obtain the efficiency bound:
E = sp / p ≤ p / p = 1Both bounds are reached together only in the ideal linear case, where the p-processor run time is exactly a p-th of the single-processor run time:
Tp = T1 / p ⇒ sp = p, E = 1
Cross-check with numbers
p-processor run time (p = 4, single-processor time = 100 s) | Speed-up | Efficiency |
|---|---|---|
25 s (ideal linear) | 4 | 1.00 |
40 s (typical) | 2.5 | 0.63 |
100 s (no gain) | 1 | 0.25 |
Across every row the speed-up figure stays at or below the processor count while the efficiency figure stays at or below one. Efficiency is normally quoted as a percentage, and 100% is its maximum.
Outside that model a “superlinear” speed-up above p is occasionally measured, when splitting a problem lets its working set fit into cache. The bounds above are the ones that hold under the work-conservation model this question is set in.
Weaker statements can be true without being the answer. Because efficiency never exceeds 1 and p is at least 1, a claim such as “efficiency is at most p” is also true — but it is loose, since for a large machine it constrains efficiency hardly at all. The question asks for the bounds that cannot be tightened any further.
Result
Under that model the tightest bounds are: efficiency is at most 1, and speed-up is at most the processor count p.