Amdahls’s Law

Amdahl’s law describes the increase in speed that can be gained from parallelizing a computation across multiple processors. It is defined by:

S = 1 / ( 1 – p + p/n)

Where

S= the Speedup gained by running a computation in parallel. This is the time taken to run the computation on a single processor / time taken to run the computation on n processors.

p = the fraction of the job that can be executed in parallel.

N = the number of processors

The above formula is derived as follows:

Time taken to run a computation on multiple processors = time taken for the parallelizable part of the job + time taken on the non-parallelizable part of the job

Time taken on parallelizable part of the job = Parallelizable fraction of the job / number of processors

= p/n

The sequential part of the job is given by 1-p

Note that part of the non-parallelizable, or sequential part of the computation may involve the overhead of coordinating the multiple processors doing the work.

Thus the ratio of the sequential to the parallelizable part is given by :

S = 1 / (1-p + p/n)

Example,

For a perfectly parallelizable job running on 5 processors, the Speedup is

S= 1/ (1-1+ 1/5 ) = 5 times speedup (500%)

For a job that is 80% parallelizable

S= 1/(1-0.8 + 1/0.8) = = 1/1.45 = 45 % speedup

**References**

- Maurice Herlihy and Nir Shavit. 2008.
*The Art of Multiprocessor Programming*. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

### Like this:

Like Loading...