1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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).

Also see: https://computing.llnl.gov/tutorials/parallel_comp

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Azmisov Jun 4 '17 at 1:59
  • $\begingroup$ 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? $\endgroup$ – Azmisov Jun 4 '17 at 2:00
  • $\begingroup$ 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. $\endgroup$ – TRex22 Jun 19 '17 at 20:46

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.