并行计算机中应用程序的性能和可扩展性
Performance and scalability of applications in parallel computers
请参阅 Hwang 的 Advanced Computer Architecture 中的图片，其中讨论了并行处理中性能的可扩展性。
问题是
1-关于图(a)，theta（指数）和alpha（常数）的例子是什么？哪些工作负载随着机器数量的增加呈指数级增长？此外，在使用 multi cores/computers.
时，我没有看到持续的工作量
2-关于图(b)，为什么指数工作负载的效率最高？看不懂！
3-关于图(c)，固定内存模型是什么意思？固定内存工作负载听起来像 alpha，它被称为固定负载模型。
4-关于图(c)，固定时间模型是什么意思？我认为 "fixed" 一词具有误导性。我将其解释为 "constant"。文中说fixed-time model其实就是(a)中的linear gamma.
5-关于图(c)，为什么指数模型（内存限制）没有达到通信限制？
您可能会看到下面描述图的文字。
我也不得不说我不明白最后一行有时，即使只用处理器达到最小时间，系统利用率（或效率）也可能很差!!
有人可以举例说明吗？
工作量是指输入大小或问题大小，基本上是要处理的数据量。机器大小是处理器的数量。效率定义为加速比除以机器尺寸。效率指标比 speedup1 更有意义。要看到这一点，请考虑一个在并行计算机上实现 2 倍加速的程序。这听起来可能令人印象深刻。但如果我也告诉你，并行计算机有 1000 个处理器，2X 加速真的很糟糕。另一方面，效率同时捕获加速和实现它的上下文（使用的处理器数量）。在此示例中，效率等于 2/1000 = 0.002。请注意，效率介于 1（最佳）和 1/N（最差）之间。如果我只告诉你效率是 0.002，你会立即意识到这很糟糕，即使我不告诉你处理器的数量。
图 (a) 显示了不同类型的应用程序，其工作负载可以以不同的方式变化以利用特定数量的处理器。也就是说，应用程序的规模不同。通常，添加更多处理器的原因是为了能够在更大的工作负载中利用越来越多的并行性。 alpha 线表示具有固定大小工作负载的应用程序，即并行量是固定的，因此添加更多处理器不会带来任何额外的加速。如果加速比固定，但 N 变大，则效率降低，其曲线看起来像 1/N。这样的应用程序具有零可扩展性。
其他三条曲线表示可以通过以某种模式增加工作负载来随着处理器数量的增加（即可扩展）保持高效率的应用程序。伽马曲线代表理想的工作负载增长。这被定义为保持高效率但以现实方式的增长。也就是说，它不会对系统的其他部分如内存、磁盘、处理器间通信或 I/O 造成太大压力。因此可扩展性是可以实现的。图（b）显示了gamma的效率曲线。由于更高并行度的开销以及执行时间不变的应用程序的串行部分，效率略有下降。这代表了一个完美可扩展的应用程序：我们可以通过增加工作负载来实际使用更多的处理器。 beta 曲线表示应用程序具有一定的可扩展性，即，可以通过增加工作负载来实现良好的加速，但效率下降得更快。
theta 曲线表示可以实现非常高效率的应用程序，因为可以并行处理的数据非常多。但这种效率只能在理论上实现。这是因为工作负载必须呈指数增长，但实际上，内存系统无法有效处理所有这些数据。因此，尽管理论上效率非常高，但这样的应用程序被认为是可扩展性差的。
通常，随着处理器数量的增加，具有次线性工作负载增长的应用程序最终会受到通信限制，而具有超线性工作负载增长的应用程序最终会受到内存限制。这是直观的。处理大量数据（theta 曲线）的应用程序大部分时间都在独立处理数据，几乎没有通信。另一方面，处理中等数据量（beta 曲线）的应用程序往往在处理器之间有更多的通信，其中每个处理器使用少量数据来计算某些东西，然后与其他处理器共享它以进行进一步处理。 alpha 应用程序也是通信绑定的，因为如果您使用太多处理器来处理固定数量的数据，那么通信开销就会太高，因为每个处理器都将在一个很小的数据集上运行。固定时间模型之所以这样称呼是因为它的扩展性非常好（使用更多可用处理器处理更多数据所需的时间大致相同）。
I also have to say that I don't understand the last line Sometimes,
even if minimum time is achieved with mere processors, the system
utilization (or efficiency) may be very poor!!
如何达到最短执行时间？只要加速增加，就增加处理器的数量。一旦加速达到固定值，那么您就达到了达到最短执行时间的处理器数量。但是，如果加速比很小，效率可能会很差。这自然地遵循效率公式。例如，假设一个算法在 100 个处理器的系统上实现了 3 倍的加速，并且进一步增加处理器的数量不会增加加速。因此，最短执行时间是使用 100 个处理器实现的。但效率仅为3/100=0.03.
示例：并行二进制搜索
串行二进制搜索的执行时间等于 log2(N)，其中 N 是要搜索的数组中的元素数。这可以通过将数组划分为 P 个分区来并行化，其中 P 是处理器的数量。然后每个处理器将对其分区执行串行二进制搜索。最后，所有部分结果可以以串行方式组合。所以并行搜索的执行时间为(log2(N)/P) + (C*P)。后一项表示开销和组合部分结果的串行部分。它在 P 中是线性的，而 C 只是一些常数。所以加速是：
log2(N)/((log2(N)/P) + (C*P))
效率就是除以P。应该增加多少工作负载（数组的大小）以保持最高效率（或使加速尽可能接近 P）？例如，考虑当我们相对于 P 线性增加输入大小时会发生什么。即：
N = K*P，其中 K 是某个常数。那么加速是：
log2(K*P)/((log2(K*P)/P) + (C*P ))
随着 P 接近无穷大，加速（或效率）如何变化？请注意，分子有一个对数项，但分母有一个对数加上一个次数为 1 的多项式。多项式的增长速度比对数快。换句话说，分母的增长速度比分子快，加速比（以及效率）迅速接近零。很明显，我们可以通过以更快的速度增加工作量来做得更好。特别是，我们必须成倍增加。假设输入大小为以下形式：
N = KP，其中 K 是某个常数。那么加速是：
log2(KP)/((log2(KP)/P) + (C*P))
= P*log2(K)/((P*log2(K)/P) + (C* P))
= P*log2(K)/(log2(K) + (C*P))
现在好多了。分子和分母都是线性增长的，所以加速比基本上是一个常数。这仍然很糟糕，因为效率将是常数除以 P，随着 P 急剧下降
增加（它看起来像图 (b) 中的 alpha 曲线）。现在应该清楚输入大小应该是以下形式：
N = KP2，其中 K 是某个常数。那么加速是：
log2(KP2)/((log2(KP2)/P) + (C*P))
= P2*log2(K)/((P2* log2(K)/P) + (C*P))
= P2*log2(K)/((P*log2(K)) + (C*P))
= P2*log2(K)/(C+log2 (K)*P)
= P*log2(K)/(C+log2(K))
理想情况下，术语log2(K)/(C+log2(K))应该是一个，但那是不可能，因为 C 不为零。但是，我们可以通过使 K 任意大来使其任意接近 1。所以 K 与 C 相比必须非常大。这使得输入大小更大，但不会渐近地改变它。请注意，这两个常数都必须通过实验确定，并且它们特定于特定的实现和平台。这是 theta 曲线的一个例子。
(1) 回想一下加速比 =（单处理器上的执行时间）/（N 处理器上的执行时间）。最小加速比为 1，最大加速比为 N。
请参阅 Hwang 的 Advanced Computer Architecture 中的图片，其中讨论了并行处理中性能的可扩展性。
问题是
1-关于图(a)，theta（指数）和alpha（常数）的例子是什么？哪些工作负载随着机器数量的增加呈指数级增长？此外，在使用 multi cores/computers.
2-关于图(b)，为什么指数工作负载的效率最高？看不懂！
3-关于图(c)，固定内存模型是什么意思？固定内存工作负载听起来像 alpha，它被称为固定负载模型。
4-关于图(c)，固定时间模型是什么意思？我认为 "fixed" 一词具有误导性。我将其解释为 "constant"。文中说fixed-time model其实就是(a)中的linear gamma.
5-关于图(c)，为什么指数模型（内存限制）没有达到通信限制？
您可能会看到下面描述图的文字。
我也不得不说我不明白最后一行有时，即使只用处理器达到最小时间，系统利用率（或效率）也可能很差!!
有人可以举例说明吗？
工作量是指输入大小或问题大小，基本上是要处理的数据量。机器大小是处理器的数量。效率定义为加速比除以机器尺寸。效率指标比 speedup1 更有意义。要看到这一点，请考虑一个在并行计算机上实现 2 倍加速的程序。这听起来可能令人印象深刻。但如果我也告诉你，并行计算机有 1000 个处理器，2X 加速真的很糟糕。另一方面，效率同时捕获加速和实现它的上下文（使用的处理器数量）。在此示例中，效率等于 2/1000 = 0.002。请注意，效率介于 1（最佳）和 1/N（最差）之间。如果我只告诉你效率是 0.002，你会立即意识到这很糟糕，即使我不告诉你处理器的数量。
图 (a) 显示了不同类型的应用程序，其工作负载可以以不同的方式变化以利用特定数量的处理器。也就是说，应用程序的规模不同。通常，添加更多处理器的原因是为了能够在更大的工作负载中利用越来越多的并行性。 alpha 线表示具有固定大小工作负载的应用程序，即并行量是固定的，因此添加更多处理器不会带来任何额外的加速。如果加速比固定，但 N 变大，则效率降低，其曲线看起来像 1/N。这样的应用程序具有零可扩展性。
其他三条曲线表示可以通过以某种模式增加工作负载来随着处理器数量的增加（即可扩展）保持高效率的应用程序。伽马曲线代表理想的工作负载增长。这被定义为保持高效率但以现实方式的增长。也就是说，它不会对系统的其他部分如内存、磁盘、处理器间通信或 I/O 造成太大压力。因此可扩展性是可以实现的。图（b）显示了gamma的效率曲线。由于更高并行度的开销以及执行时间不变的应用程序的串行部分，效率略有下降。这代表了一个完美可扩展的应用程序：我们可以通过增加工作负载来实际使用更多的处理器。 beta 曲线表示应用程序具有一定的可扩展性，即，可以通过增加工作负载来实现良好的加速，但效率下降得更快。
theta 曲线表示可以实现非常高效率的应用程序，因为可以并行处理的数据非常多。但这种效率只能在理论上实现。这是因为工作负载必须呈指数增长，但实际上，内存系统无法有效处理所有这些数据。因此，尽管理论上效率非常高，但这样的应用程序被认为是可扩展性差的。
通常，随着处理器数量的增加，具有次线性工作负载增长的应用程序最终会受到通信限制，而具有超线性工作负载增长的应用程序最终会受到内存限制。这是直观的。处理大量数据（theta 曲线）的应用程序大部分时间都在独立处理数据，几乎没有通信。另一方面，处理中等数据量（beta 曲线）的应用程序往往在处理器之间有更多的通信，其中每个处理器使用少量数据来计算某些东西，然后与其他处理器共享它以进行进一步处理。 alpha 应用程序也是通信绑定的，因为如果您使用太多处理器来处理固定数量的数据，那么通信开销就会太高，因为每个处理器都将在一个很小的数据集上运行。固定时间模型之所以这样称呼是因为它的扩展性非常好（使用更多可用处理器处理更多数据所需的时间大致相同）。
I also have to say that I don't understand the last line Sometimes, even if minimum time is achieved with mere processors, the system utilization (or efficiency) may be very poor!!
如何达到最短执行时间？只要加速增加，就增加处理器的数量。一旦加速达到固定值，那么您就达到了达到最短执行时间的处理器数量。但是，如果加速比很小，效率可能会很差。这自然地遵循效率公式。例如，假设一个算法在 100 个处理器的系统上实现了 3 倍的加速，并且进一步增加处理器的数量不会增加加速。因此，最短执行时间是使用 100 个处理器实现的。但效率仅为3/100=0.03.
示例：并行二进制搜索
串行二进制搜索的执行时间等于 log2(N)，其中 N 是要搜索的数组中的元素数。这可以通过将数组划分为 P 个分区来并行化，其中 P 是处理器的数量。然后每个处理器将对其分区执行串行二进制搜索。最后，所有部分结果可以以串行方式组合。所以并行搜索的执行时间为(log2(N)/P) + (C*P)。后一项表示开销和组合部分结果的串行部分。它在 P 中是线性的，而 C 只是一些常数。所以加速是：
log2(N)/((log2(N)/P) + (C*P))
效率就是除以P。应该增加多少工作负载（数组的大小）以保持最高效率（或使加速尽可能接近 P）？例如，考虑当我们相对于 P 线性增加输入大小时会发生什么。即：
N = K*P，其中 K 是某个常数。那么加速是：
log2(K*P)/((log2(K*P)/P) + (C*P ))
随着 P 接近无穷大，加速（或效率）如何变化？请注意，分子有一个对数项，但分母有一个对数加上一个次数为 1 的多项式。多项式的增长速度比对数快。换句话说，分母的增长速度比分子快，加速比（以及效率）迅速接近零。很明显，我们可以通过以更快的速度增加工作量来做得更好。特别是，我们必须成倍增加。假设输入大小为以下形式：
N = KP，其中 K 是某个常数。那么加速是：
log2(KP)/((log2(KP)/P) + (C*P))
= P*log2(K)/((P*log2(K)/P) + (C* P))
= P*log2(K)/(log2(K) + (C*P))
现在好多了。分子和分母都是线性增长的，所以加速比基本上是一个常数。这仍然很糟糕，因为效率将是常数除以 P，随着 P 急剧下降
增加（它看起来像图 (b) 中的 alpha 曲线）。现在应该清楚输入大小应该是以下形式：
N = KP2，其中 K 是某个常数。那么加速是：
log2(KP2)/((log2(KP2)/P) + (C*P))
= P2*log2(K)/((P2* log2(K)/P) + (C*P))
= P2*log2(K)/((P*log2(K)) + (C*P))
= P2*log2(K)/(C+log2 (K)*P)
= P*log2(K)/(C+log2(K))
理想情况下，术语log2(K)/(C+log2(K))应该是一个，但那是不可能，因为 C 不为零。但是，我们可以通过使 K 任意大来使其任意接近 1。所以 K 与 C 相比必须非常大。这使得输入大小更大，但不会渐近地改变它。请注意，这两个常数都必须通过实验确定，并且它们特定于特定的实现和平台。这是 theta 曲线的一个例子。
(1) 回想一下加速比 =（单处理器上的执行时间）/（N 处理器上的执行时间）。最小加速比为 1，最大加速比为 N。