Efficiency & speedup of parallel vs. serial

Question

Currently, I am reading over a study a guide that my professor handed out in class. The study guide is not an assignment, just something to know what to expect on an exam. I've completed all but 1 problem and was hoping someone could help me out.

Here is the question: Suppose Tserial = n and Tparallel = n/p + log2(p), where times are in miliseconds and p is the number of processes. If we increase p by a factor of k, find a formula for how much we’ll need to increase n in order to maintain constant efficiency. How much should we increase n by if we double the number of processes from 8 to 16? Is the parallel program scalable?

Any help in understanding this would be greatly appreciated.

Answer 1

Both the comment and the first answer help you solve for constant parallel compute time, but that's a little different than solving for constant efficiency.

As noted above, parallel efficiency is defined by how effectively you're making use of your multiple processors. 100% efficiency would mean that you're getting a factor of p speedup from using p processors; so efficiency is defined in terms of speedup per processor:

So now you want to consider constant efficiency if you're increasing the number of processors by a factor k and the problem size by a factor k'.

Let's first do this without the "parallel overhead" term involving log(p):

Eg, efficiency is always 1, so you don't need to do anything to problem size as you vary processor number.

But because there is some overhead, for constant efficiency you need to tackle larger problem sizes as you scale up. With the overhead term, you get

Let's look at the asymptotics here -- if you're already at an infinite number of processors, you're already at zero efficiency (because there's zero work per processor but an infinite overhead), so you can keep problem size constant; efficiency will stay the same. On the other hand, you're never going to be able to increase the problem size enough to regain the parallel efficiency you had at p=1; that was 100% and anything you do will necessarily have less than that because of the overhead.

Also note that the amount you have to increase the problem size is always going to be at least a little bit more than the factor by which you increase the number of processors.

In the particular case you're looking at, p=8, k=2, and you need to increase your problem size by 2+2/3.