Consider a program which takes 1000 seconds to execute, broken into 5 phases: A,

Question

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

(b) Starting with the original execution times (without the optimizations in Part (a)), suppose that Phase A and B are both 60% parallelizable, and Phases C, D and E are each 20% parallelizable. Assuming that there are 100 processors, and zero overhead from parallelization, what is the maximum speedup that can be obtained? What is the speed up achieved (w.r.t to the initial) if we had 1000 processors instead of 100? Based on this program alone, does the speedup increase warrant the additional 900 processors

Explanation / Answer

Solution:

Each Phase Take 1 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

The total time is the sum of the times for the 3 Phase:
T = A + B + C+D+E

Then, A and B are parallelizable 60%

So Phase A[40%] total Time = A/40
     Phase B [40%] Time = B/40
     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

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

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

Please, please upvote and ask your doubts in the comments.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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