A’s Law

There exists a law called A’s Law, where A = Amdahl.

I came across this law while I was gobbling a multi-thread library that’s new to me: OpenMP.

The idea of A’s Law is that the speedup of a program running on multiple processors in parallel is limited by the sequential section of the program. One good example of this is that if a program runs 10 hours in sequential order, and 1 hour (10%) of which cannot be made into multiple threads. Even though the rest 9 hours can be executed in parallel, the minimum execution time cannot be shorter than 1 hour (think even if the rest 9 hours get executed in 0.0001ms in parallel). Therefore the upper bound for speedup is 10x, because 10 hours work is finished in 1 hour at best case.

Source:
http://en.wikipedia.org/wiki/Amdahl%27s_law

Advertisements