固定问题大小加速通常由 Amdahl 定律控制,它简单地表明给定问题的并行加速量受问题的顺序部分限制。以下方程式描述了一个问题的加速 S,其中 F 是花费在顺序代码上的时间部分,而剩余时间部分 (1 - F) 则均匀分布在 P 处理器中。如果方程式的第二项 ((1 - F) / P) 下降为零,则总加速由第一项 F 限制,该值会保持固定。
下图以图表方式说明此概念。黑色阴影部分表示程序的顺序部分,对一个、二个、四个和八个处理器保持不变。稍许阴影部分表示程序的并行部分,可以在任意数量的处理器之间均匀分配。
图 3-1 固定问题加速
随着处理器数目的增加,每个程序并行部分所需的时间会减少,而每个程序串行部分所需的时间保持不变。
然而,实际上可能会发生由于通信以及向多个处理器分配工作而产生的开销。对于使用的任意多个处理器,这些开销可能不固定。
下图说明一个包含 0%、2%、5% 和 10% 顺序部分的程序的理想加速。假定无开销。
图 3-2 Amdahl 定律加速曲线
一旦将开销加入此模型中,加速曲线会发生很大的变化。为了方便说明,假定开销包括以下两部分:独立于处理器数的固定部分,以及随使用的处理器数呈二次增长的非固定部分:
在此方程式中,K1 和 K2 是固定因子。在这些假定下,加速曲线如下图所示。请注意,在此情况下,加速达到峰值。在某个点之后,增加更多处理器会降低性能。
图 3-3 带开销的加速曲线
此图显示:使用 5 个处理器时所有程序到达最高加速,然后添加到多达 8 个处理器时即会失去此加速优势。x 轴表示处理器的数目,y 轴表示加速。
Amdahl 定律可能会在预测真实问题的并行加速时造成误导。花费在程序的顺序部分的时间有时取决于问题大小。也就是说,通过按比例缩放问题大小,您可以获得更多加速机会,如以下示例所示。
示例 3-21 按比例缩放问题大小可能会获得更多加速机会/* * 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 值的增大,花费在程序并行部分的时间比花费在顺序部分的时间增长得更快。对于此问题,随问题大小的增大而增加处理器数很有益。