Amdahl's Law examples

Question

Amdahl's Law states that the maximal speedup of a computation where the fraction S of the computation must be done sequentially going from a 1 processor system to an N processor system is at most

                 1 / (S + [(1 - S) / N])

Does anyone know of books or notes where the actual analysis of the code, for some non-trivial computation, for determining the fraction S is done ?

Zealot

Answer 1

There is a very good discussion of Amdahl's law in the Microsoft Patterns and Practices book on Parallel Programming with .NET.

Doing a detailed analysis of the code is going to be quite difficult - as every situation is unique.

However, it should be something that can be easily approximated, provided you have the mechanisms to determine the amount of concurrency. By changing the usable concurrency and profiling, you should be able to estimate S by solving the equation in reverse.

Shogun

Answer 2

Here are a few links that might help you out:

Microsoft Research | Discussion of Amdahl's Law in the Multicore Age

Evaluation and Analysis of Amadahl's (and Gustafson's) Laws

Abstract on Estimating Speed Multipliers | Discusses Amdahl's Law Briefly

Hope they help you out.

Means

Answer 3

The principle involved isn't unique to parallelization. If 25% of the program's time is spent doing some particular operation, making everything but that 25% happen instantly (without affecting the 25%) would leave a program that took 25% of the original time, and was thus four times as fast.

In cases where an algorithm has clear phases that are or are not parallelizable, the application of the above formula would be simple--figure that N way parallelization will make the parts that are parallelizable run N times as fast, while the parts that aren't parallelizable will run at normal speed. In practice, I don't think most algorithms consist entirely of parts that are either 100% parallelizable or 100% sequential. In most interesting cases, algorithms can run largely in parallel, but have various ordering constraints; in some cases, the precise ordering constraints may be data-dependent. As such, the "percentage of parallelization" could be variable based upon the number of processors, among other things, and so trying to plug it into a formula would not be very helpful.

Cutinize