Ask Question
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)
  1. 7 March, 03:52
    0
    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
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 English if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers