Question

Assume that 40% of a program is parallelizable. In 15% of the parallel portion, 200x speed up has achieved. And in the 25% of the parallel portion 300x speed up has achieved

What is the overall speed up for that program?
What is the overall speed up if we could achieve infinite speed up for 40% of the program?

Answer 1

In the question it is mentioned that 15% of the parallel portion, 200x speed up has achieved and in the 25% of the parallel portion 300x speed up has achieved. Which means the current execution time for those segments will decrease 200 times for 15% of the program and 300 times for 25% of the program.

According to the question 40% of the program supports parallel execution, which means that 40% of the total program can allow concurrent execution. Also, we can speed up 40% of the program.

Since there is nothing mentioned in the question, I will assume that each segment of the program takes uniform time to execute.

Let us assume that the current execution time of the entire program is 100 seconds.

For the 15% of the program, the execution time is 15 seconds.

After the speedup, the time taken to execute the 15% program segment is = (15/200) seconds = 0.075 seconds

For the 25% of the program, the execution time is 25 seconds.

After the speedup, the time taken to execute the 25% program segment is = (25/300) seconds = 0.083 seconds

For the 60% of the program which does not allow parallel processing, the execution time will remain same as 60 seconds.

So, the total time to execute the program is = (60+0.083+0.075) seconds = 60.15833 seconds

Total speed up for the program is = (100/60.15833) = 1.6622 times

2nd Part:

If it is possible to achieve infinite speed up for 40% of the program then the execution time required for 40% of the program segment will be close to zero, which is negligible.

So, the entire program execution time will be = (60+0) seconds = 60 seconds.

Total speed up for the program is = (100/60) = 1.667 times

Hope this helps.