并行计算机中应用程序的性能和可伸缩性

Question

请参见Hwang的“ 高级计算机体系结构”的一部分，其中讨论了并行处理中性能的可伸缩性。

问题是

1-关于图（a）， theta （指数）和alpha （常数）的例子是什么？ 通过增加计算机数量，哪些工作负载呈指数增长？ 另外，在多核/计算机上工作时，我还没有看到持续的工作量。

2-关于图（b），为什么指数工作负载的效率最高？ 无法理解！

3-关于图（c），固定内存模型是什么意思？ 固定内存工作负载听起来像alpha ，被称为固定负载模型。

4-关于图（c），固定时间模型是什么意思？ 我认为“固定”一词是错误的。 我将其解释为“恒定”。 文本说，固定时间模型实际上是（a） gamma的线性。

5-关于图（c），为什么指数模型（内存绑定）没有达到通信限制？

您可能会看到描述下图的文字。

我也不得不说我不明白最后一行。 有时，即使仅使用处理器即可达到最短的时间，系统利用率（或效率）也可能非常差 ！

有人可以列举一些例子吗？

Answer 1

工作量是指输入大小或问题大小，基本上是要处理的数据量。 机器大小是处理器的数量。 效率定义为加速除以机器尺寸。 效率指标比加速¹更有意义。 为此，请考虑例如在并行计算机上实现2倍加速的程序。 这听起来可能令人印象深刻。 但是，如果我还告诉您并行计算机具有1000个处理器，那么2倍的加速速度确实非常糟糕。 另一方面，效率既捕获了加速，又捕获了实现它的环境（所使用的处理器数量）。 在此示例中，效率等于2/1000 = 0.002。 请注意，效率介于1（最佳）和1 / N（最差）之间。 如果我只告诉您效率为0.002，那么即使我没有告诉您处理器的数量，您也会立即意识到它很糟糕。

图（a）显示了不同类型的应用程序，它们的工作负载可以以不同的方式改变以利用特定数量的处理器。 也就是说，应用程序的缩放比例不同。 通常，添加更多处理器的原因是为了能够利用更大工作负载中越来越多的并行性。 Alpha线表示具有固定大小工作负载的应用程序，即并行性的数量是固定的，因此添加更多处理器不会带来任何额外的加速。 如果加速是固定的，但N变大，则效率会降低，其曲线将看起来像1 / N。 这样的应用程序具有零可扩展性。

其他三条曲线表示的应用程序可以通过以某种方式增加工作量来随着处理器数量的增加（即可伸缩性）而保持高效率。 伽玛曲线代表理想的工作负载增长。 这被定义为以现实的方式保持高效的增长。 也就是说，它不会对系统的其他部分（例如内存，磁盘，处理器间通信或I / O）施加太大的压力。 因此可扩展性是可以实现的。 图（b）显示了伽马的效率曲线。 由于较高的并行性的开销以及执行时间不变的应用程序的串行部分，效率会稍有下降。 这代表了一个完美的可扩展应用程序：我们可以通过增加工作量来实际使用更多处理器。 Beta曲线表示一个可扩展的应用程序，即，可以通过增加工作量来获得良好的加速，但效率下降得更快一些。

Theta曲线代表了一种可以实现非常高效率的应用，因为有太多数据可以并行处理。 但是，这种效率只能在理论上实现。 这是因为工作量必须成倍增长，但实际上，内存系统无法有效地处理所有这些数据。 因此，尽管理论上效率很高，但仍认为此类应用程序的可伸缩性较差。

通常，当增加处理器数量时，具有亚线性工作负载增长的应用程序最终将受到通信的约束，而具有超线性工作负载增长的应用程序最终将受到内存的限制。 这很直观。 处理大量数据（theta曲线）的应用程序大部分时间都花在很少的通信上，独立地处理数据。 另一方面，处理少量数据（β曲线）的应用程序倾向于在处理器之间进行更多的通信，其中每个处理器使用少量数据来计算某些东西，然后与其他人共享以进行进一步处理。 Alpha应用程序也受通信限制，因为如果您使用太多的处理器来处理固定数量的数据，则通信开销将太高，因为每个处理器都将在一个很小的数据集上运行。 之所以调用固定时间模型，是因为它可以很好地扩展（使用更多可用处理器处理更多数据大约需要相同的时间）。

我还不得不说我不明白最后一行。有时，即使仅使用处理器就可以达到最短的时间，系统利用率（或效率）也可能很差！

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

示例：并行二进制搜索

串行二进制搜索的执行时间等于log ₂ （N），其中N是要搜索的数组中元素的数量。 可以通过将阵列划分为P分区来并行化，其中P是处理器的数量。 然后，每个处理器将在其分区上执行串行二进制搜索。 最后，所有部分结果都可以串行方式合并。 因此，并行搜索的执行时间为（log ₂ （N）/ P）+（C * P）。 后一项代表间接费用和将部分结果合并的串行部分。 它在P和C是线性的，只是一个常数。 因此加速为：

对数₂ （N）/（（对数₂ （N）/ P）+（C * P））

效率就是P除以。 应该增加多少工作量（阵列的大小）以保持最大效率（或使加速尽可能接近P ）？ 例如，考虑一下当我们相对于P线性增加输入大小时会发生什么。 那是：

N = K * P，其中K是一个常数。 则加速为：

log ₂ （K * P）/（（log ₂ （K * P）/ P）+（C * P））

当P接近无穷大时，加速（或效率）如何变化？ 请注意，分子具有对数项，但是分母具有对数加上一个阶数为1的多项式。该多项式的增长比对数快。 换句话说，分母的增长速度比分子快，并且加速（因此效率）迅速接近零。 显然，我们可以通过更快地增加工作量来做得更好。 特别是，我们必须成倍增加。 假设输入大小为以下形式：

N = K ^P ，其中K为某个常数。 则加速为：

log ₂ （K ^P ）/（（log ₂ （K ^P ）/ P）+（C * P））

= P * log ₂ （K）/（（P * log ₂ （K）/ P）+（C * P））

= P * log ₂ （K）/（log ₂ （K）+（C * P））

现在好一点了。 分子和分母都线性增长，因此加速基本上是一个常数。 这仍然很糟糕，因为效率是该常数除以P ，随P增加而急剧下降（它看起来像图（b）中的alpha曲线）。 现在应该清楚输入的大小应采用以下形式：

N = K ^{P 2} ，其中K为某个常数。 则加速为：

log ₂ （K ^{P 2} ）/（（log ₂ （K ^{P 2} ）/ P）+（C * P））

= P ² * log ₂ （K）/（（P ² * log ₂ （K）/ P）+（C * P））

= P ² * log ₂ （K）/（（P * log ₂ （K））+（C * P））

= P ² * log ₂ （K）/（C + log ₂ （K）* P）

= P * log ₂ （K）/（C + log ₂ （K））

理想情况下，术语log ₂ （K）/（C + log ₂ （K））应该为1，但这是不可能的，因为C不为零。 但是，通过使K任意大，可以使它任意接近1。 因此，与C相比， K必须很大。 这使输入大小更大，但不会渐近更改。 请注意，这两个常数都必须通过实验确定，并且它们特定于特定的实现和平台。 这是θ曲线的一个例子。

---

（1）回想一下，加速比=（单处理器上的执行时间）/（N个处理器上的执行时间）。 最小加速比为1，最大加速比为N。