1.15 [5] <§1.8> When a program is adapted to run on multiple processors in a mul

Question

1.15 [5] <§1.8> When a program is adapted to run on multiple processors in a multiprocessor system, the execution time on each processor is comprised of computing time and the overhead time required for locked critical sections and/or to send data from one processor to another. Assume a program requires t = 100 s of execution time on one processor. When run p processors, each processor requires t/p s, as well as an additional 4 s of overhead, irrespective of the number of processors. Compute the per-processor execution time for 2, 4, 8, 16, 32, 64, and 128 processors. For each case, list the corresponding speedup relative to a single processor and the ratio between actual speedup versus ideal speedup (speedup if there was no overhead).

Explanation / Answer

n = 2
T(n=2) = 100/2 + 4 = 54 s
Speed up = 100/54 = 1.85
ideal Speedup = 100/50 = 2
n = 4
T(n=4) = 100/4 + 4 = 25 + 4 = 29
Speed up = 100/29 = 3.44
ideal Speedup = 100/25 = 4
n = 8
T(n=8) = 100/8 + 4 = 12.5 + 4 = 16.5
Speed up = 100/16.5 = 6.06
ideal Speedup = 100/12.5 = 8
n = 16
T(n=16) = 100/16 + 4 = 10.25
Speed up = 100/10.25 = 9.75
ideal Speedup = 100/6.25 = 16.
n = 32
T(n=2) = 100/32 + 4 = 7.125
Speed up = 100/7.125 = 14.03
ideal Speedup = 100/3.125 = 32.
n = 64
T(n=2) = 100/64 + 4 = 5.5625
Speed up = 100/5.5625 = 17.97
ideal Speedup = 100/1.5625 = 64.
n = 128
T(n=2) = 100/128 + 4 = 4.781
Speed up = 100/4.781 = 20.91
ideal Speedup = 100/0.78125 = 128.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.