Amdahl’s Law

• This rule states the following for parallel programs:

• • The non-parallel (serial) fraction s of the program includes the communication and synchronization overhead
  • Thus, the maximum parallel Speedup S(p) for a program that has parallel fraction f:

The non-parallel fraction of the code (I.e. overhead)

imposes the upper limit on the scalability of the code

(1) 1 = s + f ! program has serial and parallel fractions

(2) T(1) = T(parallel) + T(serial)

= T(1) *(f + s)

= T(1) *(f + (1-f))

(3) T(p) = T(1) *(f/p + (1-f))

(4) S(p) = T(1)/T(p)

= 1/(f/p + 1-f)

< 1/(1-f) ! for p-> inf.

(5) S(p) < 1/(1-f)

Previous slide

Next slide

Back to first slide

View graphic version