3.4 加速

如果编译器不并行化所花时间量占主体的程序部分，则不会发生加速。例如，如果并行化一个占用程序执行时间的百分之五的循环，则总加速仅限于百分之五。然而，任何改善都取决于工作量和并行执行开销的大小。

一般说来，并行化的程序执行所占的比例越大，加速的可能性就越大。

每个并行循环都会在启动和关闭期间发生少量开销。启动开销包括工作分配代价，关闭开销包括障碍同步代价。如果循环执行的工作总量不足够大，则不会发生加速。事实上，循环甚至可能减慢。如果大量程序执行工作由许多短并行循环完成，则整个程序可能减慢而不是加速。

编译器执行几个试图增大循环粒度的循环变换。其中某些变换是循环交换和循环合并。如果程序中的并行量很小或者分散在小并行区域，则加速通常很少。

按比例增大问题大小通常可提高程序中的并行程度。例如，考虑包含以下两部分的问题： 按顺序的二次部分，以及可并行化的三次部分。对于此问题，工作量的并行部分的增长速度比顺序部分的增长速度快。因此在某些点，除非达到资源限制，否则问题将加速。

尝试进行某些调节，使用指令、问题大小进行试验，重新构造程序，以便从并行 C 中获得最大好处。

3.4.1 Amdahl 定律

固定问题大小加速通常受 Amdahl 定律控制，该定律仅仅指出一个给定问题中的并行加速量受此问题的顺序部分限制。下面的公式介绍了某个问题的加速，其中 F 是花在顺序区域的时间部分，其余的时间部分则均匀地分布于 P 个处理器。如果方程式的第二项减小到零，则总加速受第一项约束，保持固定。

下图以图表方式说明此概念。黑色阴影部分表示程序的顺序部分，对一个、二个、四个和八个处理器保持不变。稍许阴影部分表示程序的并行部分，可以在任意数量的处理器之间均匀分配。

图 3-3 固定问题加速

随着处理器数目的增加，每个程序并行部分所需的时间会减少，而每个程序串行部分所需的时间保持不变。

然而，实际上可能会发生由于通信以及向多个处理器分配工作而产生的开销。对于使用的任意多个处理器，这些开销可能不固定。

下图说明一个包含 0%、2%、5% 和 10% 顺序部分的程序的理想加速。假定无开销。

图 3-4 Amdahl 定律加速曲线

显示一个包含 0%、2%、5% 和 10% 顺序部分的程序的理想加速（假定无开销）的图。x 轴表示处理器的数目，y 轴表示加速。

3.4.1.1 开销

一旦将开销加入此模型中，加速曲线会发生很大的变化。为了方便说明，假定开销包括以下两部分：独立于处理器数的固定部分，以及随使用的处理器数呈二次增长的非固定部分：

1 除以 S 等于 1 除以下列数值之和：F 加上左括号 1 减去 F 除以 P 右括号加上 K（下标 1）加上 K（下标 2）乘以 P 的平方。

在此方程式中，K₁ 和 K₂ 是固定因子。在这些假定下，加速曲线如下图所示。请注意，在此情况下，加速达到峰值。在某个点之后，增加更多处理器会降低性能。

图 3-5 带开销的加速曲线

此图显示：使用 5 个处理器时所有程序到达最高加速，然后添加到多达 8 个处理器时即会失去此加速优势。x 轴表示处理器的数目，y 轴表示加速。

3.4.1.2 Gustafson 定律

Amdahl 定律可能会在预测真实问题的并行加速时造成误导。花费在程序的顺序部分的时间有时取决于问题大小。也就是说，通过按比例缩放问题大小，您可以获得更多加速机会，如下图所示。

示例 3-12 按比例缩放问题大小可能会获得更多加速机会

/*
* initialize the arrays
*/
for (i=0; i < n; i++) {
    for (j=0; j < n; j++) {
            a[i][j] = 0.0;
            b[i][j] = ...
            c[i][j] = ...
    }
}
/*
* matrix multiply
*/
for (i=0; i < n; i++) {
    for(j=0; j < n; j++) {
            for (k=0; k < n; k++) {
                a[i][j] = b[i][k]*c[k][j];
            }
    }
}

假定理想的开销为零，并且只有第二个循环嵌套并行执行。对于较小的问题大小（即 n 的值较小），程序的顺序部分和并行部分所用的时间彼此相差并不大。然而，随着 n 值的增大，花费在程序并行部分的时间比花费在顺序部分的时间增长得更快。对于此问题，随问题大小的增大而增加处理器数很有益。