I.6 用科学应用测量并行处理器性能

如何测量并行处理器的性能，一直是并行处理领域最有争议的问题之一。当然，最直接的回答是：按原样运行给定基准，并考察实际经过时间，也就是墙钟时间。

测量墙钟时间显然合理；对并行处理器，CPU 时间可能误导读者，因为处理器可能闲置，却不能供其他用途使用。

用户和设计者往往不仅关心固定处理器数量下的性能，还关心增加处理器后性能如何扩展。许多情况下，扩大应用或基准规模是合理的。如果预期用更多处理器求解更大问题，却让基准规模保持不变，那么有限并行度和通信增加的影响会使结果显得悲观。因此，常有必要同时测量固定规模问题和扩大规模问题随处理器增加获得的加速比，分别给出未扩展和扩展后的加速比曲线。如何测量单处理器算法也很重要，以免得到异常结果：在单处理器上仍用基准的并行版本，可能低估单处理器性能，从而夸大加速比。

一旦决定测量扩展加速比，接下来的问题就是如何扩展应用。假设已经确定，在 $p$ 个处理器上运行规模为 $n$ 的基准是合理的；那么，要改在 $m\times p$ 个处理器上运行，应怎样调整规模？有两种显然的方法：保持每个处理器使用的内存量不变；或者在假定理想加速的前提下，保持总执行时间不变。

第一种称为内存约束扩展（memory-constrained scaling），规定在 $mp$ 个处理器上运行规模为 $mn$ 的问题。第二种称为时间约束扩展（time-constrained scaling）；由于要保持运行时间不变，必须知道运行时间与问题规模之间的关系。例如，若数据规模为 $n$ 的应用在 $p$ 个处理器上的运行时间与 $n^2/p$ 成正比，那么按时间约束扩展，应选择在 $mp$ 个处理器上理想运行时间仍为 $n^2/p$ 的问题。这个问题的规模为 $\sqrt m\,n$。

例题 某问题规模为 $n$ 时，执行时间与 $n^3$ 成正比。在 10 个处理器上，实际运行时间为 1 小时。按时间约束和内存约束两种扩展模型，求在 100 个处理器上应运行的问题规模及有效运行时间。

解答 按时间约束扩展，理想运行时间仍为 1 小时，因此问题规模为 $\sqrt[3]{10}\,n$，即原来的约 2.15 倍。按内存约束扩展，问题规模为 $10n$，理想执行时间为原来的 $10^3/10$ 倍，也就是 100 小时！多数用户不会愿意使用十倍的处理器，却运行一百倍长的时间，因此这一问题规模可能不现实。

除了扩展方法，还要考虑另一类问题：如果扩大问题规模会影响结果质量，程序应怎样扩展？通常，必须调整应用中的其他参数。一个简单例子是，求解微分方程所需的收敛时间。问题越大，收敛时间往往越长，例如较大问题通常需要更多迭代。因此，扩大问题规模后，总运行时间可能比基本算法复杂度所指示的增长更快。

例如，假设迭代次数按问题规模的对数增长。若基本算法运行时间与问题规模呈线性关系，实际运行时间便与 $n\log n$ 成正比。从在 10 个处理器上运行规模为 $m$ 的问题出发，只考虑基本算法的扩展，会允许在 100 个处理器上运行规模为 $10m$ 的问题。原文接着认为，计入迭代次数增长后，应运行规模为 $km$、满足 $k\log k=10$ 的问题，才能维持运行时间不变；据此得出规模为 $5.72m$，而不是 $10m$。

译注： 原书的 $k\log k=10$ 以及 5.72 按原述保留；5.72 对应近似采用自然对数。但若严格沿用前句 $T(n)\propto n\log n$，从规模 $m$ 扩至 $km$，等时条件应为 $k\log(km)/\log m=10$，仍然依赖初始规模 $m$。原书没有说明可消去这一依赖的额外归一化假设，不能将 5.72 作为任意初始规模都成立的扩展倍数。

实际中，为控制误差而扩展问题，需要深入了解应用，还可能涉及误差容限等其他因素；例如，误差容限影响 Barnes–Hut 中打开空间单元的判据。反过来，这些效应往往显著改变应用的通信特征、并行度，以及应选择的问题规模。

扩展加速比与未扩展加速比，即真正的同规模加速比，并不相同；混淆两者曾导致错误的性能主张。原文在这里仍引用 I.6 节的讨论。扩展加速比有重要作用，但前提是扩展方法合理，并且明确报告使用了扩大规模后的应用。Singh、Hennessy 和 Gupta［1993］对这些问题有详细论述。