1
$\begingroup$

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:

S=1/((1-P)+(P/N)

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

$\endgroup$
8
  • 1
    $\begingroup$ Run the program on various values of $N$, then find the value of $P$ that best fits the results. $\endgroup$ – Yuval Filmus Apr 27 '20 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 '20 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$ – Yuval Filmus Apr 27 '20 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$ – Yuval Filmus Apr 27 '20 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 '20 at 18:29
2
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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