Using Amdahl's Law and Measuring the Program

There are two rules of optimization that apply to parallel programming:

  • Focus on the part of the program that uses the most time.

  • Do not guess, measure.

Amdahl's Law

In the context of parallel programming, Gene Amdahl formalized a rule called Amdahl's Law, which states that the speed-up that is possible from parallelizing one part of a program is limited by the portion of the program that still runs serially.

The consequence may be surprising: parallelizing the part of your program where it spends 80% of its time cannot speed it up by more than a factor of five, no matter how many cores you run it on.

Therefore, to get maximum benefit from parallelizing your program, you could add parallelism to all parts of your program as suggested by Amdahl's Law. However, it is more practical to find where it spends most of its time and focus on areas that can provide the most benefit.

Do Not Guess - Measure

This leads to another rule of optimization: Do Not guess - Measure. Programmers' intuitions about where their programs are spending time are notoriously inaccurate. Intel Advisor includes a Survey tool you can use to profile your running program and measure where it spends it time.

After you add Intel Advisor annotations to your program to mark the proposed parallel code regions, run the Suitability tool to predict the approximate maximum performance gain for the program and the annotated sites. These estimated performance gain values are based on a model of parallel execution that reflects the impact of Amdahl's law.

For more complete information about compiler optimizations, see our Optimization Notice.