# 1.10 计算机设计的定量原则 前面已经讨论了如何定义、测量和汇总性能、成本、可信赖性、能耗与功耗。现在可以进一步探讨那些有助于计算机设计与分析的指导原则。本节将介绍一些重要的设计认识，以及两个用于评估不同方案的公式。 ## 利用并行性 利用并行性是提高性能最重要的手段之一。本书每一章都有通过利用并行性来提升性能的例子。这里先简要介绍三个方面，后续章节再展开讨论。 第一个例子是系统级并行。为提高典型服务器基准测试的吞吐量，例如 SPECStorage 或 TPC-C，可以使用多个处理器和多个存储设备。处理请求的工作负载可以分散到这些处理器与存储设备上，从而提高吞吐量。能够扩充内存、增加处理器和存储设备数量的能力称为**可扩展性**（scalability），是服务器的一项重要优势。把数据分散存放在多个存储设备上，以便并行读写，是在利用数据级并行性（DLP）。SPECstorage 还依靠请求级并行性（RLP）使用多个处理器，而 TPC-C 则利用线程级并行性（TLP）加快数据库查询。 在更细致的数字电路设计层面，也可以利用并行性。例如，存储系统使用多个存储体（bank），允许同时访问不同存储体，以提高内存带宽。算术逻辑单元中的超前进位（carry-lookahead）利用并行性，将求和所需时间对操作数位数的依赖，从线性关系降为对数关系。这些也是 DLP 的例子。 ## 利用流水线 在单个处理器内部，利用指令之间的并行性，是实现高性能的关键。最简单的办法之一就是**流水线**（pipelining）。（附录 C 对流水线作了更详细的介绍，第 3 章也将重点讨论。）流水线的基本思想，是让不同指令的执行过程相互重叠，从而缩短完成一段指令序列所需的总时间。其关键认识在于：并非每条指令都依赖紧邻它之前的那条指令，因此可能让这些指令全部或部分地并行执行。流水线是最广为人知的指令级并行性（ILP）实例。 ## 利用预测 俗话说，有时先做再请求原谅，胜过事先请求许可；下一种机会就是**预测**。如果预测相当准确，而预测失败后的恢复机制又不太昂贵，那么在某些情况下，与其等到完全确定，不如先作猜测并开始工作，平均而言反而更快。预测用于存储层次结构（见第 2 章），在现代流水线处理器中更得到广泛应用（见第 3 章）；但它也可能引发安全问题（见 1.8 节）。 ## 利用局部性原理 对程序特性的观察，带来了一些重要的基本认识。我们经常利用的最重要的程序特性，就是**局部性原理**：程序往往会再次使用最近用过的数据和指令。一个广为流传的经验法则是，程序 90% 的执行时间花在仅仅 10% 的代码上。局部性的一个含义是：根据程序最近的访问行为，可以相当准确地预测它接下来将使用哪些指令和数据。局部性也适用于数据访问，只是不像代码访问那样明显。 人们观察到两种不同的局部性。**时间局部性**是指，最近访问过的项很可能很快再次被访问。**空间局部性**是指，地址彼此接近的项，其访问时间也往往彼此接近。第 2 章将介绍这些原理的应用。 ## 通过冗余实现可信赖性 计算机不仅要快，还必须值得信赖。任何物理器件都有可能失效，因此我们通过加入冗余部件来提高系统的可信赖性：发生失效时，冗余部件可以接管工作，也可以帮助检测失效，前面介绍的冗余电源就是一个例子。内存和存储设备长期以来一直依赖冗余来保证可信赖性，而静默数据损坏问题（1.7 节）表明，这些技术对计算机的其他部件也将变得重要。 ## 优先优化常见情况 计算机设计中最重要、应用最广泛的原则，也许就是**优先优化常见情况**：在作设计取舍时，优先照顾经常出现的情况，而不是罕见情况。这个原则适用于资源分配，因为一种情况出现得越频繁，改进它带来的影响就越大。 这一原则不仅适用于资源分配和性能，也适用于能耗。处理器的取指与译码单元，使用频率可能远高于乘法器，因此应当优先优化前者。可信赖性同样如此。如果数据库服务器每个处理器对应 50 个存储设备，那么系统的可信赖性很可能主要由存储设备决定。 此外，常见情况往往也比罕见情况更简单，处理起来更快。例如，处理器执行两个数的加法时，可以预期溢出很少发生，因此优化更常见的无溢出情况就能提高性能。这样做可能让溢出发生时的处理变慢，但只要溢出确实罕见，优化正常情况仍能提高整体性能。 本书将反复展示这一原则。在应用这个简单原则时，需要确定什么情况最常见，以及加快这种情况究竟能带来多大性能提升。 一个称为 **Amdahl 定律**的基本规律，可以将这一原则量化。 ## Amdahl 定律 改进计算机某一部分后能够获得多大的性能收益，可以用 Amdahl 定律计算。该定律指出：采用更快执行方式所能获得的性能提升，受限于这种更快方式可以发挥作用的时间比例。 Amdahl 定律定义了采用某项功能后可以获得的**加速比**（speedup）。加速比是什么？假设我们对计算机作出一项改进，使用该改进时性能就会提高。加速比定义为： $$ \text{加速比} =\frac{\text{尽可能使用改进时完成整个任务的性能}} {\text{不使用改进时完成整个任务的性能}} $$ 也可以写成： $$ \text{加速比} =\frac{\text{不使用改进时完成整个任务的执行时间}} {\text{尽可能使用改进时完成整个任务的执行时间}} $$ 加速比告诉我们：与原计算机相比，任务在采用改进后的计算机上能运行得多快。 Amdahl 定律提供了一种快速计算改进收益的方法。所得加速比取决于两个因素： 1. **原计算机的计算时间中，能够利用改进的部分所占的比例。** 例如，一个程序总共执行 100 秒，其中有 40 秒可以利用改进，那么这个比例就是 \(40/100\)。我们将它称为 \(\mathrm{Fraction}_{\mathrm{enhanced}}\)，其值总是小于或等于 1。 2. **改进后的执行方式本身带来的加速比。** 也就是假设整个程序都能使用这种方式，它会运行得多快。这个值等于原方式所需时间除以改进方式所需时间。例如，程序的某个部分原来耗时 40 秒，改进后耗时 4 秒，那么加速比就是 \(40/4=10\)。我们将它称为 \(\mathrm{Speedup}_{\mathrm{enhanced}}\)，其值总是大于 1。 在原计算机中采用改进后的执行方式，总执行时间等于未改进部分的时间，加上使用改进部分的时间： $$ \text{执行时间}_{\mathrm{new}} =\text{执行时间}_{\mathrm{old}} \times\left[ (1-\mathrm{Fraction}_{\mathrm{enhanced}}) +\frac{\mathrm{Fraction}_{\mathrm{enhanced}}}{\mathrm{Speedup}_{\mathrm{enhanced}}} \right] $$ 整体加速比就是改进前后执行时间之比： $$ \mathrm{Speedup}_{\mathrm{overall}} =\frac{\text{执行时间}_{\mathrm{old}}}{\text{执行时间}_{\mathrm{new}}} =\frac{1}{ (1-\mathrm{Fraction}_{\mathrm{enhanced}}) +\mathrm{Fraction}_{\mathrm{enhanced}}/\mathrm{Speedup}_{\mathrm{enhanced}} } $$ ### 例：加快 Web 服务器的处理器 假设要改进一台提供 Web 服务的处理器。新处理器执行该 Web 服务应用中的计算部分时，速度是旧处理器的 10 倍。原处理器有 40% 的时间在计算，60% 的时间在等待 I/O。采用这项改进后，整体加速比是多少？ **解：** $$ \mathrm{Fraction}_{\mathrm{enhanced}}=0.4,\qquad \mathrm{Speedup}_{\mathrm{enhanced}}=10 $$ $$ \mathrm{Speedup}_{\mathrm{overall}} =\frac{1}{0.6+0.4/10} =\frac{1}{0.64}\approx1.56 $$ Amdahl 定律体现了收益递减规律：只改进计算过程的一部分时，随着该部分不断被加速，整体加速比所获得的增量会越来越小。它的一个重要推论是：如果改进只能用于任务的一部分，那么任务的加速比不可能超过“1 减去该部分所占比例”的倒数。 使用 Amdahl 定律时，一个常见错误是混淆“原时间中能够利用改进的比例”与“改进后这部分占总时间的比例”。如果测量的不是计算过程中原本可以利用改进的时间，而是改进已经生效后的时间，结果就会出错！ Amdahl 定律可以指导我们判断某项改进会带来多大性能提升，以及如何分配资源来提高性价比。显然，应当按照时间消耗的比例投入资源。它特别适合比较两种方案的整体系统性能，也可以比较两种处理器设计方案，下面就是一个例子。 ### 例：只加快平方根，还是加快全部浮点运算 图形处理器经常需要进行开平方运算。浮点平方根（FSQRT）的不同实现，性能差异很大，在面向图形的处理器之间尤其如此。假设一个关键图形基准测试有 20% 的执行时间用于 FSQRT。一种方案是改进 FSQRT 硬件，使这项操作的速度达到原来的 10 倍。 另一种方案是把图形处理器中所有浮点（FP）指令的速度提高到原来的 1.6 倍。假设浮点指令占应用执行时间的一半。设计团队认为，使全部浮点指令加速到 1.6 倍，与实现快速平方根所需的投入相同。请比较这两种方案。 **解：** 可以比较两种方案的加速比： $$ \mathrm{Speedup}_{\mathrm{FSQRT}} =\frac{1}{(1-0.2)+0.2/10} =\frac{1}{0.82}=1.22 $$ $$ \mathrm{Speedup}_{\mathrm{FP}} =\frac{1}{(1-0.5)+0.5/1.6} =\frac{1}{0.8125}=1.23 $$ 由于全部浮点运算出现得更频繁，整体加快浮点运算的方案略胜一筹。 Amdahl 定律的用途不限于性能。现在重新考虑 1.7 节的可靠性例题：通过冗余，把电源的平均失效前时间（MTTF）从 200,000 小时提高到 830,000,000 小时，即提高到原来的 4,150 倍。 ### 例：冗余电源对系统可靠性的影响 磁盘子系统失效率的计算如下： $$ \begin{aligned} \text{失效率}_{\mathrm{system}} &=10\times\frac{1}{1{,}000{,}000} +\frac{1}{500{,}000} +\frac{1}{200{,}000} +\frac{1}{200{,}000} +\frac{1}{1{,}000{,}000}\\ &=\frac{10+2+5+5+1}{1{,}000{,}000\ \text{小时}} =\frac{23}{1{,}000{,}000\ \text{小时}} \end{aligned} $$ 因此，可以改进的部分占失效率的比例，是系统总失效率每百万小时 23 次中的 5 次，即 0.22。 **解：** 可靠性的改善倍数为： $$ \mathrm{Improvement}_{\text{双电源}} =\frac{1}{(1-0.22)+0.22/4150} =\frac{1}{0.78}=1.28 $$ 尽管一个模块的可靠性提高到了惊人的 4,150 倍，从整个系统看，收益虽然可以测出，却并不大。 在前面的例子中，我们需要知道新的、改进后的版本所占用的比例。[^fraction-wording] 直接测量这些时间往往比较困难。下面将介绍另一种比较方法，它所用的公式把 CPU 执行时间分解为三个独立因素。 只要知道某个方案如何影响这三个因素，就能确定它的整体性能。此外，在硬件真正完成设计之前，通常就可以构建模拟器来测量这些因素。 ## 处理器性能公式 基本上，所有计算机都使用以固定速率运行的时钟。这些离散的时间事件称为时钟周期，英文中会使用 clock period、clock、cycle 或 clock cycle 等说法。设计者既可以用持续时间表示一个时钟周期，例如 1 ns，也可以用频率表示，例如 1 GHz。于是，程序的 CPU 时间可以写为： $$ \text{CPU 时间} =\text{程序所需的 CPU 时钟周期数}\times\text{时钟周期时间} $$ 或者： $$ \text{CPU 时间} =\frac{\text{程序所需的 CPU 时钟周期数}}{\text{时钟频率}} $$ 除了执行程序所需的时钟周期数，还可以统计执行的指令数量，称为指令路径长度（instruction path length）或**指令数**（instruction count，IC）。知道总时钟周期数与 IC，就可以计算平均每条指令的时钟周期数（CPI）。本章采用 CPI，一是因为它便于使用，二是因为本章讨论的是简单处理器。设计者有时也使用**每时钟周期指令数**（instructions per clock，IPC），它是 CPI 的倒数。 CPI 的计算方式是： $$ \mathrm{CPI} =\frac{\text{程序所需的 CPU 时钟周期数}}{\text{指令数}} $$ 这一处理器评价指标，有助于理解不同风格的指令集与实现方式，后面四章将大量使用它。 将上式中的指令数移项，可以得到总时钟周期数为 \(\mathrm{IC}\times\mathrm{CPI}\)。因此，执行时间公式可以写成： $$ \text{CPU 时间} =\text{指令数}\times\text{每条指令的时钟周期数}\times\text{时钟周期时间} $$ 把这一公式展开为计量单位，就能看清各部分如何对应： $$ \frac{\text{指令}}{\text{程序}} \times\frac{\text{时钟周期}}{\text{指令}} \times\frac{\text{秒}}{\text{时钟周期}} =\frac{\text{秒}}{\text{程序}} =\text{CPU 时间} $$ 这个公式表明，处理器性能取决于三个因素：时钟周期时间（或时钟频率）、CPI 和 IC。 而且，CPU 时间对这三个因素的依赖程度相同；例如，其中任一项改善 10%，CPU 时间也会相应改善 10%。[^percentage] 遗憾的是，很难只改变其中一个参数而完全不影响其他参数，因为改变各项指标所依赖的基础技术彼此相关： - **时钟周期时间**：硬件技术与组成。 - **CPI**：组成与指令集体系结构（ISA）。 - **指令数**：ISA 与编译器技术。 幸运的是，许多潜在的性能优化技术主要改善其中一个因素，而对另外两个因素的影响较小，或者可以预测。 设计处理器时，有时把总 CPU 时钟周期数写成下式会很有帮助： $$ \text{CPU 时钟周期数}=\sum_{i=1}^{n}\mathrm{IC}_i\times\mathrm{CPI}_i $$ 其中，\(\mathrm{IC}_i\) 表示指令 \(i\) 在程序中执行的次数，\(\mathrm{CPI}_i\) 表示该指令每次执行平均需要的时钟周期数。因此，CPU 时间可写为： $$ \text{CPU 时间} =\left(\sum_{i=1}^{n}\mathrm{IC}_i\times\mathrm{CPI}_i\right) \times\text{时钟周期时间} $$ 总体 CPI 则是： $$ \mathrm{CPI} =\frac{\sum_{i=1}^{n}\mathrm{IC}_i\times\mathrm{CPI}_i}{\text{指令数}} =\sum_{i=1}^{n} \frac{\mathrm{IC}_i}{\text{指令数}}\times\mathrm{CPI}_i $$ 后一种计算方法使用每类指令各自的 \(\mathrm{CPI}_i\)，以及该指令在程序中出现的比例，即 \(\mathrm{IC}_i/\text{指令数}\)。\(\mathrm{CPI}_i\) 必须包含流水线影响、缓存未命中以及存储系统的其他低效因素，因此应通过测量获得，而不能只根据参考手册末尾的一张表来计算。 再看前面的性能例题，这次改用各类指令出现频率及其 CPI 的测量值。在实践中，这些数据通过模拟或硬件测量机制获得。 ### 例：用处理器性能公式比较浮点优化 假设得到以下测量值： | 测量项 | 数值 | | --- | ---: | | 浮点运算出现频率 | 25% | | 浮点运算平均 CPI | 4.0 | | 其他指令平均 CPI | 1.33 | | FSQRT 出现频率 | 2% | | FSQRT 的 CPI | 20 | 有两种设计方案：把 FSQRT 的 CPI 降到 2，或者把所有浮点运算的平均 CPI 降到 2.5。请使用处理器性能公式比较两者。 **解：** 首先注意，只有 CPI 发生变化，时钟频率与指令数保持不变。先计算未采用任何改进时的原始 CPI： $$ \begin{aligned} \mathrm{CPI}_{\mathrm{original}} &=\sum_{i=1}^{n}\mathrm{CPI}_i\times \left(\frac{\mathrm{IC}_i}{\text{指令数}}\right)\\ &=(4\times25\%)+(1.33\times75\%)=2.0 \end{aligned} $$ 从原始 CPI 中减去节省的周期数，即可得到改进 FSQRT 后的 CPI： $$ \begin{aligned} \mathrm{CPI}_{\text{采用新 FPSQR}} &=\mathrm{CPI}_{\mathrm{original}} -2\%\times\left( \mathrm{CPI}_{\text{原 FPSQR}} -\mathrm{CPI}_{\text{仅新 FPSQR}} \right)\\ &=2.0-2\%\times(20-2)=1.64 \end{aligned} $$ 全部浮点指令得到改进后的 CPI，可以用同样方法计算，也可以分别计算浮点与非浮点指令的贡献后相加。采用后一种方法： $$ \mathrm{CPI}_{\mathrm{new\ FP}} =(75\%\times1.33)+(25\%\times2.5)=1.625 $$ 由于整体浮点优化方案的 CPI 略低，所以它的性能也略好。具体而言，该方案的加速比为： $$ \begin{aligned} \mathrm{Speedup}_{\mathrm{new\ FP}} &=\frac{\text{CPU 时间}_{\mathrm{original}}}{\text{CPU 时间}_{\mathrm{new\ FP}}}\\ &=\frac{\mathrm{IC}\times\text{时钟周期}\times\mathrm{CPI}_{\mathrm{original}}} {\mathrm{IC}\times\text{时钟周期}\times\mathrm{CPI}_{\mathrm{new\ FP}}}\\ &=\frac{\mathrm{CPI}_{\mathrm{original}}}{\mathrm{CPI}_{\mathrm{new\ FP}}} =\frac{2.00}{1.625}=1.23 \end{aligned} $$ 令人欣慰的是，这与前面使用 Amdahl 定律得到的加速比相同。[^cpi-rounding] 处理器性能公式中的各个因素，往往可以分别测量。 能够进行这种独立测量，是前例中采用处理器性能公式而不是 Amdahl 定律的一项重要优势。尤其是，某一组指令究竟占用了多大比例的执行时间，可能很难直接测量。在实践中，多半还是要对这组指令逐项计算 IC 与 CPI 的乘积，再求和。由于起点通常就是各项 IC 与 CPI 的测量结果，处理器性能公式格外有用。 要把这个公式作为设计工具，就必须能够测量各个因素。对已有处理器，执行时间容易通过测量获得，其默认时钟频率也已知。难点在于如何得到 IC 或 CPI。多数处理器都提供指令执行次数与时钟周期数的计数器。定期观察这些计数器，还可以把执行时间和指令数归到不同代码段上，帮助程序员理解与优化应用性能。设计者或程序员往往希望了解比硬件计数器所能提供的更细致的信息，例如，CPI 为什么是这个数值。这时，就需要使用类似于设计新处理器时所采用的模拟技术。 动态电压频率调节（DVFS）和超频等有助于能效的技术（见 1.5 节），会让这个公式更难使用，因为测量程序运行时，时钟频率可能在变化。一个简单办法是关闭这些功能，以保证结果可复现。幸运的是，性能与能效往往高度相关：程序运行时间越短，通常越节能。因此，在研究性能时，暂不考虑 DVFS 或超频对结果的影响，可能是可行的。 [^fraction-wording]: 译注：这里原文确写“the fraction consumed by the new and improved version”。但 Amdahl 定律中的 \(\mathrm{Fraction}_{\mathrm{enhanced}}\) 必须取改进前的时间比例；前文已明确警告不能使用改进后的占比。此处措辞与其定义不一致。 [^percentage]: 译注：原文以“改善 10%”概括。严格说，当指令数、CPI 或时钟周期时间单独减少 10% 时，CPU 时间也减少 10%；若时钟频率增加 10%，时间则变为原来的 \(1/1.1\)，不能把这两种百分比混同。 [^cpi-rounding]: 译注：原式保留了舍入后的数值与等号。直接代入已显示的 1.33，原始 CPI 为 1.9975，全部浮点优化后的 CPI 为 1.6225；书中的 2.0 和 1.625 对应把非浮点 CPI 视为约 \(4/3\) 的处理。平方根公式下标原写 FPSQR，与正文 FSQRT 不一致。