Question

We benchmark a program and find that 80% of the time is spent in functions we can execute in parallel. What is the maximum possible speedup we can expect? What is the maximum possible speedup if parallelizing this code for only 4 processors? (Explain your calculations).

Answer 1

If x unit is the total time to execute a program sequentially, then when 80% of the time functions execution can be done parallely, it means only 20% of x I.e. 0.2x unit time will the sequential operation will take place and when we have infinite processors then executing remaining code will take almost zero unit time.

Hence total time taken = 0.2x

Hence the maximum possible speedup = x/0.2x = 5

When there are only 4 processors, then 80% of the parallel functions can be executed by 4 processors by dividing the task into 4 equal parts only(unlike infinite parts in previous part of question).

Hence time taken to process parallel functions = 0.8x/4 = 0.2x

Hence total time taken = time taken to process sequential task + 0.2x = 0.2x + 0.2x = 0.4x

Hence maximum speed up = x/0.4x = 2.5

Please comment for any clarification