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 couldbe 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?
Calculate execution time from linear speedup
runtime analysis;distributed systems;parallel computing