Question

Amdahl's law: Suppose you ran an application on a single processor in 1.5 hours. Upon careful examination of the code, you found out that the application is in fact 90% parallelizable.
a) If you can run this application on a computer with 10 processors, what would be the execution time?
b) If you can run this application on a computer with an unlimited number of processors, what would be the execution time?

Answer 1

Solution:

Any program (or algorithm) which can be parallelized can be broken into two parts:

• A part which cannot be parallelized
• A part which can be parallelized

Let the total time for serial execution be T and the total time of Non-parallelizable part be N. Then, the total time of parallelizable part will be T-N.

T = N + (T - N)

According to Amdahl's law, the total execution time of the program when the parallelizable part is executed using X threads or CPUs is:

T(X) = N + (T - N) / X [where 'X' is the number of processors]

Now, in the problem stated above, it is given that an application runs on a single processor in 1.5 hours. This means the total time for serial execution is 1.5 hours. Also, the part which is parallelizable (T - N) is 90%. Therefore, the part which is non-parallelizable (N) is 10%.

(a) If the application is ran on a computer with 10 processors, then X = 10.

Let us assume that the serial execution be done in x minutes.

Therefore, parallelized execution will take, T(10) = 0.1x + (0.9x)/10 = 0.1x + 0.09x = 0.19x

Now, if x actually is equivalent to execution time of 1.5 hours = 90 mins, then 0.19x will be equivalent to execution time of 0.19 * 90 minutes = 17.1 minutes

Answer: If the application is run on a computer with 10 processors, then the execution time will be 17.1 minutes.

(b) If the application is ran on a computer with unlimited processors, then X = infinity (inf).

Let us assume that the serial execution be done in x minutes.

Therefore, parallelized execution will take, T(inf) = 0.1x + (0.9x)/inf = 0.1x + 0 = 0.1x

Now, if x actually is equivalent to execution time of 1.5 hours = 90 mins, then 0.1x will be equivalent to execution time of 0.1 * 90 minutes = 9 minutes

Answer: If the application is run on a computer with unlimited processors, then the execution time will be 9 minutes.