# Estimating P in Amdahl's Law theoretically and in practice

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?

• Run the program on various values of $N$, then find the value of $P$ that best fits the results. – Yuval Filmus Apr 27 '20 at 7:31
• This I think answers the practical way to estimate P. Is there a theoretical way to do that ? – Steve Apr 27 '20 at 8:33
• 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. – Yuval Filmus Apr 27 '20 at 9:14
• 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). – Yuval Filmus Apr 27 '20 at 9:16
• Thank you for your answer, Yuval. Is there a known theoretical estimate that people usually utilize that you are familiar of? – Steve Apr 27 '20 at 18:29