并行计算机中应用程序的性能和可扩展性

工作量指的是输入大小或问题大小,基本上就是要处理的数据量。机器大小是处理器的数量。效率定义为加速比除以机器尺寸。效率指标比加速更有意义 . 要了解这一点,请考虑一个在并行计算机上实现2倍加速的程序。这听起来可能令人印象深刻。但是如果我也告诉你并行计算机有1000个处理器,2倍的加速真的很糟糕。另一方面,效率则反映了加速和实现加速的环境(使用的处理器数量)。在本例中,效率等于2/1000=0.002。注意,效率在1(最佳)和1/N(最差)之间。如果我告诉你效率是0.002,你会立刻意识到这很糟糕,即使我没有告诉你处理器的数量。

其他三条曲线表示通过以某种模式增加工作负载,在处理器数量不断增加的情况下(即,可伸缩性)可以保持高效率的应用程序。gamma曲线表示理想的工作负载增长。这被定义为保持高效率的增长,但在 . 也就是说,它不会对系统的其他部分(如内存、磁盘、处理器间通信或I/O)施加太大压力。因此可伸缩性是可以实现的。图(b)显示了伽马的效率曲线。由于更高的并行性开销和应用程序的串行部分(其执行时间不变),效率略有下降。这代表了一个完全可扩展的应用程序:我们可以通过增加工作负载来实际使用更多的处理器。beta曲线表示的应用程序具有一定的可伸缩性,即通过增加工作负载可以获得良好的加速,但效率会更快地下降。

通常,当增加处理器数量时,具有次线性工作负载增长的应用程序最终会受到通信限制,而具有超线性工作负载增长的应用程序最终会受到内存限制。这是直观的。处理大量数据(θ曲线)的应用程序花费大部分时间独立处理数据,几乎没有通信。另一方面,处理中等数量数据(beta曲线)的应用程序往往在处理器之间有更多的通信,其中每个处理器使用少量数据来计算某个数据,然后与其他处理器共享该数据以进行进一步处理。alpha应用程序也是通信受限的,因为如果您使用太多的处理器来处理固定数量的数据,那么通信开销将太高,因为每个处理器将在一个很小的数据集上操作。之所以称固定时间模型,是因为它的伸缩性非常好(使用更多可用处理器处理更多数据所需的时间大致相同)。

我也不得不说有时我不明白最后一句话,

如何达到最短执行时间?只要加速比在增加,就增加处理器的数量。一旦加速率达到一个固定值,那么就达到了达到最小执行时间的处理器数量。但是,如果加速比很小,效率可能会很低。这自然来自效率公式。例如,假设一个算法在100个处理器的系统上实现了3倍的加速比,并且进一步增加处理器的数量不会增加加速比。因此,使用100个处理器可实现最小执行时间。但效率仅为3/100=0.03。

示例:并行二进制搜索

串行二进制搜索的执行时间等于log ₂ (N) 在哪里 N 数组中要搜索的元素数。这可以通过将数组划分为 P 分区在哪里 P ₂ (N) /P)+(C*P)。后一项表示开销和组合部分结果的串行部分。它是线性的 P C 只是一些常数。所以加速是:

日志 ₂ (N) /((对数) ₂ (N) /P)+(C*P)

效率就是除以 P . 工作负载(数组的大小)应该增加多少以保持最大的效率(或者使加速比接近 尽可能)?例如,考虑当我们线性地增加输入大小时会发生什么 P . 即:

N=K*P,式中 K 是一个常数。然后加速:

(K*P)/(对数) (K*P)/P)+(C*P)

接近无穷大?注意,分子有一个对数项,分母有一个对数加一个1次多项式,多项式的增长速度比对数快。换言之,分母的增长速度比分子的增长速度快,加速比(因此效率)很快接近于零。很明显,我们可以通过以更快的速度增加工作量来做得更好。特别是,我们必须指数增长。假设输入大小为以下形式:

N=K ,在哪里 K 是一个常数。然后加速:

日志 ₂ (千) ^P )/((日志) ₂ )/P) (+(C*P))

=P*对数 _{2 2} (K) /P)+(C*P)

₂ (K) /(对数) ₂

现在好多了。分子和分母都是线性增长的,所以加速比基本上是一个常数。这仍然很糟糕,因为效率将是常数除以 ,当 增加(它看起来像图(b)中的alpha曲线)。现在应该很清楚,输入大小应该是这样的:

^{P 2} ,在哪里 K 是一个常数。然后加速:

日志 ₂ (千) ² )/((日志) ₂ (千) ^P )/P) (+(C*P))

=P ² *日志 ₂ (K) /((P ² ₂ (K) /P)+(C*P)

² *日志 (K) /((P*log) (K) )+(C*P)

=P ² *日志 ₂ (K) *P)

=P*对数 _{2 2} (K) ()

理想情况下,术语log (K) /(C+对数) ₂ C K 任意大。所以呢 K 必须非常大 C . 这使得输入的大小更大,但不会渐进地改变它。请注意,这两个常数都必须通过实验确定,并且它们特定于特定的实现和平台。这是θ曲线的一个例子。