# Calculate execution time from linear speedup

Given an execution time $t(c_1)$ and linear speedup $s$, how do you calculate the execution time for $c_2$ processor cores?

(Assuming Gustafson's law, or in other words, $t(\infty)=0$)

My ideas:

I haven't found any references that give formulas for calculating execution time, surprisingly. However, I think you can derive a formula from the speedup equation: $$speedup = t(1)/t(c)$$ The problem is, I'm pretty sure this is not what people are referring to when they give you a "linear speedup" factor $s$. I haven't been able to find any exact definitions on what "linear speedup" is. I can be sure that linear speedup means that $speedup$ is linearly dependent on cores. But what is the equation?

I looked at the superlinear speedup values from the introduction of this paper. The data points $(c, speedup)$ are $(2, 2.46)$, $(4, 4.68)$, and $(8, 9.59)$. From these, it would seem the formula is: $$s = speedup/c$$ This gives $1.23$, $1.17$, and $1.20$ for $s$; since $s$ should be constant, this seems like it could be correct. Assuming this is correct, you get: $$t(1) = s*c_1*t(c_1)\\ t(c_2) = c_1*t(c_1)/c_2$$ But that can't be right, can it? It's not even dependent on $s$ anymore.

Perhaps one potential problem is that $s$ is only linear for $c>1$; so maybe you cannot estimate $t(1)$ using that formula. I've thought of a way to correct for this, by devising this formula: $$s*(c-1)+1 = speedup$$ This makes sure speedup is one for $c=1$, as you'd expect. With the modified formula, you get $1.46$, $1.23$, and $1.23$ for $s$. There is a greater variance in $s$, but not by much. So it seems like it could be a correct model. Both models work for linear speedup of one. I tried to find more datasets of non-one linear speedup, but couldn't find any. So I can't confirm whether this model works universally. Assuming this model, we get: $$t(c_2) = \frac{t(1)}{s*(c_2-1)+1}\\ \text{given: } t(1) = t(c_1)*(s*(c_1-1)+1)$$ This formula is at least dependent on $s$, as I would expect. But I feel like my corrected formula for $s$, from which this was derived, was rather arbitrary. For one thing, $s$ is undefined at $c=1$, even if it does make sure $speedup=1$. Secondly, the final equation for $t(c_2)$ is not very intuitive; given $s=.7$ you'd think $t(2)$ would get a $1.4x$ speedup, not a $1.7$ speedup.

What are your thoughts? What am I doing wrong here? What is the correct derivation?

## 1 Answer

The term you're looking for is called parallel efficiency, which is a measure of how efficiently an algorithm uses its parallel resources. And you are correct that it is:

E = parallel speedup / p


Where p is the number of processors (or cores).

Your equation for t(c_2) is still valid, when the parallel efficiency is the same for c_1 and c_2, as it's equivalent to:

t(c_1) / c_1 = t(c_2) / c_2


A parallel efficiency greater than one is truly possible. While it is observed sometimes, this is because of NUMA effects which accompany the access to more processors / cores (i.e., more of the problem fits in caches).

• Thanks for the resources. Based on what you've said, I'm wondering if speedup is given relatively to a non-parallelized algorithm. It seems efficiency of $t(1)/(c*t(c))$ will always be one. So, I'm guessing efficiency relative to $t(1)$ (a parallelized algorithm running with only one processor) is always 1; but if your serial version "t_s \neq t(1)", then efficiency will be something other than one. Is that right? – Azmisov Jun 4 '17 at 1:59
• Also, just to make sure, is the assumption that efficiency is the same for $c_1$ and $c_2$ correct, when using Gustafson's law? – Azmisov Jun 4 '17 at 2:00
• Funnily I wrote an exam on this today. A good resource can be found in these slides Introduction to Parallel Computing. I'm pretty sure there are some issues with the isoefficency derivations but I have not yet written up my notes and my courses notes are not really publicly available. – TRex22 Jun 19 '17 at 20:46