StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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.</p> <p>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:</p> <p><img src="https://i.stack.imgur.com/SmdQE.png" alt="enter image description here"></p> <p>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'.</p> <p>Let's first do this without the "parallel overhead" term involving log(p):</p> <p><img src="https://i.stack.imgur.com/HeEYL.gif" alt="enter image description here"></p> <p>Eg, efficiency is always 1, so you don't need to do anything to problem size as you vary processor number.</p> <p>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 <img src="https://i.stack.imgur.com/3k280.png" alt="enter image description here"></p> <p>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.</p> <p>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.</p> <p>In the particular case you're looking at, p=8, k=2, and you need to increase your problem size by 2+2/3.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload