A particular parallel program computation requires 100 sec when executed on a…
2018
A particular parallel program computation requires 100 sec when executed on a single processor. If 40% of this computation is inherently sequential (i.e. will not benefit from additional processors), then theoretically best possible elapsed times of this program running with 2 and 4 processors, respectively, are
- A.
20 sec and 10 sec
- B.
30 sec and 15 sec
- C.
50 sec and 25 sec
- D.
70 sec and 55 sec
Attempted by 59 students.
Show answer & explanation
Correct answer: D
To determine the theoretical best possible elapsed times, we apply Amdahl's Law. The formula for execution time with N processors is T_N = T_1 * (S + P/N), where T_1 is the single-processor time, S is the sequential fraction, and P is the parallelizable fraction. Given T_1 = 100 sec, S = 0.4 (40%), and P = 0.6 (60%). For N=2 processors: T_2 = 100 * (0.4 + 0.6/2) = 100 * (0.4 + 0.3) = 70 seconds. For N=4 processors: T_4 = 100 * (0.4 + 0.6/4) = 100 * (0.4 + 0.15) = 55 seconds. Thus, the elapsed times are 70 sec and 55 sec respectively.
A video solution is available for this question — log in and enroll to watch it.