效率与并行与串行加速 [英] Efficiency & speedup of parallel vs. serial

问题描述

目前，我正在阅读一份研究报告，该报告是我的教授在课堂上分发的.学习指南不是一项作业，而是一些知道考试期望的内容.我已经完成了除1个问题以外的所有问题，希望有人可以帮助我.

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.

这里是一个问题: 假设Tserial = n和Tparallel = n/p + log2(p)，其中时间以毫秒为单位，p是 进程数.如果我们将p增加k倍，请找到一个公式，说明为了保持恒定的效率，我们需要增加n多少.如果将进程数从8增加到16，我们应该将n增加多少?并行程序可扩展吗?

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.

推荐答案

注释和第一个答案都可以帮助您解决恒定并行计算时间的问题，但这与解决恒定效率问题有些不同.

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.

如上所述，并行效率是由您使用多个处理器的效率定义的. 100％的效率意味着您使用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:

因此，如果您将处理器数量增加k倍，而问题规模增加k'倍，那么现在您要考虑恒定的效率.

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

我们首先要做的是不涉及涉及log(p)的并行开销"一词:

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

例如，效率始终为1，因此，随着处理器数量的变化，您无需为问题大小做任何事情.

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

让我们看一下这里的渐近线-如果您已经拥有无限数量的处理器，那么您的效率已经为零(因为每个处理器的工作量为零，而开销却是无限的)，因此您可以使问题的大小保持不变;效率将保持不变.另一方面，您将永远无法增加问题的大小，以至于无法重新获得p = 1时的并行效率.那是100％，由于开销，您所做的任何事情都必然会少于该值.

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.

在您要查看的特殊情况下，p = 8，k = 2，您需要将问题大小增加2 + 2/3.

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

这篇关于效率与并行与串行加速的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！