The table below shows the execution time in percentage for v

The table below shows the execution time in percentage for various sections of a code. Answer the following questions clearly showing all your steps. Define Amdahl\'s law. Which section takes the least execution time and which section takes the most execution time? By reducing the execution time of the write back section can the entire code gain a speed-up of 2? By reducing the execution time of the computation section can the entire code gain a speed-up of 2?

Solution

Q3.) a.) Amdahl\'s Law:

Amdahl\'s law gives the speedup in the execution of a same program after using parallel processors in place of a single serial processor. i.e., speedup = (time taken by single processor to perform a task) / (time taken by parallel processors to perform similar task).

b.) As, we can see clearly Final section will take least execution time while Computation will take most execution time.

c.) Let us assume overall execution time will be 100 sec. So, read data will take 10 sec, Computation will take 60 sec, Write back will take 25 sec and Final will take 5 sec. Let we have reduced the time of Write Back to 0 sec. Now, from Amdahl\'s law, speedup = prev. time/ new time = 100/75 = 1.33. So, we can\'t acheive speedup of 2 by reducing the execution time of write back section.

d.) Similary, let\'s assume computation section take x sec. Therefore in order to acheive speedup of 2, We have

100/ ( 10 + x + 25 + 5) = 2

100 / (40+x) = 2

40 + x = 50

x = 10.

So, if we able to reduce execution time of Computation section by 10 sec (or %) or less, we can acheive speedup of 2.