In parallel computing, Amdahl's law is mainly used to predict the theoretical maximum speedup for program processing using multiple processors. If we denote the speed up by S then Amdahl’s law is given by the formula:


where P is the proportion of a system or program that can be made parallel, and 1-P is the proportion that remains serial. My question is: how can we compute or estimate P for a given program?

More specifically, my question has two parts:

How can we compute P theoretically? How can we compute P in practice?

reference: https://www.techopedia.com/definition/17035/amdahls-law

  • 1
    $\begingroup$ Run the program on various values of $N$, then find the value of $P$ that best fits the results. $\endgroup$ Apr 27, 2020 at 7:31
  • $\begingroup$ This I think answers the practical way to estimate P. Is there a theoretical way to do that ? $\endgroup$
    – Steve
    Apr 27, 2020 at 8:33
  • $\begingroup$ Amdahl's law is an approximation. If you actually run an experiment, I predict that you won't see the speedup predicted by Amdahl's law, that is, you wouldn't be able to find any appropriate $P$. In some sense, $P$ is a fictitious quantity. $\endgroup$ Apr 27, 2020 at 9:14
  • $\begingroup$ That said, suppose that your program is composed from a very sequential part followed by an embarrassingly parallel part. By timing each part, you can easily find $P$. If you are against timing, you can make some "theoretical estimate", but such theoretical estimates are typically only qualitative (are only correct up to constant factors). $\endgroup$ Apr 27, 2020 at 9:16
  • $\begingroup$ Thank you for your answer, Yuval. Is there a known theoretical estimate that people usually utilize that you are familiar of? $\endgroup$
    – Steve
    Apr 27, 2020 at 18:29

1 Answer 1


Amdahl divided a program in two parts, serial and parallel, and assumed each processor to have same compute ability. This concept has been further refined by Hill and Marty Amdahl's law in multi-core era, in other words it is not necessary that every processor should have same the compute ability and Cassidy Beyond Amdahl's Law: An Objective Function That Links Multiprocessor Performance Gains to Delay and Energy, in other words why divide in only two parts.

After a brief overview of Amdahl's law, I answer the question how to measure the serial (1-P) and parallel (P) parts of a program.

  1. Static instrumentation: Put a function that gives the current time like gettimeofday in Linux at the start of the program, the point where you create threads and points where you join threads and if necessary (if your program does a lot of post processing) at the end of program. Take differences and you will have the P value. Use the single threaded program. If you want to have more precision in measurement use the rdtscp instruction on Intel processors Excellent blog by Dr. John McCalpin.
  2. Dynamic instrumentation: It is possible to do the above even when you don't have the source code to do static instrumentation. You can use library preloading (LD_PRELOAD) or the Intel Pin tool Introduction to Pin using examples or similar dynamic binary instrumentation tools like Dynamorio, Valgrind and Linux perf Tutorial by Brendan gregg. All of them are established frameworks, completely free, with multiple research tools using them.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.