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?

Question

Daniella Nolan

English

7 March, 03:49

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?

+2

Answers (1)

Know the Answer?

Holloway · 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

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