Question

Amdahl's Law

Consider a program which takes 1000 seconds to execute, broken into 5 phases: A, B, C, D, E. Without any optimizations, each phase takes one-fifth of the total execution time.

Suppose that Phase A and B are both 60% parallelizable, and Phase C, D, and E are each 20% parallizable.

a. Assuming that there are 100 processors, and zero overhead from parallelization, what is the maximum speedup that can be obtained?
b. Wat is the speed up achieved (w.r.t to the initial) if we had 1000 processors instead of 100?
c. Based on this program alone, does hte speedup increase warrant the additional 900 processors?

Answer 1

Part a: The speed up in case of the 100 processors is 400/21.

Part b: The speed up in case of the 1000 processors is 4000/21.

Part c: Yes in case of 1000 processors the speedup will increase eventually, and it will be 4000/21 Time

Step-by-step explanation:

Each Phase Take 1\5 of Total Execution Time.

Total Execution Time is : 1000 Seconds.

A Time = 200 Seconds

B Time = 200 Seconds

C Time = 200 Seconds

D Time = 200 Seconds

E Time = 200 Seconds

T = [A + B] + [C+D+E]

As A and B are parallelizable 60%, the individual time of A and B is

Phase A[40%] total Time = A/40

Phase B [40%] Time = B/40

Similarly the pase C, D & E are parallelizable for 20% so the remaining time for individual process is

Phase C[80%] Time = C/80

Phase D[80%] Time = D/80

Phase E[80%] Time = E/80

Phase A + Phase B [60%] Time = 6*A/40 = 6*B/40

Phase C+Phase D+Phase E [20%] time= 2*C/80= 2*D/80 =2*E/80

T' = A' + B' + C' + D' + E'

= A/40 + B/ 40 + C / 80 + D/80 + E/80 + 6*B / 40 + 2*D/80

T' = T/(5*40) + T/(5*40) + T/(5*80) + T/(5*80)+ T/(5*80) + 6*T/(5*40) + 2*T/(5*80)

We know that A, B, C, D, AND E are 1/5 of T. So:

T' =T/200 + T/ 200 + T/ 400 + T/400 + T/400 + 6*T/ 200 + 2*T/400

= 21/400*T

The speed-up is

T / T' = T / (21/400 T) = 400/21 Time

In case of 1000 processors the time is given as

T/T'=T / (21/400 T) = 400/21 Time*1000/100=400/21 Time*10=4000/21 time

Yes in case of 1000 processors the speedup will increase eventually, and it will be 4000/21 Time