计算机体系结构 量化研究方法 笔记1

量化设计与分析基础

处理器性能的提高从单纯依赖指令集并行（ILP）转向数据级并行（DLP）和线程级并行（TLP）。

并行度与并行体系结构的分类

在所有4个计算机类别中，多种级别的并行度现在已经成为计算机设计的推动力量，而能耗和成本则是主要约束条件。应用程序中主要有以下两种并行。

1. 数据级并行（DLP），它的出现是因为可以同时操作许多数据项。
2. 任务级并行（TLP），它的出现是因为创建了一些能够单独处理但大量采用并行方式执行的工作任务。

计算机硬件又以如下4种主要方式来开发这两种类型的应用并行。

• 指令级并行在编译器的帮助下，利用流水线之类的思想适度开发数据级并行，利用推理执行之类的思想以中等水平开发数据级并行。
• 向量体系结构和图形处理器（GPU）将单条指令并行应用于一个数据集，以开发数据级并行。
• 线程级井行在一种紧耦合硬件模型中开发数据级并行或任务级并行，这种模型允许在并行线程之间进行交互。
• 请求级并行在程序员或操作系统指定的大量去耦合任务之间开发并行。

Michael Flynn[1966]在20世纪60年代研究并行计算工作量时，提出了一种简单的分类方式，他研究了多处理器最受约束组件中的指令流及数据流的并行，并据此将所有计算机分为以下4类。

• 单指令流、单数据流（SISD）是单处理器。程序员把它看作标准的顺序计算机，但可以利用指令级并行。第3章介绍了采用ILP技术（比如超标量和推理执行）的SISD体系结构。
• 单指令流、多数据流（SIMD）同一指令由多个使用不同数据流的处理器执行。SIMD计算机开发数据级并行，对多个数据项并行执行相同操作。每个处理器都有自己的数据存储器，但只有一个指令存储器和控制处理器，用来提取和分派指令。
• 多指令流、单数据流（MISD）：目前为止，还没有这种类型的商用多处理器。
• 多指令流、多数据流（MIMD）：每个处理器都提取自己的指令，对自己的数据进行操作。它针对的是任务级并行。

计算机体系结构

指令集体系结构：计算机体系结构的近距离审视

我们在本书中用指令集体系结构（ISA）一词来指代程序员可以看到的实际指令集。ISA的作用相当于区分软件和硬件的界限。在下面对ISA的快速回顾中，将使用80x86、ARM和MIPS的例子从7个方面来介绍ISA。

（1）ISA分类。现今几乎所有的ISA都划分到通用寄存器体系结构中，在这种体系结构中，操作数或者是寄存器，或者是存储器地址。80x86有16个通用寄存器和16个通常存入浮点数据的寄存器，而MIPS则有32个通用寄存器和32个浮点寄存器（见表）。这一类别有两种主流版本，一种是寄存器-存储器ISA，比如80x86，可以在许多指令中访问存储器，另一种是载入-存储ISA，比如ARM和MIPS，它们只能用载入或存储指令来访问存储器。所有最新ISA都采用载入-存储版本。

（2）存储器寻址。几乎所有桌面计算机和服务器计算机（包括80x86、ARM和MIPS）都使用字节寻址来访问存储器操作数。有些体系结构（像ARM和MIPS）要求操作对象必须是对齐的。一个大小为s的对象，其字节地址为A，如果A mod s = 0，则对这个对象的访问是对齐的。如果操作数是对齐的，访向速度通常会快一些。

（3）寻址模式。除了指定寄存器和常量操作数之外，寻址模式还指定了一个存储器对象的地址。MIPS寻址模式为：寄存器、立即数、位移量。立即数寻址用于常数寻址，在位移量寻址模式中，将一个固定偏移量加到寄存器，得出存储器地址。

（4）操作数的类型和大小。和大多数ISA类似，80x86、ARM和MIPS支持的操作数大小为8位（ASCII字符〕、16位（Unicode字符或半个字）、32位（整数或字）、64位（双字或长整型）以及IEEE754浮点数，包括32位（单精度）和位〈双精度）。80x86还支持80位浮点（扩展双精度）。

（5）操作指令。常见的操作类别为：数据传输指令、算术逻辑指令、控制指令（下面进行讨论）和浮点指令。MIPS是一种简单的、易于实现流水化的指令集体系结构，它是2011年采用RISC体系结构的代表。表中总结了MIPS ISA。8cx86的操作指令集要丰富得多。

（6）控制流指令。几乎所有ISA，包括上述三种在内，都支持条件转移、无条件跳转、过程调用和返回。所有这三种都使用相对于PC的寻址方式，其中的分支地址由一个地址字段指定，该地址将被加到PC。这三种ISA之间有一些微小的区别。MIPS条件分支（BE、BNE等）检验寄存器中的内容，而80x86和ARM分支测试条件代码位，这些位是在执行算术/逻辑运算时顺带置位的。ARM和MIPS过程调用将返回地址放在一个寄存器中，而886调用（CALLF）将返回地址放在存储器中的一个栈内。

（7）ISA的编码。有两种基本的编码选择：固定长度和可变长度。所有ARM和MIPS指令的长度都是32位，从而简化了指令译码。图中给出了MIPS指令格式。80x86编码为可变长度，变化范围为1～18个字节。与固定长度的指令相比，可变长度的指令可以占用较少的空间，所以为80x86编译的程序通常要小于为MIPS编译的相同程序。

真正的计算机体系结构：设计满足目标和功能需求的组成和硬件

计算机的实现包括两个方面：组成和硬件。组成一词包含了计算机设计的高阶内容，比如存储器系统，存储器互连，设计内部处理器或CPU（中央处理器一一一算术、逻辑、分支和数据输送功能都在这里实现）。

由于单个微处理器上开始采用多个处理器，所以人们开始使用核心一词来称呼处理器：人们一般不说“多处理器微处理器”，而是使用“多核”。由于现今几乎所有芯片都有多个处理器，所以人们不怎么使用中央处理器（或CPU）一词了。

硬件是指一个计算机的具体实现，包括计算机的详尽逻辑设计和封装技术。同一系列的计算机通常具有相同的指令集体系结构和几乎相同的组成，但在具体硬件实现方面有所不同。

计算机设计的量化原理

充分利用并行

充分利用并行是提高性能的最重要方法之一。这里给出三个简单的例子，在后续各章会给出详细解释。

第一个例子是在系统级别开发并行。为了提高在一个典型服务器基准测试（比如SPECWeb或TPC-C）上的吞吐量性能，可以使用多个处理器和多个磁盘。随后可以在处理器和磁盘之间分散处理请求的工作负载，从而提高吞吐量。扩展内存以及处理器和磁盘数目的能力称为可扩展性。在许多磁盘之间分布数据，以实现并行读写，就可以支持数据级并行。SPECWeb还依靠请求级并行来使用大量处理器，而TPC-C使用线程级并行实现对数据库请求的更快速处理。

在单独的处理器级别，充分利用指令间的并行对于实现高性能非常关键。实现这种并行的最简单方法之一就是通过流水线。流水线背后的基本思想是将指令执行重叠起来，以缩短完成指令序列的总时间。流水线能够实现的关键是认识到并非所有执行都取决于与其直接相邻的前一条指令，所以有可能完全并行或部分并行地执行这些指令。

在具体的数字设计级别也可以开发并行。例如，组相联（Set Associative）缓存使用多组存储器，通常可以对它们进行并行查询，以查找所需项目。现代ALU（算术逻辑单元）使用先行进位，这种方法使用并行来加快求和过程，使计算时间与操作数位数之间的关系由线性关系变为对数关系。数据级并行的例子还有许多。

局域性原理

一个最重要程序特性是局域性原理：程序常常重复使用它们最近用过的数据和指令。一条广泛适用的经验规律是：一个程序90%的执行时间花费在仅10%的代码中。局域性意味着我们可以根据一个程序最近访问的指令和数据，比较准确地预测它近期会使用哪些内容。时间局域性是指最近访问过的内容很可能会在短期内被再次访问。空间局域性是指地址相互临近的项目很可能会在短时间内都被用到。

Amdahl定律

利用Amdahl定律，可以计算出通过改进计算机某一部分而能获得的性能增益。Amdahl定律表明，使用某种快速执行模式获得的性能改进受限于可使用此种快速执行方式的时间比例。

Amdabl定律定义了使用某一特定功能所获得的加速比（speedup〕。加速比的定义为：加速比=整个任务在采用该升级时的性能/整个任务在未采用该升级时的性能。或者：加速比=整个任务在未采用该升级时的执行时间/整个任务在采用该升级时的执行时间。加速比告诉我们，与原计算机相比，在经过升级的计算机上运行一个任务可以加快多少。

Amdahl定律为我们提供了一种快速方法，用来计算某一升级所得到的加速比，加速比取决于下面两个因素。

• 原计算机计算时间中可升级部分所占的比例。例如，一个程序的总执行时间为秒，如果有20秒的执行时间可进行升级，那这个比例就是20/60。我们将这个值称为升级比例，它总是小于或等于1。
• 通过升级执行模式得到的改进，也就是说在为整个程序使用这一执行模式时，任务的运行速度会提高多少倍。这个值等于原模式的执行时间除以升级模式的执行时间。如果为程序的某一部分采用升级模式后需要2秒，而在原始模式中需要5秒，则提升值为5/2。我们将这个值称为升级加速比，它总是大于1。

原计算机采用升级模式后的执行时间等于该讨机未升级部分耗用的时间加上使用升级部分耗用的时间：

新执行时间 = 原执行时间 × （（1-升级比例） + 升级比例/升级加速比）

总加速比是这两个执行时间之比：

总加速比=原执行时间/新执行时间=1/（（1-升级比例）+升级比例/升级加速比）

Amdahl定律阐述了回报递减定律：如果仅改进一部分计算的性能，在增加改进时，所获得的加速比增量会逐渐减小。

存储器层次结构设计

引言

由于快速存储器非常昂贵，所以将存储器层次结构分为几个级别——越接近处理器，容量越小、速度越快、每字节的成本也越高。其目标是提供一种存储器系统，每字节的成本几乎与最便宜的存储器级别相同，速度几乎与最快速的级别相同。在大多数（但并非全部）情况下，低层级存储器中的数据是其上一级存储器中数据的超集。这一性质称为包含性质，层次结构的最低级别必须具备这一性质，如果这一最低级别是缓存，则由主存储器组成，如果是虚拟存储器，则由磁盘存储器组成。

随着处理器性能的提高，存储器层次结构的重要性也在不断增加。图2-2是单处理器性能和主存储器访问次数的历史发展过程。处理器曲线显示了平均每秒发出存储器请求数的增加（即两次存储器引用之间延迟值的倒数），而存储器曲线显示每秒DRAM访问数的增加（即DRAM访问延迟的倒数）。在单处理器中，由于峰值存储器访问速度要快于平均速度（也就是图中绘制的速度），所以其实际情况要稍差一些。

近来，高端处理器已经转向多核，与单核相比，进一步提高了带宽需求。事实上，总峰值带宽基本上随核心个数的增大而增大。现代高端处理器每个时钟周期可以由每个核心生成两次数据存储器引用，i7有4个核心，时钟频率为3.2G，除了大约128亿次128位指令引用的峰值指令要求之外，每秒最多还可生成256亿次位数据存储器引用；总峰值带宽为409.6GB/s！

这一难以置信的高带宽是通过以下方法实现的：实现缓存的多端口和流水线；利用多级缓存，为每个核心使用独立的第一级缓存，有时也使用独立的第二级缓存；在第一级使用独立的指令与数据缓存。与其形成鲜明对比的是，DRAM主存储器的峰值带宽只有它的6%（25GB/s）。

如果在缓存中找不到某一个字，就必须从层次结构的一个较低层级（可能是另一个缓存，也可能是主存储器）中去提取这个字，并把它放在缓存中，然后才能继续。出于效率原因，会一次移动多个字，称为块（或行），这样做还有另外一个原因：由于空间局域性原理，很可能马上就会用到这些字。每个缓存块都包括一个标记，指明它与哪个存储器地址相对应。

在设计时需要作出一个非常重要的决策：哪些块（或行）可以放在缓存中。最常见的方案是组相联，其中组是指缓存中的一组块。一个块首先被映射到一个组上，然后可以将这个块放到这个组中的任意位置。要查找一个块，首先将这个块的地址映射到这个组，然后再搜索这个组（通常为并行搜索），以找到这个块。这个组是根据数据地址选择的：（块地址）MOD（缓存中的组数）。

如果组中有n个块，则缓存的布局被称为n路组相联。组相联的端点有其自己的名字。直接映射缓存每组中只有一个块（所以块总是放在同一个位置），全相联缓存只有一个组（所以块可以放在任何地方）。

要缓存只读数据是一件很容易的事情，这是因为缓存和存储器中的副本是相同的。缓存写入难一些；比如，缓存和存储器中的副本怎样才能保持一致呢？共有两种主要策略。一种是直写（write-through）缓存，它会更新缓存中的项目，并直接写入主存储器，对其进行更新。另一种是回写（write-back）缓存，仅更新缓存中的副本。在马上要替换这个块时，再将它复制回存储器。这两种写入策略都使用了一种写缓冲区，将数据放入这个缓冲区之后，马上就可以进行缓存操作，不需要等待将数据写入存储器的全部延迟时间。

为了衡量不同缓存组织方式的优劣，可以采用一个名为缺失率的指标。缺失率是指那些未能找到预期目标的缓存访问所占的比例，即未找到目标的访问数目除以总访问数目。为了深刻理解高缺失率的原因，从而更好地设计缓存，一种”3C”模式将所有这些缺失情景分为以下三个简单的类别。

• 强制（compulsory）：对一个数据块的第一次访问，这个块不可能在缓存中，所以必须将这个块调入缓存中。即使拥有无限大的缓存，也会发生强制缺失。
• 容量（Capacity）：如果缓存不能包含程序运行期间所需要的全部块，就会因为有些块被放弃，之后再被调入，从而导致容量缺失（还有强制缺失）。
• 冲突（conflict）：如果块放置策略不是全相联的，如果多个块映射到一个块的组中，对不同块的访问混杂在一起，一个块可能会被放弃，之后再被调入，从而发生冲突缺失（还有强制缺失和容量缺失）。

多线程和多核都增加了缓存的复杂性，都加大了出现容量缺失的可能性，而且还因为缓存刷新增加了第4个C——一致性（coherency）缺失，之所以进行缓存刷新是为保持多处理器中多个缓存的一致性。

要小心，缺失率可能会因为多个原因而产生误导。因此，一些设计人员喜欢测量每条指令的缺失次数，而不是每次存储器引用的缺失次数（缺失率）。这两者之间的关系如下：

缺失数/指令 = 缺失率×存储器访问/指令数 = 缺失率x存储器访问/指令

这两种度量指标的问题在于它们都没有考虑缺失成本的因素。一种更好的度量指标是存储器平均访问时间：

存储器平均访问时间 = 命中时间 + 缺失率 × 缺失代价

其中，命中时间是指在缓存中命中目标花费的时间，缺失代价是从内存中替代块的时间（即缺失成本）。多线程的使用也允许一个处理器容忍一些缺失，而不会被强制转入空闲状态。

下文给出了6种基本的缓存优化方法

1. 增大块以降低缺失率。这是降低缺失率的最简单方法，它利用了空间局域性，并增大了块的大小。使用较大的块可以减少强缺失，但也增加了缺失代价。因为较大块减少了标记数目，所以它们可以略微降低静态功率。较大块还可能增大容量缺失或冲突缺失，特别是当缓存较小时尤为如此。选择合适的块大小是一项很复杂的权衡过程，具体取决于缓存的大小和缺失代价。
2. 增大缓存以降低缺失率。要减少容量缺失，一个显而易见的方法就是增大缓存容量。其缺点包括可能会延长较大缓存存储器的命中时间，增加成本和功率。较大的缓存会同时增大静态功率和动态功率。
3. 提高相联程度以降低缺失率。显然，提高相联程度可以减少冲突缺失。较大的相联程度是以延长命中时间为代价的。

4. 采用多级缓存以降低缺失代价。是加快缓存命中速度，以跟上处理器的高速时钟频率，还是加大缓存，以缩小处理器访问和主存储器访问之间的差距，这是一个艰难的决策。在原缓存和存储器之间加入另一级缓存可以降低这一决策的难度。第一级缓存可以非常小，足以跟上快速时钟频率，而第二级（或第三级）缓存可以非大，足收集容纳许多本来要对主存储器进行的访问。为了减少第二级缓存中的缺失，需要采用更大的块、更大的容量和更高的相联程度。与一级总缓存相比，多级缓存的功率效率更高。如果用LI和L2分别指代第一级和第二季缓存，可以将平均存储器访问时间定义为：

   L1命中时间 + L1缺失率 × (L2命中时间 + L2缺失率 × L2缺失代价)

5. 为读取缺失指定高于写入操作的优先级，以降低缺失率。写缓冲区是实现这一优化的好地方。因为写缓冲区拥有在读取缺失时所需位置的更新值，所以写缓冲区存在隐患，即通过存储器进行先写后读的隐患。一种解决方案就是在读取缺失时检查写缓冲区的内容。如果没有冲突，如果存储器系统可用，则在写入操作之前发送读取请求会降低缺失代价。大多数处理器为读取指定的优先级要高于写入操作。这种选择对功耗几乎没有什么影响。

** 识别结果 1**

访问时间通常会随着缓存大小和相联程度的增大而增加。这些数据假定采用40nm制程、单一存储器组、块大小为64字节。由于对缓存布局所做的假定，以及在互连延迟（通常取决于正在访问的缓存块的大小）和标记检查与多工之间的复杂权衡，会得到一些有时看起来令人惊奇的结果，比如对于两路组相联的64KB缓存，其访问时间会低于直接映射。与此类似，当缓存大小增大时，八路组相联产生的结果也会导致一些不同寻常的行为。

1. 在缓存索引期间避免地址转换，以缩短命中时间。缓存必须妥善应对从处理器虚拟地址到访问存储器的物理地址之间的转换。一种常见的优化方法是使用页偏移地址（虚拟地址和物理地址中的相同部分）来索引缓存。这种虚拟索引/物理标记方法增加了某些系统复杂度以及（或者）对L1缓存大小与结构的限制，但从关键路径消除转换旁视缓冲区（TLB）访问这一优点抵得过这些缺点。

缓存性能的10种高级优化方法

上面的存储器平均访问时间公式提供了三种缓存优化度量：命中时间、缺失率和缺失代价。根据最近的发展趋势，我们向这个列表中添加了缓存带宽和功耗两个度量。根据这些度量，可以将我们研究的10种高级缓存优化方法分为以下5类。

1. 缩短命中时间。小而简单的第一级缓存和路预测。这两种技术通常还都能降低功耗。
2. 增加缓存带宽。流水化缓存、多组缓存和无阻塞缓存。这些技术对功耗具有不确定影响。
3. 降低缺失代价。关键字优化，合并写缓冲区。这两种优化方法对功率的影响很小。
4. 降低缺失率。编译器优化。显然，缩短编译时间肯定可以降低功耗。
5. 通过并行降低缺失代价或缺失率。硬件预取和编译器预取。这些优化方法通常会增加功耗，主要是因为提前取出了未用到的数据。

一般来说，在采用这些技术方法时，硬件复杂度会增加。另外，这些优化技术中有几种需要采用高级编译器技术。对其中比较简单的优化方法仅作简单介绍，而对其他技术将给出更多描述。

第一种优化：小而简单的第一级缓存，用以缩短命中时间、降低功率

提高时钟频率和降低功率的双重压力都推动了对第一级缓存大小的限制。与此类似，使用较低级别的相联度，也可以缩短命中时间、降低功率，不过这种权衡要比限制大小涉及的权衡更复杂一些。

缓存命中过程中的关键计时路径由3个步骤组成：

• 使用地址中的索引确定标记存储器的地址；
• 读取的标签值与地址进行比较；
• 如果缓存为组相联缓存，则设置多路转换器以选择正确的数据项。

直接映射的缓存可以将标记核对与数据传输重叠起来，有效缩短命中时间。此外，在采用低相联度时，由于减少了必须访问的缓存行，所以通常还可以降低功率。尽管在各代新型微处理器中，片上缓存的总数已经大幅增加，但由于大容量L1缓存带来的时钟频率影响，所以L1缓存大小最近的涨幅很小，甚至根本没有增长。选择相联度时的另一个考虑因素是消除地址别名的可能性。

在选择缓存大小和相联度时，能耗也是一个因素，在128KB或256KB缓存中，当从直接映射变到两路组相联时，高相联度的能量消耗从大于2到可以忽略。

每次读取操作的能耗随缓存大小、相联度增加而增加。八路组相联缓存的代价之所以很高，是因为并行读取8个标签及相应数据的成本造成的

在最近的设计中，有三种其他因素导致了在第一级缓存中使用较高的相联度。

• 第一，许多处理器在访问缓存时至少需要两个时钟周期，因此命中时间较长可能不会产生太过严重的影响。
• 第二，将TLB排除在关键路径之外（TLB带来的延迟可能要大于高相联度导致的延迟），几乎所有L1缓存都应当是变址寻址的。这就将缓存的大小限制为页大小与相联度的乘积，这是因为只有页内的位才能用于变址。在完成地址转换之前对缓存进行变址的问题还有其他一些解决方案，但提高相联度是最具吸引力的一种，它还有其他一些好处。
• 第三，在引入多线程之后，冲突缺失会增加，从而使提高相联度更具吸引力。

第二种优化：采用路预测以缩短命中时间

这是另外一种可以减少冲突缺失，同时又能保持直接映射缓存命中速度的方法。在路预测技术中，缓存中另外保存了一些位，用于预测下一次缓存访问组中的路或块。这种预测意味着尽早设定多工选择器，以选择所需要的块，在与缓存数据读取并行的时钟周期内，只执行一次标签比较。如果缺失，则会在下一个时钟周期中查看其他块，以找出匹配项。

在一个缓存的每个块中都添加块预测位。根据这些位选定要在下一次缓存访问中优先尝试琊些块。如果顸测正确，则存访问延迟就等于这一快速命中时间。如果预测错误，则尝试其他块，改变路预测器，延迟会增加一个时钟周期。模拟表明，对于一个两路组相联缓存，组预测准确度超过90%；对于四路组相联缓存，超过80%，对I-缓存的准确度优于对D-缓存的准确度。

还有一种扩展形式的路预测，它使用路预测位来判断实际访问的缓存块，可以用来降低功耗（路预测位基本上就是附加地址位〕；这种方法也可称为路选择，当路预测正确时，它可以节省功率，但在路预测错误时则会显著增加时间，这是因为需要重复进行访问，而不仅是重复标记匹配与选择过程。这种优化方法只有在低功率处理器中才可能有意义。

第三种优化：实现缓存访问的流水化，以提高缓存带宽

这种方法就是实现缓存访问的流水化，使第一级缓存命中的实际延迟可以分散到多个时钟周期，从而缩短时钟周期时间、提高带宽，但会减缓命中速度。这一变化增加了流水线的段数，增加了预测错误分支的代价，延长了从发出载入指令到使用数据之间的时钟周期数，但的确更便于采用高相联度的缓存。

第四种优化：采用无阻塞缓存，以提高缓存带宽

对于允许乱序执行的流水化计算机，其处理器不必因为一次数据缓存缺失而停顿。例如，在等待数据缓存返回缺失数据时，处理器可以继续从指令缓存中提取指令。无阻塞缓存（或称为自由查询缓存）允许数据缓存在一次缺失期间继续提供缓存命中，进一步加强了这种方案的潜在优势。这种“缺失时仍然命中”优化方法在缺失期间非常有用，它不会在此期间忽略处理器的请求，从而降低了实际缺失代价。还有一种精巧而复杂的选项：如果能够重叠多个缺失，那缓存就能进一步降低实际缺失代价，这种选项被称为“多次缺失时仍然命中”或者“缺失时缺失”优化方法。只有当存储器系统可以为多次缺失供服务时，第二种选项才有好处，大多数高性能处理器通常都支持这两种优化方法。

对非阻塞缓存进行性能评估时，真正的难度在于一次缓存缺失不一定会使处理器停顿。在这种情况下，很难判断一次缺失造成的影响，因此也就难以计算存储器平均访问时间。实际缺失代价并不等于这些缺失时间之和，而是处理器的非重叠停顿时间。非阻塞缓存的优势评估非常复杂，因为它取决于存在多次缺失时的缺失代价、存储器引用模式以及处理器在有未处理缺失时能够执行多少条指令。

通常，对于一个能够在L2缓存中命中的L1数据缓存缺失，乱序处理器能够隐藏其大部分缺失代价，但不能隐藏更低层次缓存缺失的大部分代价。而在决定支持多少个未处理缺失时，需要考虑多种因素，如下所述。

• 缺失流中的时间与空间局域性，它决定了一次缺失是否会触发对低级缓存或对存储器的新访问操作。
• 对访问请求作出回应的存储器或缓存的带宽。
• 为了允许在最低级别的缓存中出现更多的未处理缺失（在这一级别的缺失时间是最长的），需要在较高级别上支持至少数目相等的缺失，这是因为这些缺失必须在最高级别缓存上启动。
• 存储器系统的延迟。

第五种优化：采用多种缓存以提高缓

我们可以将缓存划分为几个相互独立、支持同时访问的缓存组，而不是将它们看作一个整体。分组方式最初用于提高主存储器的性能，现在也用于DRAM芯片和缓存中。Arm Cortex-A8在其L2缓存中支持1至4个缓存组；Intel Core i7的L1中有4个组（每个时钟周期内可以支持2次存储器访问），L2有8个组。

显然，当访问请求很自然地分布在缓存组之间时，分组方式的效果最佳，所以将地址映射到缓存组的方式影响着存储器系统的行为。一种简单有效的映射方式是将缓存块地址按顺序分散在这些缓存组中，这种方式称为顺序交错。例如，如果有4个缓存组，0号缓存组中的所有缓存块地址对4求模后余0，1号缓存组中的所有缓存块地址对4求模后余1，以此类推。图中显示了这种交错方式。采用分组方式还可以降低缓存和DRAM中的功耗。

图2使用块寻址的四路交错缓存组。假定每个块64个字节，这些地址需要分别乘以64才能实现字节寻址

第六种优化：关键字优先和提前重启动以降低缺失代价

这一技术的事实基础是人们观测到处理器在某一时刻通常仅需要缓存块的一个字。这一策略显得“不够耐心”：无须等待完成整个块的载入过程，一旦载入被请求字之后，立即将其发出，然后就重启处理器。下面是两个待定策略。

• 关键字优先：首先从存储器中请求缺失的字，在其到达缓存之后立即发给处理器；使处理器能够在载入块中其他字时继续执行。
• 提前重启动：以正常顺序提取字，但只要块中的被请求字到达缓存，就立即将其发送给处理器，让处理器继续执行。

通常，只有在采用大型缓存块的设计中，这些技术才有用武之地，如果缓存块很小，它们带来的好处是很低的。注意，在载入某个块中的其余内容时，缓存通常可以继续满足对其他块的访问请求。

不过，根据空间局域性原理，下一次引用很可能就会指向这个块的其余内容。和非阻塞缓存一样，其缺失代价的计算也不是非常容易。在采用关键字优先策略时，如果存在第二次请求，实际缺失代价等于从本次引用开始到第二部分内容到达之前的非重叠时间。关键字优先策略和提前重启动策略的好处取决于块的大小以及在尚未获取某部分内容时又出现另一次访问的机率。

第七种优化：合并写缓冲区以降低缺失代价

因为所有存储内容都必须发送到层次结构的下一层级，所以直写缓存依赖于写缓冲区。即使是写回缓存，在替代一个块时也会使用一个简单的缓冲区。如果写缓冲区为空，则数据和整个地址被写到缓冲区中，从处理器的角度来看，写入操作已经完成；在写缓冲区准备将字写到存储器时，处理器继续自己的工作。如果缓冲区中包含其他经过修改的块，则检查它们的地址，看看新数据的地址是否与写缓冲区中有效项目的地址匹配。如果匹配，则将新数据与这个项目合并在一起。这种优化方法称为写合并。如果缓冲区已满，而且没有匹配地址，则缓存（和处理器）必须等待，直到缓冲区中拥有空白项目为止。由于多字写入的速度通常快于每次只写入一个字的写入操作，所以这种优化方法可以更高效地使用存储器。

这种优化方式还会减少因为写缓冲区已满而导致的停顿。图中显示了一个写缓冲区在采用和不采用写合并时的情况。假定这个写缓冲区中有四项，每一项有4个位的字。在采用这一优化方法时，图中的4个字可以完全合并，放在写缓冲区的一个项目中，而在不采用这一优化方法时，对写缓冲区的连续地址执行4次存储操作，将整个缓冲区填满，每个项目中保存一个字。

注意，输入/出设备寄存器经常被映射到物理地址空间。由于IO寄存器是分享的，不能像存储器中的字数组那样操作，所以这些IO地址不能允许写合并。例如，它们可能要求为每个IO寄存器提供一个地址和一个数据字，而不能只提供一个地址进行多字写入。为了现这些副作用，通常由缓存将这些页面进行标记，表明其需要采用非合并直写方式。

图中为了说明写合并过程。上面的写缓冲区未采用该技术，下面的写缓冲区采用了这一技术。在进行合并时，4次写入内容被合并到一个缓冲区项目中；而未进行合并时，4次写入操作就填满了整个缓冲区，每个项目的四分之三被浪费。这个缓冲区有四个项目，每一项保存4个纠位字。每个项目的地址位于左侧，有效位（v）指明这个项目的下面8个连续字节是否被占用（未采用写合并时，图中上半部分右侧的字只会用于同时写多个字的指令。）

第八种优化：采用编译器优化以降低缺失率

前面介绍的技术都需要改变硬件。下面这种技术可以在不做任何硬件改变的情况下降低缺失率。

这种神奇的降低效果来自软件优化。处理器与主存储器之间的性能差距越拉越大，己经促使编译器编写入员深人研究存储器的层次结构，以了解能否通过编译时间优化来提高性能。同样，研究内容包括两个方面：指令缺失性能改进和数据缺失性能改进。下面给出的优化技术在很多现代编译器中均有应用。

循环交换

一些程序中存在嵌套循环，它们会以非连续顺序访问存储器中的数据。只要交换一下这些循环的嵌套顺序，就可能使程序代码按照数据的存储顺序来访问它们。如果缓存中无法容纳这些数组这一技术可以通过提高空间局域性来减少缺失；通过重新排序，可以使缓存块中的数据在被替换之前，得到最大限度的充分利用。

例如，设x是一个大小为5000*100的两维数据，其分配方式使得x[i,j]和x[i,j+1]相邻（由于这个数组是按行进行排列的，所以我们说这种顺序是以行为主的），以下两段代码说明可以怎样来优化访问过程：

/* 优化之前 */
for(j=0; j< 100; j=j+1)
    for(i=0; i<5000; i++)
        x[i][j] = 2 * x[i][j];

/* 优化之后 */
for(i=0; i<5000; i++)
    for(j=0; j< 100; j=j+1)
        x[i][j] = 2 * x[i][j];

原代码以100个字的步幅跳跃式浏览存储器，而修改后的版本在访问了一个缓存块中的所有字之后才进入下一个块。这一优化方法提高了缓存性能，却没有影响到所执行的指令数目。

分块

这一优化方法通过提高时间局域性来减少缺失。这一次还是要处理多个数组，有的数组是按行来访问的，有的是按列来访问的。由于在每个循环迭代中都用到了行与列，所以按行或按列来存储数组并不能解决问题（按行存储称为行主序，按列存储称为列主序）。这种正交访问方式意味着在进行循环交换之类的转换操作之后，仍然有很大的改进空间。

分块算法不是对一个数组的整行或整列进行操作，而是对其子矩阵（或称块）进行操作。其目的是在缓存中载入的数据被替换之前，在最大限度上利用它。下面这段执行矩阵乘法的示例可以帮助理解这一优化方法的动机：

/* 优化之前 */
for (i = 0; i < N; i ++)
    for (j = 0; j < N; j ++) {
        r = 0;
        for (k = 0; k < N; k ++)
            r = r + y[i][k] * z[k][j];
        x[i][j] = r;
    }

两个内层循环读取Z的所有N×N个元素，重复读取Y中一行的同一组N个元素，再写入X的一行N个元素。图中是访问这三个数组的一个快照。深色阴影区域表示最近的访问，浅色阴影区域表示较早的访问，白色表示还没有进行访问。

容量缺失的数目显然取决于N和缓存的大小。如果它能容纳所有这3个N×N矩阵，只要没有缓存冲突，就一切正常。如果缓存可以容纳一个N×N矩阵和包含N个元素的一行，则至少Y的第i行和数组Z可以停留在缓存中。如果缓存的容量更小，那可能对于X和Z都会发生缺失。在最差情况下，进行N^3次操作可能需要从存储器中读取2N^3 + N^2个字。

三个数组X、Y和Z的快照，其中N=6，i=1。对数组元素访问的前后时间用阴影表示。白色表示还没有被访问过，浅色表示较早的访问，深色表示最近的访问。与下图相对照，为了计算X的新元素，会重复读取Y和Z的元素。在行或列的旁边显示了用于访问这些数组的变量i，j和k。

为了确保正在访问的元素能够放在缓存中，对原代码进行了修改，改为计算一个大小为B×B的子矩阵。两个内层循环现在以大小为B的步长进行计算，而不是以X和Z的完整长度为步长。B被称为分块因子。（假定x被初始化为0。）

/* 优化之后 */
for (jj = 0; jj < N; jj += B)
for (kk = 0; kk < N; kk += B)
for (i = 0; i < N; i ++)
    for (j = kk; j < min(jj+B, N); j ++) {
        r = 0;
        for (k = kk; k < min(kk+B, N); k ++)
            r = r + y[i][k] * z[k][j];
        x[i][j] = r;
    }

图展示了使用分块方法对三个数组的访问。仅观察容量缺失，从存储器中访问的总字数为2N^3/B+N^2。这一总数的改善因素大约为B。由于Y获益于空间局域性，Z获益于时间局域性，所以分层方法综合利用了空间局域性和时间局域性。

尽管我们的目标是降低缓存缺失，但分块方法也可用于帮助寄存器分配。通过设定一个较小的分块大小，使这个块能够保存在寄存器中，可以在最大程度上降低程序中的载入与存储数量。

第九种优化：对指令和数据进行硬件预取，以降低缺失代价或缺失率

在处理器请求项目之前，预先提取它们。指令和数据都可以预先提取，既可以直接放在缓存中，也可以放在一个访问速度快于主存储器的外部缓冲区中。指令预取经常在缓存外部的硬件中完成。通常，处理器在一次缺失时提取两个块：被请求块和下一个相邻块。被请求块放在它返回时的指令缓存中，预取块被放在指令流缓冲区中。如果被请求块当前存在于指令流缓冲区中，则原缓存请求被取消，从流缓冲区中读取这个块，并发出下一条预取请求。

Intel core i7支持利用硬件预先提取到L1和L2中，最常见的预取情况是访问下一行。一些较早的Intel处理器使用更主动的硬件预取，但会导致某些应用程序的性能降低，一些高级用户会因此而关闭这一功能。图显示了在启用硬件预取时，部分SPEC2000程序的整体性能改进。注意，这一数字仅包含12个整数程序中的两个，而大多数SPEC浮点程序则都包含在内。

图在intel Pentium4上启用硬件预取之后，12个SPECInt 2000基准测试中的2个测试、14个SPECfp2000基准测试中的9个測试获得的加速比。图中仅给出从预取中获益最多的程序，对于图中未给出的15个SPEC基准测试，顸取加速比低于15%

预取操作需要利用未被充分利用的存储器带宽，但如果它干扰了迫切需要的缺失内容，反而可能会实际降低性能。在编译器的帮助下，可以减少无用预取。当预取操作正常执行时，它对功率的影响可以忽略。如果未用到预取数据或者替换了有用数据，预取操作会对功率产生非常负面的影响。

第十种优化：用编译器控制预取，以降低缺失代价或缺失率

作为硬件预取的替代方法，可以在处理器需要某一数据之前，由编译器插入请求该数据的预取指令。共有以下两种预取。

• 寄存器预取将数据值载入到一个寄存器中。
• 缓存预取仅将数据载入到缓存中，而不是寄存器中。

这两种预取都可能是故障性的，也都可能是非故障性的；也就是说，其地址可能会导致虚拟地址错误异常和保护冲突异常，也可能不会导致。利用这一术语，正常的载入指令可能被看作是“故障性寄存器预取指令”。非故障性预取只是在通常导致异常时转换为空操作，而这正是我们想要的结果。

最有效的预取对程序来说是“语义透明的”：它不会改变寄存器和存储器的内容，也不会导致虚拟存储器错误。今天的大多数处理器都提供非故障性缓存预取。本节假定非故障性缓存预取，也称为非绑定预取。

只有当处理器在预取数据时能够继续工作的情况下，预取才有意义；也就是说，缓存在等待返回预取数据时不会停顿，而是继续提供指令和数据。可以想到，这些计算机的数据缓存通常是非阻塞性的。

与硬件控制的预取操作类似，这里的目标也是将执行过程与数据预取过程重叠起来。循环是重要的预取优化目标，因为它们本身很适于进行预取优化。如果缺失代价很小，编译器只需要将循环展开一两次，在执行时调度这些预取操作。如果缺失代价很大，它会使用软件流水线或者将循环展开多次，以预先提取数据，供后续迭代使用。

不过，发出预取指令会导致指令开销，所以编译器必须非常小心地确保这些开销不会超过所得到的好处。如果程序能够将注意力放在那些可能导致缓存缺失的引用上，就可以避免不必要的预取操作，同时明显缩短存储器平均访问时间。

许多处理器支持缓存预取指令，高端处理器还经常在硬件中完成某种类型的自动预取。

缓存优化小结

表中估计了它们对复杂度的影响，其中“+”表明该技术会改进该项因素，“-”表明会损害该项因素。

存储器技术与优化

主存储器在层次结构上位于缓存的下一层级。主存储器满足缓存的需求，并充当接口，既是输入的目的地，又是输出的源头。对主存储器的性能度量同时强调延迟和带宽。传统上，主存储器延迟（它会影响缓存缺失代价）是缓存的主要考虑因素，而主存储器带宽则是微处理器和I/O的主要考虑因素。

由于多级缓存日益普及，而且采用较大的分块，使主存储器带宽对于缓存也非常重要。事实上，缓存设计人员增大块大小就是为了利用更高的存储器带宽。在过去，对主存储器的革新就是改变构成主存储器的众多DRAM芯片（比如多个存储器组）的组织方式。在使用存储器组时，通过拓宽存储器或其总线，或者同时加宽两者，可以提供更大的带宽。

但是，具有讽刺意味的是，随着单片存储器芯片容量的增加，在同样大小的存储器系统中，所需要的芯片越来越少，从而降低了存储器系统容量不变、带宽加大的可能性。为使存储器系统跟上现代处理器的带宽需求，存储器革新开始在DRAM芯片自身内部展开。

存储期延迟主要由两部分组成，访问时间和周期时间。访问时间是发出读取请求到收到所需字之间的时间，周期时间是指对存储器发出两次不相关请求之间的最短时间。

SRAM

SRAM的第一个字母表示静态。DRAM电路的动态本质要求在读取数据之后将其写回，因此在访问时间和周期时间之间存在差异，并需要进行刷新。SRAM不需要刷新，所以存在时间与周期时间非常接近。SRAM通常使用6个晶体管保存1位数据，以防止在读取信息时对其造成干扰。在待机模式中，SRAM只需要很少的功率来维持电荷。

DRAM技术

早期DRAM的容量增大时，由于封装上需要提供所有必要的地址线，所以封装成本较高。解决方案是对地址线进行复用，从而将地址管脚数砍去一半。图中给出基本的DRAM组成结构。先在行选通（RAS）期间发送一半地址。然后在列选通（CAS）期间发送另一半地址。行选通和列选通等名字源于芯片的内部结构，这些存储器的内部是一个按行和列寻址的长方形矩阵。

对DRAM的另一要求来自其第一个字母D表示的特性，即动态（dynamic）。为了在每个芯片中容纳更多的位，DRAM仅使用一个晶体管来存储一位数据。信息的读取过程会破坏该信息，所以必须进行恢复。这是DRAM周期时间一般要长于访问时间的原因之一；近来，DRAM已经引入了多个组，从而可以隐藏访问周期中的重写部分，见图。此外，为了防止在没有读写某一个位时丢失信息，必须定期“刷新”该位。幸运的是，只需对一行进行读取就可以同时刷新该行。因此，每个DRAM必须在某一特定时间窗口内访问每一行。

图为DRAM中的内部组成结构。现代DRAM是以“组”为单位进行组织的，DDR3通常有4组。每一组由一系列行构成。发送PRE（precharge）命令会打开或关闭一个组。行地址随Act（activate）命令发送，该命令会将一个行传送到缓冲区中。将行放入缓冲区后，就可以采用两种方式进行传送，一种是根据DRAM的宽度采用连续列地址传送（在DDR3中，这一宽度通常为4位、8位、16位），另一种是指定块传送方式，并给出起始地址。每个命令和块传送过程，都以一个时钟进行同步。

这一要求意味着存储器系统偶尔会有不可用时间，因为它要发出一个信号，告诉每个芯片进行刷新。刷新时间通常是对DRAM中每一行进行完整存储器访同（RAS和CAS）的时间。由于DRAM中的存储器矩阵在概念上是方形的，所以一次刷新中的步骤通常是DRAM容量的平方根。DRAM设计人员尽力将刷新时间保持在总时间的5％以下。

刷新操作是存储器延迟发生变化的另一个原因，从而也会影响缓存缺失代价的变化。

Amdahl提出一条经验规律：要保持系统的平衡，存储器容量应当随处理器的速度线性增长，所以一个运算速度为1000MIPS的处理器应当拥有1000 MB的存储器。处理器设计人员依靠DRAM来满足这一要求。过去，他们可以指望存储器容量每三年翻两番，也就是年增长率为55％。遗憾的是，DRAM现在的性能增长速度非常慢。表2-2给出了行访问时间的性能改变，它与延迟有关，每年大约为5％。CAS或数据传输时间与带宽有关，其增长速度超过上述
速度的两倍。

尽管我们前面讨论的是独立芯片，但DRAM通常是放在被称为双列直插存储模块（DIMM）的小电路板上出售的。DIMM通常包括4-16个DRAM，对于桌面系统和服务器系统，它们通常被组织为8字节宽度（+ECC）。

提高DRAM芯片内部的存储器性能

前面曾经提到，对DRAM的访问分为行访问和列访问两部分。DRAM必须在DRAM内部缓冲一行中的所有位，为列访问做好准备，一行的位数通常等于DRAM大小的平方根，比如，4Mbit DRAM的每行有2Kbit。随着DRAM容量的增大，添加了一些附加结构，也多了几种提高带宽的可能性。

第一，DRAM添加了定时信号，允许复访问行缓冲区，从而节省了行访问时间。这种缓冲区的出现非常自然，因为每个数组会为每次访问操作缓冲1024-4094位信息。最初，在每次传输时都需要发送不同的列地址，从而在每组新的列地址之后都有一定的延迟时间。

DRAM原来有一个与存储器控制器相连的异步接口，所以每次传输都需要一定的开销，以完成与控制器的同步。第二，向DRAM接口添加一个时钟信号，使重复传输不需要承担这一开销。这种优化的名字就是同步DRAM（SDRAM）。SDRAM通常还有一个可编程寄存器，用于保存请求字节数，因此可以在几个周期内为每个请求发送许多字节。通常，将DRAM置于突发模式，不需要发送任何新地址就能进行8次或更多次的16位传输；这种模式支持关键字优先传
输方式，是唯一能够达到表2-3所示峰值带宽的方法。

第三，随着存储器系统密度的增加，为了从存储器获得较宽的比特流，而又不必使存储器系统变得过大，人们拓展了DRAM的宽度。原来提供一种4位传输模式；2010年，DDR2和DDR3 DRAMS已经拥有宽达16位的总线。

第四种提高带宽的DRAM重要创新是在DRAM时钟信号的上升沿和下降沿都传输数据，从而使峰值数据传输率加倍。这种优化方法被称为双倍数据率（DDR）。

为了提供交错（interleaving）的一些优点，并帮助进行电源管理，SDRAM还引入了分组，将一块SDRAM分为2-8个可以独立运行的块（在目前的DDR3 DRAM中为8块）。在一个DRAM中创建多个组可以有效地添加另一个地址段，它现在由组号、行地址和列地址组成。在发送指定一个新组的地址时，这个组必须己经打开，会增加一些延迟。分组与行缓冲区的管理完全由现代存储器控制接口处理，这样，如果后续地址指定了一个开放组的相同行时，只需要发送列地址就能快速完成访问。

在将DDR SDRAM封装为DIMM形式时，会用DIMM峰值带宽进行标记，这种标记方法很容易引起混淆。比如，之所得到PC2100这样一个DIMM名称，是源于133MHz x 2 x 8字节=2100MB/s，为了避免这种混淆，在对芯片本身进行标记时，给出的不是其时钟频率，而是每秒比特数，因此一个133MHz的DDR芯片被称为DDR266。表2-3给出了时钟频率、每芯片每秒钟的传送数目、芯片名称、DIMM带宽和DIMM名称之间的关系。

降低SDRAM中的功耗

动态存储器芯片中的功耗由静态（或待机）功率和读写期间消耗的动态功率构成，这两者取决于工作电压。在大多数高端DDR3 SDRAM中，工作电压已经降到1.35-1.5伏，与DDR2 SDRAM相比，显著降低了功率。分组的增加也降低了功率，这是因为每次仅读取并预充电一个分组中的行。

除了这些变化之外，所有最新SDRAM都支持一种省电模式，通知DRAM忽略时钟即可进入这一模式。省电模式会禁用SDRAM，但内部自动刷新除外（如果没有自动刷新，当进入省电模式时间长于刷新时间后，将会导致存储器内容丢失）。图2-12给出了一个2Gbit DDR3 SDRAM在三种情况下的功耗。从低功率模式返回正常模式所需的确切延迟时间取决于SDRAM，但从自动刷新低功率模式返回正常状态的时间一般为200个时钟周期；在第一个命令之前复位模式寄存器可能需要延长一些时间。

DDR3 SDRAM在3种不同运行条件下的功耗：低功率（关闭）模式、典型系统模式。（在读取操作中，DRAM有30%的时间处于活动状态，在写入操作中有15％的时间处于活动状态）和完全活动模式，在这种模式下，DRAM在非预充电状态下持续读取或写入。读取和写入采用由8次传输组成的突发形式。

闪存

闪存是一种EEPROM（电可擦可编程只读存储器），它通是只读的，但可以檫除。闪存的另一个重要特性是能在没有任何供电的情况下保存其内容。

闪存在PMD中用作备份存储，其工作方式与笔记本型计算机或服务器中的磁盘相同。此外，由于大多数PMD的DRAM数量有限，所以闪存在很大程度上还要充当存储器层次结构的一级，闪存使用的体系结构与标准DRAM有很大不同，性质也有所不同。最重要的区别在于以下几方面。

1. 在改写内存之前，必须对其进行擦除，（在高密度闪存中，称为NAND闪存，大多数计算机都采用这种闪存）它的擦除过程是按块进行的，而不是单独擦除各个字节或各个字。这意味着在需要向闪存中写入数据时，必须对整个块进行处理，或者全是新数据，或者将要写入的数据与块中的其他内容合
   并在一起。
2. 闪存是静态的（也就是说，即使在没有供电的情况下，它也能保持其内容），在未进行读写时，只消耗非常低的一点功率（在待机模式下会低于一半，在完全非活动状态上可以为零）。
3. 对任何一个块来说，闪存为其提供有限数目的写入周期，通常至少为1000000个。这样，系统可以确保写入块均匀分布在整个存储器中，从而在最大程度上延长闪存系统的寿命。
4. 高密度闪存比SDRAM便宜，但比磁盘贵：闪存的价格大约是2美元/GB，SDRAM为20美元到40美GB，磁盘为0.09美元/GB。
5. 闪存的速度比SDRAM慢得多，但比磁盘快得多。从DDR SDRAM进行类似传输需要的时间大约长四分之一，而从磁盘上传输则大约慢1000倍。对于写入操作，这种区别更是大得多，SDRAM至少比闪存快10倍，也可能达到100倍，具体数值取决于环境。

提高存储器系统的可靠性

缓存和主存储器容量的增大也大幅提高了在制造过程期间和对存储器单元进行动态冲击时（主要来自宇宙射线）出现错误的概率。这些动态错误会改变存储器单元的内容，但不会改变电路，称之为软错误。所有DRAM，闪存和许多SRAM在制造时都留有备用行，这样可以容忍少量的制造缺陷，只需要通过编程方式用备用行替代缺陷行即可。除了必须在配置期间纠正的制造错误之外，还可能在运行时发生硬错误，它可能会永久改变一个或多个存储器单元的运行方式。

动态错误可以使用奇偶校验位检测，可以使用纠错码（ECC）检测和纠正。因为指令缓存是只读的，用奇偶校验位就足够了。在更大型的数据缓存和主存储器中，则使用ECC技术来检测和纠正错误。奇偶校验位只需要占用一个数据位就可以检测一系列数据位中的一个错误。由于无法使用奇偶校验位来检测多位错误，所以必须限制用奇偶校验位提供保护的位数。一个常用比值是每8个数据位使用一个奇偶校验位。如果采用ECC技术，在每64个数据位中，8位的开销成本可以检测两个错误，纠正一个错误。

保护：虚拟存储器和虚拟机

通过虚拟存储器提供保护

页式虚拟存储器（包括缓存页表项目的变换旁视缓冲区）是保护进程免受相互伤害的主要机制。

多道程序设计（multi programming，几个同时运行的程序共享一台计算机的资源）需要在各个程序之间提供保护和共享，从而产生了进程概念。在任意时刻，必须能够从一个进程切换到另一个进程。这种交换被称为进程切换或上下文切换。操作系统和体系结构联合起来就能使进程共享硬件而不会相互干扰。为此，在运行一个用户进程时，体系结构限制用户进程能够访问的资源，但要允许操作系统进程访问更多资源。体系结构至少要做到以下几点。

1. 提供至少两种模式，指出正在运行的进程是用户进程还是操作系统进程。后者有时被称为内核进程或管理进程。
2. 提供一部分处理器状态信息，用户进程可以使用但不能写入。这种状态信息包括用户/管理模式位、异常启用/禁用位和存储器保护位。之所以禁止用户写入这些状态信息，是因为如果用户可以授予自己管理权限、禁用异常或者改变存储器保护，那操作系统就不能控制用户进程了。
3. 提供处理器借以从用户模式转为管理模式及反向转换的机制。前一种转换通常通过系统调用完成，使用一种特殊指令将控制传递到管理代码空间的一个专用位置。保存系统调用时刻的程序计数器，处理器转入管理模式。返回用户模式的过程类似于一个全程返回过程，恢复到先前的用户/管理模式。
4. 提供限制存储器访问的机制，在上下文切换时不需要将一个进程切换到磁盘就能保护该进程的存储器状态。

到目前为止，最流行的机制还是添加对虚拟存储器各个页面的保护性限制。固定大小的页面（通常长4KB或8KB）通过一个页表由虚拟地址空间映射到物理地址空间。这些保护性限制就包含在每个页表项中。保护性限制可以决定一个用户进程能否读取这个页面，一个用户进程能否写这个页面以及能否从这个页面执行代码。此外，如果一个进程没有包含在页表中，那它就既不能读取也不能写入一个页面。由于只有操作系统才能更新页表，所以分页机制提供了全面的访问保护。

分页虚拟存储器意味着每次存储器访问在逻辑上都要花费至少两倍的时间，一次存储器访问用以获取物理地址，第二次访问用于获取数据。这种成本可能太过高昂了。解决方案就是依靠局域性原理，如果这些访问具有局域性，那么访问操作的地址转换也肯定具有局域性。只要将这些地址转换放在一个特殊的缓存中，存储器访问就很少再需要第二次访问操作来转换地址了。这种特殊的地址转换缓存被称为变换旁视缓冲区（TLB）。

TLB项目类似于缓存项目，其中的标记保存虚拟地址部分，数据部分保存物理页地址、保护字段、有效位，通常还有一个使用位和一个更改位（dirty bit）。操作系统在改变这些位时，改变页表中的值，然后使相应的TLB项失效。当这个项目新载入到页表中时，TLB即获得这些位的准确副本。

通过虚拟机提供保护

有一个与虚拟存储器相关而且几乎与它一样古老的概念，那就是虚拟机（VM）。它们最早是在20世纪60年代后期提出的，多年以来一直是大型机计算的重要组成部分。近来得到广泛关注，原因如下：

• 隔离与安全在现代系统中的重要性提高
• 标准操作系统的安全性和可靠性出现问题；
• 许多不相关用户（比如一个数据中心或云中的用户〕共享同一计算机，
• 处理器原始速度的飞速增大，使虚拟机的开销更容易接受。

最常见的情况是，VM支持的ISA与底层硬件相同；但也有可能支持不同的ISA，在ISA之间迁移时经常采用这种方法，这样，在能够迁移到新ISA之前，使软件能够继续在原ISA上使用。在我们重点关注的虚拟机中，所提供的ISA与其底层硬件相匹配。这种虚拟机称为（操作）系统虚拟机。它们让虚拟机用户感觉到自己拥有整个计算机，包括操作系统的副本在内。一台计算机可以运行多个虚拟机，可以支持多种不同操作系统。在传统平台上，一个操作系统“拥有”所有硬件资源，但在使用虚拟机时，多个操作系统一起共享硬件资源。

为虚拟机提供支持的软件称为虚拟机监视器(VMM)或管理程序，VMM是虚拟机技术的核心。底层硬件平台称为主机，其资源在来宾VM之间共享。VMM决定了如何将虚拟资源映射到物理资源：物理资源可以分时共享、划分，甚至可以在软件内模拟。VMM要比传统操作系统小得多。

一般来说，处理器虚拟化的成本取决于工作负载。用户级别的处理器操作密集型程序的虚拟化开销为零，这是因为很少会调用操作系统，所有程序都以原速运行。与之相对的是L/O操作密集的工作负载，它们通常也会大量涉及操作系统，执行许多系统调用（以满足I/O需求）和可能导致高虚拟化开销的特权指令。如果涉及大量I/O操作的工作负载也是IO密集型的，由于处理器经常要等待IO，所以处理器虚拟化的成本可以完全被较低的处理器利用率所隐藏。

尽管我们这里关心的是VM提供保护的功能，但VM还提供了其他两个具有重要商业价值的优点。

1. 软件管理。VM提供一种能运行整个软件栈的抽象层。一种典型部署是用一部分VM运行原有OS，大量VM运行当前稳定的OS，一小部分VM用于测试下一代OS。
2. 硬件管理。需要多个服务器的原因之一是希望每个应用程序都能在独立的计算机上与其兼容的操作系统一起运行，这种分离可以提高系统的可靠性。VM允许这些分享软件栈独立运行，却共享硬件，从而减少了服务器的数量。还有一个例子，一些VMM允许将正在运行的VM迁移到不同计算机上，既可能是为了平衡负载，也可能是为了撤出发生故障的硬件。

对虚拟机监视器的要求

一个VM监视器必须完成哪些任务？它向来宾软件提供一个软件接口，必须使不同来宾的状态相互隔离，还必须保护自己免受客户端软件的破坏（包括来宾操作系统）。定性需求包括：

• 来宾软件在VM上的运行情况应当与在原始硬件上完全相同，当然，与性能相关的行为或者因为多个VM共享固定资源所造成的局限性除外；
• 来宾软件应当不能直接修改实际系统资源的分配。

为了实现处理器的“虚拟化”，VMM必须控制几乎所有操作——特权状态的访问、地址转换、异常和中断，即使目前正在运行的来宾VM和操作系统正在临时使用它们，也不应当影响到这些控制。

例如，在计时器中断时，VMM将挂起当前正在运行的来宾VM，保存其状态、处理中断、判断接下来运行哪个来宾VM，然后载入其状态。依赖计时器中断的来宾都会有一个由VMM提供的虚拟计时器和仿真计时器。

为了进行管理，VMM的管理权限必须高于来宾，后者通常运行于用户模式；这样还能确保任何特权指令的执行都由VMM处理。系统虚拟机的基本需求几乎与上述分页虚拟存储器的要求相同。

• 至少两种处理器模式：系统模式和用户模式。
• 指令的一些特权子集只能在系统模式下使用，如果在用户模式下执行将会导致陷阱。所有系统资源都只能通过这些指令进行控制。

虚拟机（缺少）的指令集体系结构支持

如果在设计ISA期间已经为VM作了规划，那就可以比较轻松地减少VMM必须执行的指令数、缩短模拟这些指令所需要的时间。如果一种体系结构允许、直接在硬件上运行，则为其冠以可虚拟化的头衔。

由于VMM必须确保客户系统只能与虚拟资源进行交互，所以传统的来宾操作系统是作为一种用户模式程序在VMM的上层运行的。因此，如果一个来宾操作系统试图通过特权指令访问或修改与硬件相关的信息，它会向VM发出陷阱中断。VMM随后可以对相应的实际资源实进行适当修改。

因此，如果任何以用户模式执行的指令试图读写此类敏感信息陷阱，VMM可以截获它，根据来宾操作系统的需要，向其提供敏感信息的一个虚拟版本。如果缺乏此类支持，则必须采取其他措施。

虚拟机对虚拟存储器和IO的影响

由于每个VM中的每个来宾操作系统都管理其自己的页表集，所以虚拟存储器的虚拟化就成为另一项挑战。为了实现这一功能，VMM区分了实际存储器（real memory）和物理存储器，使实际存储器成为虚拟存储器与物理存储器之间的独立、中间级存储器。来宾操作系统通过它的页表将虚拟存储器映射到实际存储器，然页表将来宾的实际存储器映射到物理存储器。虚拟存储器体系结构可以通过页表指定；也可以通过TLB结构指定，许多RISC体系结构属于此类。

VMM没有再为所有存储器访问进行一级间接迂回，而是维护了一个影子页表，直接从来宾虚拟地址空间映射到硬件的物理地址空间。通过检测来宾页表的所有修改，VMM就能保证硬件在转换地址时使用的影子页表项与来宾操作系统环境的页表项一一对应，只是用正确的物理页代替了来宾表中的实际页。因此，只要来宾试图修改它的页表，或者试图访问页表指针，VMM都必须加以捕获。这一功能通常通过以下方法来实现：对来宾页表提供写保护，并捕获来宾操作系统对页表指针的所有访问尝试。前面曾经指出，如果对页表指针的访问属于特权操作，就会很自然地实现捕获。

IBM 370体系结构在20世纪70年代添加了一个由VMM管理的迂回层，解决了页表问题。来宾操作系统和以前一样保存自己的页表，所以就不再需要影子页表。在许多RISC计算机中，为了实现TLB的虚拟化，VMM管理实际TLB，并拥有每个来宾VM的TLB内容副本。为实现这一功能，所有访问TLB的功能都必须被捕获。具有进程ID标记的TLB可以将来自不同VM与VMM的项目混合在一起，所以不需要在切换VM时刷新TLB。与此同时，VMM在后台支持VM的虚拟进程ID与实际进程ID之间的映射。

体系结构中最后一个要虚拟化的部分是I/O。到目前为止，这是系统虚拟化中最困难的一部分，原因在于连接到计算机的I/O设备数目在增加，而且这些IO设备的类型也变得更加多样化。另外一个难题是在多个VM之间共享实际设备，还有一个难题是需要支持不同的设备驱动程序，在同一VM系统上支持不同来宾操作系统时尤为困难。为了仍然能够实现VM，可以为每个VM提供每种I/O设备驱动程序的一个通用版本，然后交由VMM来处理实际IO。

将虚拟设备映射到物理IO设备的方法取决于设备类型。例如，VMM通常会对物理进行分区，为来宾VM创建虚拟磁盘，而VMM会维护虚拟磁道与扇区到物理磁盘与扇区的映射。网络接口通常会在非常短的时间片内在VM之间共享，VMM的任务就是跟踪虚拟网络地址的消息，以确保来宾VM只收到发给自己的消息。

交叉问题：存储器层次结构的设计

保护和指令集体系结构

保护是由体系结构和操作系统协力完成的。但是当虚拟存储器变得更为普及时，体系结构必须修改现有指令集体系结构中一些不便使用的细节。在历史上，IBM大型机硬件和VMM通过以下3个步骤来提高虚拟机的性能：

• 降低处理器虚拟化的成本
• 降低由于虚拟化而造成的中断开销
• 将中断传送给正确的VM，而不调用VMM，以降低中断成本。

Intel和AMD芯片集的最近版本添加了一些指令，用以支持VM中的设备，在较低层级屏蔽来自每个VM的中断，将中断发送到适当的VM。

缓存数据的一致性

数据可以同时出现在存储器和缓存中。只要处理器是唯一修改或读取数据的组件。并且缓存存在于处理器和存储器之间，那处理器看到旧副本或者说过期副本的危险性就很低。后面将会看到，使用多个处理器和IO设备增大了副本不一致及读取错误副本的机会。

处理器出现缓存一致性问题的频率与IO不同。对IO来说出现多个数据副本是非常罕见的情况，而一个在多处理器上运行的程序会希望在几个存中拥有同一数据的多个副本。多处理器程序的性能取决于系统共享数据的性能。IO缓存一致性问题可以表述如下：IO发生在计算机中的什么地方？在I/O设备与缓存之间，还是在IO设备与主存储器之间？如果输入将数据放在缓存中，而且输出从缓存中读取数据，那IO和处理器会看到相同数据。这种方法的难点在于它干扰了处理器。可能会导致处理器因为等待IO而停顿。输入还可能会用某些不会马上用到的新数据来取代存中的某些信息，从而对缓存造成干扰。

在带有缓存的计算机中，IO系统的目标应当是防止出现数据过期问题，同时尽可能减少干扰。因此，许多系統喜欢直接对主有储器进行I/O操作，把主存储器当作一个I/O缓冲区。如果使用直写缓存，存储器中将拥有最新的信息副本，在榆出时不存在过期数据问题（这一好处也是处理器使用直写方式的一个原因。遗憾的是，现在通常只会在第一级数据缓存中使用直写方式，由使用写回方式的L2缓存为其提供后盾。

输入操作还需要另外做点功课。软件解决方案是保证输入缓冲区的所有数据块都没有在缓存中。可以将包含缓冲区的页标记为不可缓存，操作系統总是可以向这样一个页面中输入数据。或者，可以由操作系统在输入之前从缓存刷新缓冲区地址。硬件解决方案则是在输入时检查IO地址，查看它们是否在缓存中。如果在缓存中找到了IO地址的匹配项，则使缓存项失效，以免过期数据。所有这些方法也都能用于带有写回缓存的输出操作。

融会贯通：ARM Cortex-A8和Intel i7中的存储器层次结构

ARM Cortex-A8

Cortex-A8是一种支持ARMv7指令集体系结构的可配置核心。它是作为一种IP（知识产权）核心交付的。在嵌入式、PMD和相关市场上，IP核心是主要的技术交付形式；利用这些IP核心已经生成了数十亿个ARM和MIPS处理器。注意，IP核心不同于Intel i7中的核心和AMD Athlon多核心。一个IP核心（它本身可能是多核心）就是为与其他逻辑集成而设计的，因此，它是一个芯片的核心。这些其他逻辑包括专用处理器（比如视频编解码器）、 I/O接口和存储器接口，从而制造出一种专门针对特定应用进行优化的处理器。

整体来说，IP 核心分为两类。硬核心针对特定半导体厂家进行优化，是一些具有外部接口的黑盒（不过这些接口仍然在片上）。硬核心通常仅允许对核心外面的逻辑进行参数设定，比如L2缓存大小，不能对IP核心本身进行修改。软核心的交付形式通常采用一个标准的逻辑元件库。软核心可以针对不同的半导体厂家进行编译，也可以进行修改，不过由于当今IP核心的复杂度，很难对其进行大幅修改。一般来说，硬核心的性能较高、晶片面积较小，而软核心则允许针对不同厂家进行调整，其修改更容易。

当时钟频率高达1 GHz 时，Cortex-A8每个时钟周期可以发出两条指令。它可以支持一种两级缓存层次结构，第一级是一个缓存对（I和D），分别为16 KB或32 KB，其组织形式为四路组相联缓存，并使用路预测和随机替代。其目的是使缓存的访问延迟只有一个周期，使Cortex-A8将从载入到使用的延迟时间保持在一个周期，简化指令提取，在分支缺失导致预取了错误指令时，降低提取正确指令的代价。第二级缓存是可选的，如果存在这一级缓存，则采用八路组相联，容量可达128 KB ~ 1 MB；它的组织形式分为1-4组，允许同时从存储器进行多次传输。一个64位至128位的外部总线用来处理存储器请求。第一级缓存为虚索引、物理标记，第二级缓存为物理索引与标记；这两级缓存的块大小都是64字节。当D缓存为32 KB且页大小为4KB时，每个物理页可以映射到两个不同的缓存地址；在发生缺失时，通过硬件检测可以避免出现混淆现象。

存储器管理由TLB对处理（I和D），每个TLB与32个项目完全相关，页面大小可变（4KB、16KB、64KB、1 MB和16 MB）；TLB中的替换用轮询算法完成。TLB缺失在硬件中处理，它会遍历存储器中的一个页表结构。图2-13显示如何使用32位虚拟地址来索引TLB和缓存，假定主缓存为32 KB，次级缓存为512 KB，页面大小为16 KB。

Cortex-A8存储器层次结构的性能：Cortex-A8的存储器层次结构使用32 KB主缓存和1 MB八路组相联L2缓存来模拟，用整数Minnespec基准测试进行测试。Minnespec 是一个基准测试集，由SPEC2000基准测试组成，但其输入不一样，将运行时间缩短了几个数量级。尽管使用较小规模的输入并不会改变指令混合比例，但它的确会影响缓存行为。例如，根据mcf的测试结果（它是存储器操作最密集的SPEC2000整数基准测试），当缓存为32 KB时，Minnerspec的缺失率只有完整SPEC版本缺失率的65%。当缓存为1 MB时，这种差距为6倍。根据许多其他基准测试，这些比值都与mof的测试结果类似，但绝对缺失率要小得多。由于这一原因，不能将Minniespec基准测试与SPEC2000基准测试进行对比。不过这些数据对于研究L1和L2缺失对整体CPI的相对影响是很有用的。

图中展示了ARM Cortex-A8数据缓存和数据TLB的虚拟地址、物理地址、索引、标记和数据块。由于指令与数据层次结构是对称的，所以这里只给出其中一个。 TLB（指令或数据）与32个项目完全相关联。L1缓存是四路组相联，块大小为64个字节，容量为32 KB。L2缓存是八路组相联，块大小为64个字节，容量为1 MB。本图没有显示缓存和TLB的有效位和保护位，也没有使用可以指示L1缓存预测组的路预测位

即使仅对于L1，这些基准测试（以及作为Minniespec基础的完全SPEC2000版本）的指令缓存缺失率也非常低：大多接近于零，都低于1%。这种低缺失率的原因可能是因为SPEC程序在本质上是计算密集型的，而且四路组相联缓存消除了大多数冲突缺失。图2-14给出了数据缓存结果，这些结果中的L1和L2缺失率非常高。以DDR SDRAM为主存储器时，1 GHz Cortex-A8的L1缺失代价为11个时钟周期，L2缺失代价为60个时钟周期。通过这些缺失代价数据，图2-15给出了每次数据存取的平均代价。

2.6.2 Intel Core i7

i7支持x86-64指令集体系结构，它是80x86体系结构的64位扩展。i7 是包含四个核心的乱序执行处理器。i7中的每个核心采用一种多次发送、动态调度、16 级流水线，每个时钟周期可以执行多达4个80x86指令。i7还使用一种名为“同时多线程”的技术，每个处理器可以支持两个同时线程。2010 年，最快速i7的时钟频率为3.3GHz，指令的峰值执行速度为每秒132亿条指令，四核芯片超过每秒500万条指令。

i7可以支持多达三个存储器通道，每个通道由独立的DIMM组构成，它们能够并行传输数据。i7采用DDR3-1066（DIMM PC8500），峰值存储器带宽超过25 GB/s。i7使用48位虚拟地址和36位物理地址，物理存储器容量最大为36 GB。存储器管理用一个两级TLB处理，表2-4中对此进行了总结。

表2-5总结了i7 的三级缓存层次结构。第一级缓存为虚索引、物理标记，而L2和L3则采用物理索引。图2-16标有对存储器层次结构进行存取的步骤。首先，向揩令缓存发送程序计数器。指令缓存索引为:

2^索引 = 缓存大小/(块大小*组相联度) = 32K/(64*4) = 128 = 2^7

也就是7位。指令地址的页帧（36位）被发送给指令TLB。同时，来自虚拟地址的7位索引（再加上来自块偏移量的另外两位，用以选择适当的16字节，指令提取数）被发送给指令缓存。注意，对于四路相联指令缓存，缓存地址需要13位: 7位用于索引缓存，再加上64字节块的6位块偏移量，但页大小为4KB=2^12，这意味着缓存索引的一位必须来自虚拟地址。使用1位虚拟地址意味着对应块实际上可能位于缓存中的两个不同位置，这是因为对应的物理地址在这一位置既可能为0也可能为1。对指令来说，这样不会有什么问题，因为即使一条指令出现在缓存中的两个不同位置，这两个版本也必然是相同的。但如果允许对数据进行此类重复或别名设置，那在改变页映射时就必须对缓存进行检查，这一事件并非经常出现。注意，只要很简单地应用页着色就能消除出现这种混淆的可能性。如果偶数地址的虛拟页被映射到偶数地址的物理页（奇数页也一样），那么因为虚拟页号和物理页中的低阶位都是相同的，所以就不可能发生这种混淆。

为查找地址与有效页表项（PTE）之间的匹配项而访问指令TLB。除了转换地址之外，TLB还会进行检查，以了解这一访问操作所需要的PTE是否会因为非法访问而产生异常。

指令TLB缺失首先进入L2 TLB，它包含512个页大小为4KB的PTE，为四路组相联。从L2 TLB中载入L1 TLB需要两个时钟周期。如果L2 TLB缺失，则使用一种硬件算法遍历页表，并更新TLB项。在最糟糕情况下，这个页不在存储器中，操作系统从磁盘中获取该页。由于在页面错误期间可能执行数百万条指令，所以这时如果有另一进程正在等待，操作系统将转入该进程。否则，如果没有TLB异常，则继续访问指令缓存。

地址的索引字段被发送到指令缓存的所有4个组中。指令缓存标记为36-7位(索引)-6位(块偏移)=23位。将4个标记及有效位与来自指令TLB中的物理页帧进行对比。由于i7希望每个指令获取16个字节，所以使用6位块偏移量中的2位来选择适当的16个字节。因此，在向处理器发送16字节指令时使用了7+2=9位。L1缓存实现了流水化，一次命中的延迟为4个时钟周期。一次缺失将进入第二级缓存。前面曾经提到，指令缓存采用虚寻址、物理标记。因为第二级缓存是物理寻址的，所以来自TLB的物理页地址包含页偏移量，构成一个能够访问L2缓存的地址。L2索引为:

2^索引 = 缓存大小/(块大小*组相联度) = 256K/(64*8) = 512 = 2^9

所以长30位的块地址（36位物理地址-6位块偏移）被分为一个21位的标记和一个9位的索引。索引和标记再次被发送给统一L2缓存的所有8个组，同时对它们进行比较。如果有一个匹配且有效，则在开头的10周期延迟之后按顺序返回该块，返回速度为每个时钟周期8个字节。

如果L2缓存缺失，则访问L3缓存。对于一个四核i7（它的L3为8MB），其索引大小为：

2^索引 = 缓存大小/(块大小*组相联度) = 8M/(64*16) = 8192 = 2^13

这个长13位的地址被发送给L3的所有16个组。L3 标记的长度为36-(13-6)=17位，将其与来自TLB的物理地址进行对比。如果发生命中，则在初始延迟之后以每个时钟周期16字节的速度返回这个块，并将它放在L1和L3中。如果L3缺失，则启动存储器访问。

如果在L3中没有找到这个指令，片上存储器控制器必须从主存中找到这个块，i7有三个64位存储器通道，它们可以用作一个192位通道，这是因为只有一个存储器控制器，在两个通道上发送的是相同的地址；当两个通道具有相同的DIMM时，就可以进行宽通道传送。每个通道最多支持4个DDR DIMM。由于L3包含在内，所以在数据返回时，会将它们放在L3和L1中。

在发生指令缺失时，由主存储器提供这一指令的总延迟包括用于判断发生了L3缺失的约35个处理器周期，再加上关键指令的DRAM延迟。对于一个单组DDR1600 SDRAM和3.3 GHz CPU来说，在接收到前16个字节之前的DRAM延迟为大约35 ns或100个时钟周期，所以总的缺失代价为135个时钟周期。存储器控制器以每个存储器时钟周期16个字节的速度填充64字节缓存块的剩余部分，这将另外花费15 ns或45个时钟周期。

由于第二级缓存是一个写回缓存，任何缺失都会导致将旧块写回存储器中。i7 有一个10项合并写缓冲区，当缓存的下一级未用于读取时写回脏缓存行。在发生任何缺失时都会查看此写缓冲区，看看该缓存地是否在这个缓冲区中；如果在，则从缓冲区中获取缺失内容。在L1和L2缓存之间使用了一个类似缓冲区。

如果初始指令是一个载入指令，则将数据地址发送给数据缓存和数据TLB，与指令缓存访问非常类似，但有一个非常关键的区别。 第一级数据缓存为八路组相联，也就是说索引是6位(指令缓存为7位)，用于访问此缓存的地址与页偏移相同。因此，就不再需要担心数据缓存中的混淆问题。

假定这个指令是存储指令，而不是载入指令。在发出存储指令时，它会像载入指令一样进行数据缓存查询。发生缺失时，会将这个块放到写缓冲区中，这是因为L1缓存在发生写缺失时不会分配该块。在命中时，存储不会立即更新L1（或L2）缓存，而是要等到确认没有疑问时才会进行更新。在此期间，存储指令驻存在一个“载入-存储”队列中，这是处理器乱序控制机制的一个组成部分。i7还支持从层次结构的下一层级为L1和L2进行预取。在大多数情况下，预取行就是缓存中的下一个块。在仅为L1和L2预取时，就可以避免向存储器执行高成本的提取操作。

我们使用SPECCPU2006基准测试中的19个基准测试（12个整型和7个浮点）来评估i7缓存结构的性能。本节的数据由路易斯安那州大学的LuPeng教授和Ying Zhang博士生收集。

我们首先来看L1缓存。这个32 KB、4路组相联指令缓存的指令缺失率非常低，最主要的原因是因为i7的指令预取十分有效。当然，由于i7不会为单个指令单元生成单独的请求，而是预取16字节的指令数据（通常介于4~ 5个指令之间），所以如何评估这一缺失率需要一点技巧。为了简单起见，如果我们就像处理单一指令引用那样研究指令缓存缺失率，那么L1指令缓存缺失率的变化范围为0.1%-1.8%，平均略高于0.4%。这一比率与利用SPECCPU2006基准测试对指令缓存行为进行的其他研究一致，这些研究也显示指令缓存缺失率很低。

L1数据缓存更有趣，对它的评估需要更强的技巧性，原因如下所述。

• 因为L1数据缓存不进行写入分派，所以写入操作可以命中，从来不会真正缺失，之所以这么说，是因为那些没有命中的写入操作会将其数据放在写缓冲区中，而不会记录为缺失。
• 因为推测有时可能会错误，所以会有一些对L1数据缓存的引用，它们没有对应最终会完整执行的载入或存储操作。这样的缺失应当怎样处理呢?
• 最后，L1数据缓存进行自动预取。发生缺失的预取是否应当计算在内？如果要计算在内，如何计算？

为了解决这些问题，在保持数据量合理的情况下，图2-17以两种方式显示了L1的数据缓存缺失: 一种是相对于实际完成的载入指令数（通常称为“已完成”或“中途退出”），另一种是相对于从任意来源执行的L1数据缓存访问数。可以看到，在仅相对于已完成载入指令测试的缺失率要高出1.6倍（平均9.5%对5.9%）。表2-6以表格形式显示了相同数据。

由于L1数据缓存缺失率达到5%~10%，有时还会更高一些，所以L2和L3缓存的重要性应当就非常明显了。图2-18给出了L2和L3缓存相对于L1引用的缺失率。由于对存储器的一次缺失需要超过100个周期的成本，而且L2中的平均数据觖失率达4%，所以L3的重要性就不言而喻了。如果没有L3，并假定一半指令是载入或存储指令，L2缓存缺失会使CPI增加每条指令2个周期！作为对比，L3的平均数据缺失率为1%，仍然非常显眼，但只有L2缺失率的1/4，是L1缺失率的1/6。

指令级并行及其开发

指令级并行

大约1985年之后的所有处理器都使用流水线来重叠指令的执行过程，以提高性能。由于指令可以并行执行，所以指令之间可能实现的这种重叠称为指令级并行（ILP）。在本章中，我们将研究一系 列通过提高指令并行度来扩展基本流水线概念的技术。本章首先研究数据和控制冒险带来的局限性，然后再转而讨论如何提高编译器和处理器对并行的开发能力。

ILP大体有两种不同开发方法:

1. 依靠硬件来帮助动态发现和开发并行；
2. 依靠软件技术在编译时静态发现并行；

什么是指令级并行

这一章的所有技术都是开发指令间的并行。基本块（一段顺序执行代码，除入口外没有其他转入分支，除出口外没有其他转出分支）中可以利用的并行数非常有限。对于典型的MIPS程序，平均动态分支频率通常介于15%到25%之间，也就是说在一对分支之间会执行3~6条指令。由于这些指令可能相互依赖，所以在基本块中可以开发的重叠数量可能要少于基本块的平均大小。为了真正地提高性能，我们必须跨越多个基本块开发ILP。提高ILP的最简单、最常见方法是在循环的各次迭代之间开发并行。这种并行经常被称作循环级并行。

下面是一个简单的循环示例，它对两个分别有1000个元素的数组求和，完全可以并行实现：

for (i=0; i<=999; =i+1)
    x[i] = x[i] + y[i];

这个循环的每次迭代都可以与任意其他迭代重叠，当然，在每次循环迭代中进行重叠的机会不大，甚至没有这种机会。我们将研究大量将这种循环级并行转换为指令级并行的技术。这些技术的工作方式基本上都是采用编译器静态展开循环或者利用硬件动态展开循环。开发循环级并行的一种重要替代方法是使用向量处理器和图形处理器中的SIMD。SIMD指令在开发数据级并行时，并行处理少量到中等数量的数据项。而向量指令在开发数据级并行时，则通过使用并行执行单元和深流水线，并行处理许多数据项。例如，上述代码序列的简单形式在每次迭代中需要7条指令（2次载入、1次求和、1次存储、2次地址更新和1次分支），总共7000条指令，而在每条指令可以处理4个数据项的某种SIMD体系结构中，只需要四分之一的指令就能完成任务。在一些向量处理器中，这个序列可能只需要4条指令：2条指令用于从存储器中载入向量x和y, 1条指令用于对两个向量求和，还有1条指令用于将结果向量存回存储器。当然，这些指令可以是流水化的，其延迟相对较长，但可以对这些延迟进行重叠。

数据相关与冒险

要确定一个程序中可以存在多少并行以及如何开发并行，判断指令之间的相互依赖性是至关重要的。具体来说，为了开发指令级并行，我们必须判断哪些指令可以并行执行。如果两条指令是并行的，只要流水线有足够资源（因而也就不存在任何结构性冒险），就可以在一个任意深度的流水线中同时执行它们，不会导致任何停顿。如果两条指令是相关的，它们就不是并行的，尽管它们通常可以部分重叠，但必须按顺序执行。这两种情景的关键在于判断一条指令是否依赖于另一指令。

数据相关

共有3种不同类型的相关:数据相关（也称为真数据相关）、名称相关和控制相关。如果以下任一条件成立，则说指令j数据相关于指令i：

• 指令i生成的结果可能会被指令j用到；
• 指令j数据相关于指令k，指令k数据相关于指令i。

第二个条件就是说：如果两条指令之间存在第一类型的相关链，那么这两条指令也是相关的。这种相关链可以很长，贯穿整个程序。注意，单条指令内部的相关性（比如ADDD RI, R1, R1）不认为是相关。例如，考虑以下MIPS代码序列，它用寄存器F2中的一个标量来递增存储器中的一个值向量（从0(R1)开始，最后一个元素是B(R2)）。

Loop:   L.D F0,0(R1)     ;F0=数组元素
        ADD.D F4,F0,F2   ;加上F2中的标量
        S.D F4,0(R1)     ;存储结果
        DADDUI R1,R1,#-8 ;使指针递减8个字节
        BNE R1,R2 ,LOOP  ;R1!=R2 时跳转

这一代码序列中的数据相关涉及两个浮点数据:

Loop:   L.D F0,0(R1)     ;F0=数组元素
        ADD.D F4,F0,F2   ;加上F2中的标量
        S.D F4,0(R1)     ;存储结果

和整型数据：

DADDIU R1,R1,#-8 ;使指针递减 8个字节
                 ;(每个DW)
BNE R1 ,R2 ,Loop ;R1!=R2 时跳转

在以上两个相关序列中，如箭头所示，每条指令都依赖于上一条指令。这段代码及以下示例中给出的箭头表示为了正确执行必须保持的顺序。位于箭头起始处的指令必须位于箭头所指指令之前。如果两条指令是数据相关的，那它们必须按顺序执行，不能同时执行或不能完全重叠执行。这种相关意味着两条指令之间可能存在由一个或多个数据冒险构成的链。同时执行这些指令会导致具有流水线互锁（而且流水线深度大于指令间距离，以周期为单位）的处理器检测冒险和停顿，从而降低或消除重叠。在依靠编译器调度、没有互锁的处理器中，编译器在调度相关指令时不能使它们完全重叠，这样会使程序无法正常执行。指令序列中存在数据相关，反映出生成该指令序列的源代码中存在数据相关。原数据相关的影响一定会保留下来。

相关是程序的一种属性。某种给定相关是否会导致检测到实际冒险，这一冒险又是否会实际导致停顿，这都属于流水线结构的性质。这一区别对于理解如何开发指令级并行至关重要。数据相关传递了三点信息：

1. 冒险的可能性
2. 计算结果必须遵循的顺序
3. 可开发并行度的上限

由于数据相关可能会限制我们能够开发的指令级并行数目，所以本章的一个重点就是如何克服这些局限性。可以采用两种不同方法来克服相关性:

• 保护相关性但避免冒险；
• 通过转换代码来消除相关性。

对代码进行调度是在不修改相关性的情况下避免冒险的主要方法，这种调度既可以由编译器完成，也可以由硬件完成。数据值既可以通过寄存器也可以通过存储器位置在指令之间传送。当数据传送在寄存器中发生时，由于指令中的寄存器名字是固定的，所以相关性的检测很简单，当然，如果存在分支干扰以及为了保持正确性而迫使编译器或硬件变得保守，那可能会变得复杂些。当数据在存储器位置之间流动时，由于两个看起来不同的地址可能引用同一位置，所以其相关性更难以检测，比如100(R4)和20(R6)可能是同一个存储器地址。

此外，载入指令或存储指令的实际地址可能会在每次执行时发生变化（所以20(R4)和20(R4)可能是不一样的），这使相关性的检测进一步复杂化。本章研究采用硬件来检测那些涉及存储器位置的数据相关，但我们将会看到，这些技术也有局限性。用于检测这些相关的编译器技术是揭示循环级别并行的关键所在。

名称相关

第二种相关称为名称相关。当两条指令使用相同的寄存器或存储器位置（称为名称），但与该名称相关的指令之间并没有数据流动时，就会发生名称相关。在指令i和指令j（按照程序顺序，指令i位于指令j之前）之间存在两种类型的名称相关。

(1)当指令j对指令i读取的寄存器或存储器位置执行写操作时就会在指令i和指令j之间发生反相关。为了确保i能读取到正确取值，必须保持原来的顺序。在前面的例子中，S.D和DADDIU之间存在关于寄存器R1的反相关。

(2)当指令i和指令j对同一个寄存器或存储器位置执行写操作时，发生输出相关。为了确保最后写入的值与指令j相对应，必须保持指令之间的排序。

由于没有在指令之间传递值，所以反相关和输出相关都是名称相关，与真数据相关相对。因为名称相关不是真正的相关，因此，如果改变这些指令中使用的名称（寄存器号或存储器位置），使这些指令不再冲突，那名称相关中涉及的指令就可以同时执行，或者重新排序。对于寄存器操作数，这一重命名操作更容易实现，这种操作称作寄存器重命名。寄存器重命名既可以由编译器静态完成，也可以由硬件动态完成。在介绍因分支导致的相关性之前，先让我们来看看相关与流水线数据冒险之间的关系。

数据冒险

只要指令间存在名称相关或数据相关，而且它们非常接近，足以使执行期间的重叠改变对相关操作数的访问顺序，那就会存在冒险。由于存在相关，必须保持程序顺序，也就是由原来的源程序决定的指令执行顺序。软、硬件技术的目的都是尽量开发并行方式，仅在程序顺序会影响程序输出时才保持程序顺序。检测和避免冒险可以确保不会打乱必要的程序顺序。根据指令中读、写访问的顺序，可以将数据冒险分为三类。根据惯例，一般按照流水线必须保持的程序顺序为这些冒险命名。考虑两条指令i和j，其中i根据程序顺序排在j的前面。可能出现的数据冒险为:

• RAW（写后读）——j试图在i写入一个源位置之前读取它，所以j会错误地获得i旧值。这一冒险是最常见的类型，与真数据相关相对应。为了确保j会收到来自i的值，必须保持程序顺序。
• WAW（写后写）——j试图在i写一个操作数之前写该操作数。这些写操作最终将以错误顺序执行，最后留在目标位置的是由i写入的值，而不是由j写入的值。这种冒险与输出相关相对应。只有允许在多个流水级进行写操作的流水线中，或者在前一指令停顿时允许后一指令继续执行的流水线中，才会存在WAW冒险。
• WAR（读后写）——j尝试在i读取一个目标位置之前写入该位置，所以i会错误地获取新值。这一冒险源于反相关（或名称相关）。在大多数静态发射流水线中（即使是较深的流水线或者浮点流水线），由于所有读取操作都较早进行，所有写操作都要晚一些，所以不会发生WAR冒险。如果有一些指令在指令流水线中提前写出结果，而其他指令在流水线的后期读取一个源位置，或者在对指令进行重新排序时，就会发生WAR冒险，在本章后面将对此进行讨论。注意，RAR（读后读）情况不是冒险。

控制相关

最后一种相关是控制相关。控制相关决定了指令i相对于分支指令的顺序，使指令i按正确程序顺序执行，而且只会在应当执行时执行。除了程序中第一基本块中的指令之外，其他所有指令都与某组分支存在控制相关，一般来说，为了保持程序顺序，必须保留这些控制相关。控制相关的最简单示例就是分支中if语句的then部分中的语句。例如，在以下代码段中:

if p1 {
    S1;
};
if p2 {
    S2;
}

S1与p1控制相关，S2与p2控制相关，但与p1没有控制相关。

一般来说，控制相关会施加下述两条约束条件。

• 如果一条指令与一个分支控制相关，那就不能把这个指令移到这个分支之前，使它的执行不再受控于这个分支。例如，不能把if语句then部分中的一条指令拿出来，移到这个if语句的前面。
• 如果一条指令与一个分支没有控制相关，那就不能把这个指令移到这个分支之后，使其执行受控于这个分支。例如，不能将if之前的一个语句移到它的then部分。

在不影响程序正确性的情况下，我们可能希望执行一些还不应当执行的指令，从而会违犯控制相关。因此，控制相关并不是一个必须保持的关键特性。有两个特性对程序正确性是至关重要的，即异常行为和数据流，通常保持数据相关与控制相关也就保护了这两种特性。保护异步行为意味着对指令执行顺序的任何改变都不能改变程序中激发异常的方式。通常会放松这一约束条件，要求改变指令的执行顺序时不得导致程序中生成任何新异常。下面的简单示例说明维护控制相关和数据相关是如何防止出现这类情景的。考虑以下代码序列:

DADDU R2, R3, R4
BEQZ  R2,L1
LW    R1 ,0(R2)
L1:

在这个例子中，可以很容易地看出如果不维护涉及R2的数据相关，就会改变程序的结果。还有一个事实没有那么明显：如果我们忽略控制相关，将载入指令移到分支之前，这个载入指令可能会导致存储器保护异常。注意，没有数据相关禁止交换BEQZ和LN；这只是控制相关。要允许调整这些指令的顺序（而且仍然保持数据相关），我们可能希望在执行这一分支操作时忽略此异常。

通过维护数据相关和控制相关来保护的第二个特性是数据流。数据流是指数据值在生成结果成和使用结果的指令之间进行的实际流动。分支允许一条给定指令从多个不同地方获取源数据，从而使数据流变为动态的。换种说法，由于一条指令可能会与之前的多条指令存在数据相关性，所以仅保持数据相关是不够的。一条指令的数据值究竟由之前哪条指令提供，是由程序顺序决定的。而程序顺序是通过维护控制相关来保证的。

例如，考虑以下代码段:

    DADDU R1,R2,R3
    BEQZ  R4,L
    DSUBU R1,R5,R6
L:  
    OR    R7,R1,R8

在这个例子中，OR指令使用的R1值取决于是否进行了分支转移。单靠数据相关不足以保证正确性。OR指令数据相关于DADDU和DSUBU指令，但仅保持这一顺序 并不足以保证能够正确执行。

在执行这些指令时，还必须保持数据流：如果没有进行分支转移，那么由DSUBU计算的R1值应当由OR使用；如果进行了分支转移，由DADDU计算的R1值则应当由OR使用。通过保持分支中OR的控制相关，就能防止非法修改数据流。出于类似原因，DSUBU指令也不能移到分支之前。推测不但可以帮助解决异常问题，还能在仍然保持数据流的同时降低控制相关的影响。

有些情况下，我们可以断定违犯控制相关并不会影响异常行为或数据流。考虑以下代码序列：

    DADDU R1,R2,R3
    BEQZ  R12,skip
    DSUBU R4, R5,R6.
    DADDU R5,R4,R9
skip:
    OR R7 ,R8,R9

假定我们知道DSUBU指令的目标寄存器(R4)在标有skip的指令之后不再使用。（一个值是否会被后续指令使用，这一特性被称为活性。）如果R4不会再被使用，由于它在skip之后的代码部分变为死亡（不再具备活性），那么就在这个分支之前改变R4的值并不会影响数据流。因此，如果R4已经死亡，而且现有DSUBU指令不会生成异常（处理器会从某些指令处重启同一过程，这些指令除外），那就可以把DSUBU指令移到分支之前，数据流不会受这一改变的影响。

如果进行了分支转移，将会执行DSUBU指令，之后不再有用，但这样仍然不会影响程序结果。由于编译器在对分支结果进行猜测，所以这种类型的代码调度也是一种推测形式，通常称为软件推测；在这个例子中，编译器推测通常不会进行分支转移。

对导致控制停顿的控制冒险进行检测，可以保持控制相关。控制停顿可以通过各种软硬件技术加以消除或减少。

揭示ILP的基本编译器技术

这一节研究一些简单的编译器技术，可以用来提高处理器开发ILP的能力。这些技术对于使用静态发射或静态调度的处理器非常重要。有了这一编译器技术，稍后将会研究那些采用静态发射的处理器的设计与性能。

基本流水线调度和循环展开

为使流水线保持满载，必须找出可以在流水线中重叠的不相关指令序列，充分开发指令并行。为了避免流水线停顿，必须将相关指令与源指令的执行隔开一定的时间周期，这一间隔应当等于源指令的流水线延迟。编译器执行这种调度的能力既依赖于程序中可用ILP的数目，也依赖于流水线中功能单元的延迟。表3-2给出了在本章采用的FP单元延迟，如果偶尔采用不同延迟，会另行明确说明。假定采用一个标准的5级整数流水线，所以分支的延迟为一个时钟周期。假定这些功能单元被完全流水化或复制，所以在每个时钟周期可以发射任何一个类型的指令，不存在结构冒险。

最后一列是为了避免停顿而需要插入的时钟周期数。这些数字与我们在FP单元上看到的平均延迟类似。由于可以旁路载入指令的结果，不会使存储指令停顿，所以浮点载入指令对载入指令的延迟为0。我们还假定整数载入延迟为1，整数ALU操作延迟为0。

在这一小节，我们将研究编译器如何通过转换循环来提高可用ILP的数目。我们的讨论将就以下代码段展开，它将对一个标量和一个向量求和：

for (i = 999; i >= 0; i = i - 1)
    x[1] = x[i] + s;

注意，这个循环的每个迭代体都是相互独立的，从而可以看出这个循环是并行的。首先来看这个循环的性能，说明如何利用并行来提高一个MIPS流水线的性能（采用以上所示的延迟值）。第一步是将以上代码段转换为MIPS汇编语言。在以下代码段中，R1 最初是数组元素的最高地址，F2 包含标量值s。寄存器R2的值预先计算得出，使8(R2)成为最后一个进行运算的元素的地址。

这段简单的MIPS代码应当类似如下所示(未针对流水线进行调度):

Loop:   L.D    F0,0(R1)  ;F0=数组元素
        ADD.D  F4,F0,F2  ;加上F2中的标量
        S. D   F4,0(R1)  ;存储结果
        DADDUI RI,R1,#-8 ;使指针逐减8个字节
                         ;(每个DW)
        BNE    R1,R2,Loop;R1!=R2时跳转

首先来看看在针对MIPS的简单流水线上调度这个循环时的执行情况。

写出在进行调度与不进行调度的情况下，这个循环在MIPS上的执行过程，包括所有停顿或空闲时钟周期。调度时要考虑浮点运算产生的延迟，但忽略延迟分支。

在不进行任何调度时，循环的执行过程如下，共花费9个周期：

                       发射的时钟周期
Loop:   L. D   F0,0(RI)      1
        停顿                 2
        ADD.D  F4,F0,F2      3
        停顿
        停顿
        S,D    F4,0(R1)      6
        DADDUI R1,R1,#-8     7
        停顿                 8
        BNE    R1. ,R2,Loop  9

我们可以调度这个循环，使其只有2次停顿，将花费时间缩短至7个周期:

Loop:   L.D      F0,0(R1)
        DADDUI   R1,R1.#-8
        ADD.D    F4,F0,F2
        停顿
        停顿
        S.D      F4,8(R1)
        BNE      R1,R2, Loop

ADD.D之后的停顿是供S.D.使用的。

在上面这个例子中，每7个时钟周期完成一次循环迭代，并存回一个数组元素，但对数组元索进行的实际运算仅占用这7个时钟周期中的3个（载入、求和与存储）。其余4个时钟周期包括循环开销（DADDUI和BNE）和2次停顿。为了消除这4个时钟周期，需要使循环体中的运算指令数多于开销指令数。

要提高运算指令相对于分支和开销指令的数目，一种简单的方案是循环展开。展开就是将循环体复制多次，调整循环的终止代码。

循环展开还可用于提高调度效率。由于它消除了分支，因此可以将来自不同迭代的指令放在一起调度。在这个例子中，我们通过在循环体内创建更多的独立指令来消除数据使用停顿。如果在展开循环时只是简单地复制这些指令，最后使用的都是同一组寄存器，所以可能会妨碍对循环的有效调度。因此，我们希望为每次迭代使用不同寄存器，这就需要增加寄存器的数目。

展开以上循环，使其包含循环体的4个副本，假定R1-R2（即数组的大小）最初是32的倍数，也就是说循环迭代的数目是4的倍数。消除任何明显的冗余计算，不要重复使用任何寄存器。

合并DADDUI指令，删除在展开期间重复的非必需BNE运算，得到的结果如下。注意，现在必须对R2进行置位，使32（R2）成为后4个元素的起始地址。

Loop:   L.D      F0,0(R1)
        ADD.D    F4,F0,F2
        S.D      F4,0(R1)    ;删除DADDUI和BNE
        L.D      F6,-8(R1)
        ADD.D    F8,F6,F2
        S.D      F8,-8(R1)   ;删除DADDUI和BNE 
        L.D      F10,-16(R1) 
        ADD.D    F12,F10,F2 
        S.D      F12,-16(R1) ;删除DADDUI和BNE
        L.D      F14,-24(R1}
        ADD.D    F16,F14,F2
        S.D      F16,-24(R1)
        DADDUI   R1,R1,#-32
        BNE      R1,R2, LOOP

我们省掉了三次分支转移和对R1的三次递减。并对载入和存储指令的地址进行了补偿，以允许合并针对R1的DADDUI指令。这一优化看起来似乎微不足道，但实际并非如此；它需要进行符号替换和化简。符号替换和化简将重新整理表达式，以合并其中的常量，比如表达式((i+ 1)+ 1)可以重写为(i+(1 + 1))，然后化简为(i+2)。这种优化方式消除了相关计算。如果没有调度，展开循环中的每个操作后面都会跟有一个相关操作，从而导致停顿。这个循环将运行27个时钟周期（每个LD有1次停顿，每个ADDD 2、DADDUI 1，加上14个指令发射周期），或者说在4个元素的每个元素上平均花费6.75个时钟周期，但通过调度可以显著提高其性能。循环展开通常是在编译过程的早期完成的，所以优化器可以发现并消除冗余运算。

在实际程序中，人们通常不知道循环的上限。假定此上限为n，我们希望展开循环，制作循环体的k个副本。我们生成的是一对连续循环，而不是单个展开后的循环。第一个循环执行(n mod k)次，其主体就是原来的循环。第二个循环是由外层循环包围的展开循环，迭代(n/k)次。当n值较大时，大多数执行时间都花费在未展开的循环体上。在前面的例子中，通过展开消除了开销指令，尽管这样会显著增大代码规模，但却可以提高这一循环的性能。如果针对先前介绍的流水线来调度展开后的循环，它的执行情况又会如何呢?

针对具有表3-2 所示延迟的流水线，调度前面例子中展开后的循环，写出其执行情况。

Loop:   L.D         F0,0(R1)
        L.D         F6,-8{R1)
        L.D         F10,-16(R1}
        L.D         F14,-24{R1)
        ADD.D       F4,F0,F2
        ADD.D       F8,F6,F2
        ADD.D       F12,F10,F2
        ADD.D       F16,F14,F2
        S.D         F4,0(R1)
        S.D         F8,-8(R1)
        DADDUI      R1,R1,#-32
        S.D         F12,16(R1)  
        S.D         F16,8(R1)
        BNE         R1,R2, Loop

展开后循环的执行时间已经缩减到总共14个时钟周期，或者说每个元素需要3.5个时钟周期，而在未进行任何展开或调度之前为每个元素9个时钟周期，进行调度但未展开时为7个周期。对展开循环进行调度所获得的收益甚至还会大于对原循环进行调度的收益。之所以会这样，是因为展开后的循环暴露了更多可以进行调度的计算，从而可以将停顿时间减至最低；上述代码中就没有任何停顿。要以这种方式调度循环，必须意识到载入指令和存储指令是不相关的，可以交换位置。

循环展开与调度小结

在本章中，我们将会研究各种可以利用指令级并行的硬件与软件技术，以充分发挥处理器中各功能单元的潜力。大多数此类技术的关键在于判断何时能够改变指令顺序以及如何改变。我们的例子中进行了许多此类改变，对于人类来说，可以很容易地判断出是可以进行此类改变的。而在实践中，这一过程必须采用系统方式，由编译器或硬件来完成。为了获得最终展开后的代码，必须进行如下决策和变换。

• 确认循环迭代不相关（循环维护代码除外），判定展开循环是有用的。
• 使用不同寄存器，以避免由于不同运算使用相同寄存器而施加的非必要约束（比如，名称相关）。
• 去除多余的测试和分支指令，并调整循环终止与迭代代码。
• 观察不同迭代中的载入与存储指令互不相关，判定展开后的循环中的载入和存储指令可以交换位置。这一变换需要分析存储器地址，查明它们没有引用同一地址。
• 对代码进行调度，保留任何必要相关，以得到与原代码相同的结果。

要进行所有这些变换，最关键的要求就是要理解指令之间的相关依赖关系，而且要知道在这些给定关系下如何改变指令或调整指令的顺序。

有3种不同的效果会限制循环展开带来的好处：

1. 每次展开操作分摊的开销数目降低，
2. 代码规模限制，
3. 编译器限制。

我们首先考虑循环开销问题。如果将循环展开4次，所生成的指令并行足以使循环调度消除所有停顿周期。事实上，在14个时钟周期中，只有2个周期是循环开销：维护索引值的DADDUI和终止循环的BNE。如果将循环展开8次，这一开销将从每次原迭代的1/2周期降低到1/4。对展开的第二个限制是所生成代码规模的增长。对于较大规模的循环，如果代码规模的增长会导致指令缓存缺失率的上升，那就要特别加以关注。还有一个因素通常要比代码大小更为重要，那就是由于大量进行展开和调试而造成寄存器数量不足。因为在大段代码中进行指令调度而产生的这一副作用被称为寄存器紧缺。它的出现是因为在为了提高ILP而调试代码时，导致存活值的数目增加。在大量进行指令调度之后，可能无法将所有存活值都分配到寄存器中。尽管转换后的代码在理论上可以提高运行速度，但由于它会造成寄存器短缺，所以可能会损失部分乃至全部收益。在没有展开循环时，分支就足以限制调度的大量使用，所以寄存器紧缺几乎不会成为问题。但是，循环展开与大量调度的综合应用却可能导致这一问题。 在多发射处理器中需要公开更多可以重叠执行的独立指令序列，上述问题可能变得尤其困难。一般来说， 高级复杂转换的应用已经导致现代编译器的复杂度大幅增加，而在生成具体代码之前，很难衡量这种应用带来的潜在改进。

直行代码段可以进行有效的调度，而循环展开是一种增大直行代码段规模的简单有效方法。这种转换在各种处理器上都非常有用，从我们前面已经研究过的简单流水线，到多发射超标量，再到本章后面要研究的VLIW。

用高级分支预测降低分支成本

由于需要通过分支冒险和停顿来实施控制相关，所以分支会伤害流水线性能。循环展开是降低分支冒险的一种方法，我们还可以通过预测分支的行为方式来降低分支的性能损失。我们将研究一些简单的分支预测器，它们既可能依赖于编译时信息，也可能依赖于在隔离状态下观测到的分支动态行为。随着所用指令数目的增大，更准确的分支预测也变得越来越重要。在本节，我们将研究一些提高动态预测准确度的技术。

相关分支预测

2位预测器方案仅使用单个分支的最近行为来预测该分支的未来行为。如果我们同时还能查看其他分支的最近行为，而不是仅查看要预测的分支，那就有可能提高预测准确度。考虑eqntott基准测试中的一小段代码，这个基准测试是早期SPEC基准测试套件的一个成员，用来显示特别糟糕的分支预测行为:

if (aa==2)
    aa=0;
if (bb==2)
    bb=0;
if (aa !=bb){

下面是通常为这一代码段生成的MIPS代码，假定aa和bb分别被赋值给R1和R2:

        DADDIU    R3,R1,#-2
        BNEZ      R3,L1         ;branch b1 (aa!=2)
        DADD      R1,RO,R0      ;aa=0
L1:     DADDIU    R3,R2,#-2    
        BNEZ      R3,L2         ;branch b2 (bb!=2)
        DADD      R2,RO,RO      ;bb=0
L2:     DSUBU     R3,R1,R2      ;R3=aa-bb
        BEQZ      R3,L          ;branch b3 (aa==bb)

我们将这些分支标记为b1、b2和b3。从中可以看出很重要的一点：分支b3的行为与分支b1和b2的行为有关。显然，如果分支b1和b2都未执行转移（即其条件均为真，且aa和bb均被赋值为0），aa 和bb明显相等，所以会进行b3分支转移。如果预测器仅利用一个分支的行为来预测分支结果，那显然不会捕获到这一行为。利用其他分支行为来进行预测的分支预测器称为相关预测或两级预测器。现有相关预测器增加最近分支的行为信息，来决定如何预测一个给定分支。例如，（1,2）预测器在预测一个特定分支时，利用最近一个分支的行为从一对2位分支预测器中进行选择。在一般情况下，（m,n）预测器利用最近m个分支的行为从2^m个分支预测器中进行选择，其中每个预测器都是单个分支的n位预测器。这种相关分支预测器的吸引力在于它的预测率可以高于2位方案，而需要添加的硬件很少。

硬件的这种简易性源自一个简单的观察事实：最近m个分支的全局历史可以记录在m位移位的寄存器中，其中每一位记录是否执行了该分支转移。将分支地址的低位与m位全局历史串联在一起，就可以对分支预测缓冲区进行寻址。例如，在一个共有64项的（2,2）缓冲区中，分支的低4位地址（字地址）和2个全局位（表示最近执行的两个分支的行为）构成一个6位索引，可用来对64个计数器进行寻址。

与标准的2位方案相比，相关分支预测器的性能可以提高多少呢?为了进行公平对比，进行比较的预测器必须使用相同数目的状态位。一个(m,n)预测器的位数为:

2^m * n *由分支地址选中的预测项数目

没有全局历史的2位预测器就是(0,2)预测器。

在具有4K项的(0,2)分支预测器中有多少位?在具有同样位数的(2,2)预测器中有多少项?

具有4K项的预测器拥有:

2^0 * 2 * 4K = 8K位

在预测缓冲区中共有8K位的(2,2)预测器中有多少由分支选中的项呢?我们知道：

2^2 * 2 * 由分支选中的预测项数=8K

因此，由分支选中的预测项数=1K。

图3-1对比了前面具有4K项的(0,2)预测器与具有1K项的(2,2)预测器的错误预测率。可以看出，这种相关预测器的性能不但优于具有相同状态位数的简单2位预测器，还经常会优于具有无限项数的2位预测器。

2位预测器的对比。第一个是4096位的非相关预测器，然后是具有无限数目的非相关2位预测器，和一个具有2位全局历史和总共1024项的2位预测器。尽管这些数据是从SPEC的较早版本获取的，但最近SPEC基准测试的数据也显示了类似的准确度差异。

竞赛预测器: 局部预测器与全局预测器的自适应联合

采用相关分支预测器主是要因为观察到：仅使用局部信息的标准2位预测器无法预测某些重要分支，而通过增加全局信息就可以提升性能。竞赛预测器更进一步，采用了多个预测器，通常是一个基于全局信息的预测器和一个基于局部信息的预测器，用选择器将它们结合起来。竞赛预测器既可以以中等规模的预测位（8K~32K位）实现更好的预测准确度，还可以更有效地利用超大量预测位。现有竞赛预测器为每个分支使用一个2位饱和预测器，根据哪种预测器（局部、全局，甚至包括两者的组合方式）在最近的预测中最为有效，从两个不同预测器中进行选择。在简单的2位预测器中，饱和计数器要在两次预测错误之后才会改变优选预测器的身份。

竞赛预测器的优势在于它能够为特定分支选择正确的预测器，这一点对于整数基准测试尤为重要。对于SPEC整数基准测试，典型竞赛预测器为其选择全局预测器的概率大约为40%，而对于SPECFP基准测试，则少于15%。除了在竞赛预测器方面走在前列的Alpha处理器之外，最近的AMD处理器，包括Opteron和Phenom，都已经采用了竞赛类型的预测器。图3-2以SPEC89为基准测试，研究三种不同预测器：一个局部2位预测器、一个相关预测器和竞赛预测器，在不同位数时的性能。和我们前面曾经看到的一样，局部预测器的预测性能改进不会超出一定的范围。相关预测器的改进非常突出，竞赛预测器的性能稍好一些。对于SPEC的最新版本，其结果是类似的，但需要采用稍大些的预测器规模才能达到渐趋一致的行为。

图3-2在总位数升高时，3种不同预测器运行SPEC89的错误预测率。这些预测器包括：一个局部2位预测器；一个相关预测器；针对图中每一点的全局和局部信息采用了结构优化；一个竞赛预测器。尽管这些数据是从SPEC的较早版本获取的，但最近SPEC基准测试的数据也显示了类似行为，当预测器规模稍大时，可能趋于一个渐近值

局部预测器包括一个两级预测器。顶级是一个局部历史表，包括1024个10位项；每个10位项对应这一项最近10个分支输出。即，如果这个分支被选中10次或更多次，那么这个局部历史表中的相应项都是1。如果这个分支被交替选中和未选中，那么历史项中则包括交替的0和1。这个10位历史信息最多可以发现和预测10个分支。局部历史表的选定项用来对一个拥有1K项的表进行索引，这个表由3位饱和计数器组成，可以提供局部预测。这种组合共使用29K位，可以提高分支预测的准确度。

Intel Core i7分支预测器

关于Core i7的分支预测器，Intel 只发布了非常有限的信息，这种预测器是以Core Duo芯片中使用的较早预测器为基础。i7 使用了一个两级预测器，它的第一级预测器较小, 设计用来满足周期约束条件：每个时钟周期预测一个分支，还有一个较大的二级预测器作为备份。每个预测器都组合了3个不同预测器：(1)简单的两位预测器；(2)全局历史预测器，类似于我们刚刚看到的预测器；(3)循环退出预测器。对于一个被检测为循环分支的分支，循环退出预测器使用计数器来预测被选中分支的确切数目（也就是循环迭代的数目）。对于每个分支，通过跟踪每种预测的准确度从3个预测器中选择最佳预测，就像一个竞赛预测器。除了这一多级主预测器之外，还有一个独立单元为间接分支预测目标地址，还使用了栈来预测返回地址。

和在其他情景中一样，推测在评估预测器方面也导致了一些难题，这是因为对一个分支的错误预测很容易导致提取和错误预测另一个分支。为了使事情变得简单一些，我们看一下错误预测数占成功完成分支数（这些分支不是推测错误导致的结果）的百分比。图3-3显示了19个SPECCPU 2006基准测试的数据。这些基准测试明显大于SPEC89或SPEC2000，其结果是：即使更精心地组合应用预测器，其错误预测率也只是稍大于图3-2中所示数据。由于分支预测错误会导致推测效率低下，所以它会导致一些无效工作，在本章后面将会了解到这一点。

图3-3 19 个SPECCPU2006基准测试错误预测数占成功完成分支数的比例，整数基准测试的平均值稍高于FP（4%对3%）。更重要的是，某些基准测试的错误率高出很多

用动态调度克服数据冒险

除非是流水线中的已有指令与要提取的指令之间存在数据相关，而且无法通过旁路或转发来隐藏这一数据相关，否则，简单的静态调度流水线就会提取一条指令并发射出去。（转发逻辑可以减少实际流水线延迟，所以某些特定的相关不会导致冒险）如果存在不能隐藏的数据相关，那些冒险检测软件会从使用该结果的指令开始，将流水线置于停顿状态。在清除这一相关之前，不会提取和发射新的指令。

本节将研究动态调度，在这种调度方式中，硬件会重新安排指令的执行顺序以减少停顿，并同时保持数据流和异常行为。动态调度有几个优点。

• 第一，它允许针对一种流水线编译的代码在不同流水线上高效执行，不需要在使用不同微体系结构时重新进行编译，并拥有多个二进制文件。
• 第二，在某些情况下，在编译代码时还不能知道相关性，利用动态调度可以处理某些此类情况；比如，这些相关可能涉及存储器引用或者与数据有关的分支，或者，它们可能源自使用动态链接或动态分发的现代编程环境。
• 第三，也可能是最重要的一个优点，它允许处理器容忍些预料之外的延迟，比如缓存缺失，它可以在等待解决缺失问题时执行其他代码。

在3.6节，我们将研究以动态调度为基础的硬件推测，这一技术还有更多性能方面的优势。我们将会看到，动态调度的好处是以硬件复杂度的显著提高为代价的。尽管动态调度的处理器不能改变数据流，但它会在存在相关性时尽力避免停顿。相反，由编译器调度的静态流水线也会尽力将停顿时间降至最低，具体方法是隔离相关指令，使它们不会导致冒险。当然，对于那些本来准备在采用动态调度流水线的处理器上运行的代码，也可以使用编译器流水线调度。

动态调度: 思想

简单流水线技术的一个主要限制是它们使用循序指令发射与执行：指令按程序顺序发射，如果一条指令停顿在流水线中，后续指令都不能继续进行。因此，如果流水线中两条相距很近的指令存在相关性，就会导致冒险和停顿。如果存在多个功能单元，这些单元也可能处于空闲状态。如果指令j依赖于长时间运行的指令i（当前正在流水线中执行），那么j之后的所有指令都必须停顿，直到i完成、j可以执行为止。例如，考虑以下代码:

DIV.D     F0, F2,F4
ADD.D     F10,F0,F8
SUB.D     F12,F8,F14

由于ADD.D对DIV.D的相关性会导致流水线停顿，所以SUB.D指令不能执行；但是，SUB.D与流水线中的任何指令都没有数据相关性。这一冒险会对性能造成限制，如果不需要以程序顺序来执行指令，就可以消除这一限制。在经典的五级流水线中，会在指令译码（ID）期间检查结构冒险和数据冒险：当一个指令可以无冒险执行时，知道所有数据冒险都已经解决，从ID将其发射出去。

为了能够开始执行上面例子中的SUB.D，必须将发射过程分为两个部分：检查所有结构冒险和等待数据冒险的消失。因此，我们仍然使用循序指令发射（即，按程序顺序发射指令），但我们希望一条指令能够在其数据操作数可用时立即开始执行。这样一种流水线实际是乱序执行，也就意味着乱序完成。

乱序执行就可能导致WAR和WAW冒险，在这个五级整数流水线及其循序浮点流水线的逻辑扩展中不存在这些冒险。考虑以下MIPS浮点代码序列：

DIV.D    F0,F2,F4
ADD.D    F6,F0,F8
SUB.D    F8,F10,F14
MUL.D    F6,F10,F8

在ADD.D和SUB.D之间存在反相关，如果流水线在ADD.D之前执行SUB.D（ADD.D在等待DIV.D），将会违犯反相关，产生WAR冒险。与此类似，为了避免违犯输出相关，比如由MUL.D写入F6，就必须处理WAW冒险。后面将会看到，利用寄存器重命名可以避免这些冒险。

乱序完成还会使异常处理变得复杂。采用乱序完成的动态调度必须保持异常行为，使那些在严格按照程序顺序执行程序时会发生的异常仍然会实际发生，也不会发生其他异常。动态调度处理器会推迟发布相关异常的发布，一直等到处理器知道该指令就是接下来要完成的指令为止，通过这一方式来保持异常行为。

尽管异常行为必须保持，但动态调度处理器可能生成一些非精确异常。如果在发生异常时，处理器的状态与严格按照程序顺序执行指令时的状态不完全一致，那就说这一异常是非精确的。非精确异常可以因为以下两种可能性而发生。

1. 流水线在执行导致异常的指令时，可能已经完成了按照程序顺序排在这一指令之后的指令。
2. 流水线在执行导致异常的指令时，可能还没有完成按照程序顺序排在这一指令之前的指令。

非精确异常增大了在异常之后重新开始执行的难度。我们在这一节不会解决这些问题，而是讨论一种解决方案，能够在具有推测功能的处理器环境中提供精确异常。对于浮点异常，已经采用了其他解决方案。

为了能够进行乱序执行，我们将五级简单流水线的ID流水级大体分为以下两个阶段。

1. 发射：译码指令，检查结构性冒险。
2. 读操作数：直等到没有数据冒险，然后读取操作数。

指令提取阶段位于发射阶段之前，既可以把指令放到指令寄存器中，也可能放到一个待完成指令队列中；然后从寄存器或队列发射这些指令。执行阶段跟在读操作数阶段之后，这一点和五级流水线中一样。执行过程可能需要多个周期，具体数目取决于所执行的操作。

我们区分一个指令开始执行和完成执行的时刻，在这两个时刻之间，指令处于执行过程中。我们的流水线允许同时执行多条指令，没有这一功能，就会失去动态调度的主要优势。要同时执行多条执行，需要有多个功能单元、流水化功能单元，或者同时需要这两者。由于这两种功能（流水化功能单元和多个功能单元）在流水线控制方面大体相当，所以我们假定处理器拥有多个功能单元。

在动态调度流水线中，所有指令都循序经历发射阶段（循序发射）；但是，它们可能在第二阶段（读操作数阶段）停顿或者相互旁路，从而进行乱序执行状态。记分板技术允许在有足够资源和没有数据相关时乱序执行指令。这里重点介绍一种名为Tomasulo算法的更高级技术。它们之间的主要区别于Tomasulo算法通过对寄存器进行有效动态重命名来处理反相关和输出相关。

此外，还可以对Tomasulo算法进行扩展，用来处理推测，这种技术通过预测一个分支的输出、执行预测目标地址的指令、当预测错误时采取纠正措施，从而降低控制相关的影响。使用记分板可能足以支持诸如ARM A8之类的简单两发射超标量处理器，而诸如四发射Intel i7之类更具主动性的处理器则受益于乱序执行的使用。

使用Tomasulo算法进行动态调度

IBM 360/91浮点单元使用一种支持乱序执行的高级方案。这一方案由Robert Tomasulo发明，它会跟踪指令的操作数何时可用，将RAW冒险降至最低，并在硬件中引入寄存器重命名功能，将WAW和WAR冒险降至最低。在现代处理器中存在这一方案的许多变体，但跟踪指令相关以允许在操作数可用时立即执行指令、重命名寄存器以避免WAR和WAW冒险，这些核心概念仍然是它们的共同特征。

IBM的目标是从指令集出发、从为整个350计算机系列设计的编译器出发来实现高浮点性能，而不是通过采用专门为高端处理器设计的编译器来实现。360体系结构只有4个双精度浮点寄存器，它限制了编译器调度的有效性；这一事实是开发Tomasulo方法的另一个动机。此外，IBM 360/91的内存访问时间和浮点延迟都很长，Tomasulo算法就是设计用来克服这些问题的。在本节的最后，我们将会看到Tomasulo算法还支持重叠执行一个循环的多个迭代。

我们将在MIPS指令集上下文中解释这一算法，重点放在浮点单元和载入-存储单元。MIPS与360之间的主要区别是后者的体系结构中存在寄存器存储器指令。由于Tomasulo算法使用一个载入功能单元，所以添加寄存器-存储器寻址模式并不需要进行大量修改。IBM 360/91还有一点不同，它拥有的是流水化功能单元，而不是多个功能单元，但我们在描述该算法时仍然假定它有多个功能单元。它只是对功能单元进行流水化的概念扩展。

我们将会看到，如果仅在操作数可用时才执行指令，就可以避免RAW冒险，而这正是一些简单记分板方法提供的功能。WAR和WAW冒险（源于名称相关）可以通过寄存器重命名来消除。对所有目标寄存器（包括较早指令正在进行读取或写入的寄存器）进行重命名，使乱序写入不会影响到任何依赖某一操作数较早值的指令，从而消除WAR和WAW冒险。为了更好地理解寄存器重命名如何消除WAR和WAW冒险，考虑以下可能出现WAR和WAW冒险的代码序列示例：

DIV.D     F0,F2,F4
ADD.D     F6,F0,F8
S.D       F6,0(R1)
SUB.D     F8,F10,F14
MUL.D     F6,F10,F8

以上代码共有两处反相关：ADD.D与SUB.D之间，S.D和MUL.D之间。在ADD.D和MUL.D之间还有一处输出相关，从而一共可能存在3处冒险：ADD.D使用F8和SUB.D使用F6时的WAR冒险，以及因为ADD.D可能在MUL.D之后完成所造成的WAW冒险。还有3个真正的数据相关：DIV.D和ADD.D之间、SUB.D和MUL.D之间、ADD.D和S.D之间。

这3个名称相关都可以通过寄存器重命名来消除。为简便起见，假定存在两个临时寄存器：S和T。利用S和T，可以对这一序列进行改写，使其没有任何相关，如下所示:

DIV.D    F0,F2,F4
ADD.D    S,FO,F8
S.D      S, 0(R1)
SUB.D    T,F10,F14
MUL.D    F6,F10,T

此外，对F8的任何后续使用都必须用寄存器T来代替。在这个代码段中，可以由编译器静态完成这一重命名过程。要在后续代码中找出所有使用F8的地方，需要采用高级编译器分析或硬件支持，这是因为上述代码段与后面使用F8的位置之间可能存在插入分支。我们将会看到，Tomasulo算法可以处理跨越分支的重命名问题。

在Tomasulo方案中，寄存器重命名功能由保留站提供，保留站会为等待发射的指令缓冲操作数。其基本思想是：保留站在一个操作数可用时马上提取并缓冲它，这样就不再需要从寄存器中获取该操作数。此外，等待执行的指令会指定保留站，为自己提供输入。最后，在对寄存器连续进行写入操作并且重叠执行时，只会实际使用最后一个操作更新寄存器。在发射指令时，会将待用操作数的寄存器说明符更名，改为保留站的名字，这就实现了寄存器重命名功能。

由于保留站的数目可能多于实际寄存器，所以这一技术甚至可以消除因为名称相关而导致的冒险，这类冒险是编译器所无法消除的。使用保留站，而不使用集中式寄存器堆，可以导致另外两个重要特性。

• 冒险检测和执行控制是分布式的：每个功能单元保留站中保存的信息决定了一条指令什么时候可以开始在该单元中执行。
• 结果将直接从缓冲它们的保留站中传递给功能单元，而不需要经过寄存器。这一旁路是使用公共结果总线完成的，它允许同时载入所有等待一个操作数的单元。在具有多个执行单元并且每个时钟周期发射多条指令的流水线中，将需要不止一条总线。

图3-4给出了基于Tomasulo算法的处理器的基本结构，其中包括浮点单元和载入存储单元；所有执行控制表均未显示。每个保留站保存一条已经被发射、正在功能单元等待执行的指令，如果已经计算出这一指令的操作数值，则保留这些操作数值，如果还没有计算出，则保留提供这些操作数值的保留站名称。

使用Tomasulo箅法的MIPS浮点单元的基本结构。指令由指令单元发送给指令队列，再按先入先出（FIFO）顺序从指令队列中发射出去。保留站包括运算和实际操作数，还有用于检测和解决冒险的信息。载入缓冲区有3项功能：

1. 保存有效地址的各个部分，直到计算完成；
2. 跟踪正在等待存储器的未完成载入过程；
3. 保存正在等待总线的已完成载入过程的结果。

与此类似，存储器缓冲区也有3项功能：

1. 保存有效地址的各个部分，直到计算完成；
2. 对于尚未完成、正在等待待存储数据值的存储过程，存储其目标存储器地址；
3. 保存要存储的地址和数据值，直到存储器单元可用为止。

来自FP单元或载入单元的所有结果都被放在CDB中，它会通向FP寄存器堆以及保留站和存储器缓冲区。FP加法器实现加法和减法，FP乘法器完成乘法和除法。

载入缓冲区和存储缓冲区保存来自和进入存储器的数据或地址，其行为方式基本与保留站相同，所以我们仅在必要时才区分它们。浮点寄存器通过一对总线连接到功能单元，由一根总线连接到存储缓冲区。来自功能单元和来自存储器的所有结果都通过公共数据总线发送，它会通向除载入缓冲区之外的所有地方。所有保留站都有标记字段，供流水线控制使用。

在详细描述保留站和此算法之前，让我们看看一条指令所经历的步骤。尽管每条指令现在可能需要任意数目的时钟周期，但一共只有以下3个步骤。

• 发射
  • 从指令队列的头部获取下一条指令，指令队列按FIFO顺序维护，以确保能够保持数据流的正确性。如果有一个匹配保留站为空，则将这条指令发送到这个站中，如果操作数值当前已经存在于寄存器，也一并发送到站中。如果没有空保留站，则存在结构性冒险，该指令会停顿，直到有保留站或缓冲区被释放为止。如果操作数不在寄存器中，则一直跟踪将生成这些操作数的功能单元。这一步骤将对寄存器进行重命名，消除WAR和WAW冒险。（在动态调度处理器中，这一阶段有时被称为分派。）
• 执行
  • 如果还有一个或多个操作数不可用，则在等待计算的同时监视公共数据总线。当一个操作数变为可用时，就将它放到任何一个正在等待它的保留站中。当所有操作数都可用时，则可以在相应功能单元中执行运算。通过延迟指令执行，直到操作数可用为止，可以避免RAW冒险。（一些动态调度处理器将这一步骤称为“发射”，但我们使用“执行”一词。）
  • 注意，在同一时钟周期，同一功能单元可能会有几条指令同时变为就绪状态。尽管独立功能单元可以在同一时钟周期执行不同指令，如果单个功能单元有多条指令准备就绪，那这个单元就必须从这些指令中进行选择。对于浮点保留站，可以任意作出这一选择；但是载入和存储指令可能要更复杂一些。载入和存储指令的执行过程需要两个步骤。第一步是在基址寄存器可用时计算有效地址，然后将有效地址放在载入缓冲区或存储缓冲区中。载入缓冲区中的载入指令在存储器单元可用时立即执行。存储缓冲区中的存储指令等待要存储的值，然后将其发送给存储器单元。邇过有效地址的计算，载入和存储指令保持程序顺序，稍后将会看到，这样有助于通过存储器来避免冒险。
  • 为了保持异常行为，对于任何一条指令，必须要等到根据程序顺序排在这条指令之前的所有分支全部完成之后，才能执行该指令。这一限制保证了在执行期间导致异常的指令实际上已经执行。在使用分支预测的处理器中（就和所有动态调度处理器一样），这意味着处理器在允许分支之后的指令开始执行之前，必须知道分支预测是正确的。如果处理器记录了异常的发生，但没有实际触发，则可以开始执行一条指令，在进入写结果阶段之前没有停顿。后面可以看到，推测提供了一种更灵活、更完整的异常处理方法，所以我会将推后进行这一改进，并说明推测是如何解决这一问题的。
• 写结果
  • 在计算出结果之后，将其写到CDB上，再从CDB传送给寄存器和任意等待这一结果的保留站（包括存储缓冲区）。存储指令一直缓存在存储缓冲区中，直到待存储值和存储地址可用为止，然后在有空闲存储器单元时，立即写入结果。

保留站、寄存器堆和载入存储缓冲区都采用了可以检测和消除冒险的数据结构，根据对象的不同，这些数据结构中的信息也稍有不同。这些标签实际上就是用于重命名的虛拟寄存器扩展集的名字。在这里的例子中，标签字段包含4个数位，用来表示5个保留站之一或5个载入缓冲区之一。后面将会看到，这相当于设定了10个可以指定为结果寄存器的寄存器。在拥有更多真正寄存器的处理器中，我们可能希望重命名能够提供更多的虚拟寄存器。标签字段指出哪个保留站中包含的指令将会生成作为源操作数的结果。

在指令被发射出去并开始等待源操作数之后，将使用一个保留站编号来引用该操作数，这个保留站中保存着将对寄存器进行写操作的指令。如果使用一个未用作保留站编号的值来引用该操作数（比如0），则表明该操作数已经在寄存器中准备就绪。由于保留站的数目多于实际寄存器数目，所以使用保留站编号对结果进行重命名，就可以避免WAW和WAR冒险。在Tomasulo方案中，保留站被用作扩展虚拟寄存器，而其他方法可能使用拥有更多寄存器的寄存器集，也可能使用诸如重排序缓冲区这样的结构。

在Tomasulo方案以及后面将会介绍的支持推测的方法中，结果都是在受保留站监视的总线（CDB）上广播。采用公用结果总线，再由保留站从总线中提取结果，共同实现了静态调度流水线中使用的转发和旁路机制。但在这一做法中，动态调度方案会在源与结果之间引入一个时钟周期的延迟，这是因为要等到“写结果”阶段才能让结果与其应用匹配起来。因此，在动态调度流水线中，在生成结果的指令与使用结果的指令之间至少要比生成该结果的功能单元的延迟长一个时钟周期。

一定别忘了，Tomasulo方案中的标签引用的是将会生成结果的缓冲区或单元；当一条指令发射到保留站之后，寄存器名称将会丢弃。（这是Tomasulo方案与记分板之间的一个关键区别：在记分板中，操作数保存在寄存器中，只有生成结果的指令已经完成、使用结果的指令做好执行准备之后才会读取操作数。）每个保留站有以下7个字段。

• Op——对源操作数S1和S2执行的运算。
• Qj、Qk——将生成相应源操作数的保留站；当取值为0时，表明已经可以在Vj或Vk中获得源操作数，或者不需要源操作数。
• Vj、Vk——源操作数的值。注意，对于每个操作数，V字段和Q字段中只有一个是有效的。对于载入指令，Vk字段用于保存偏移量字段。
• A——用于保存为载入或存储指令计算存储器地址的信息。在开始时，指令的立即数字段存储在这里；在计算地址之后，有效地址存储在这里。
• Busy——指明这个保留站及其相关功能单元正被占用。

寄存器堆有一个字段Qi。

• Qi——一个运算的结果应当存储在这个寄存器中，则Qi是包含此运算的保留站的编号。如果Qi的值为空（或0），则当前没有活动指令正在计算以此寄存器为目的地的结果，也就是说这个值就是寄存器的内容。

载入缓冲区和存储缓冲区各有一个字段A，一旦完成了第一个执行步骤，这个字段中就包含了有效地址的结果。在下一节，我们将首先看一些示例，说明这些机制是如何工作的，然后再详细研究具体算法。

动态调度:示例和算法

在详细研究Tomasulo算法之前，让我们看几个示例，这些示例有助于说明这种算法的工作方式。

对于以下代码序列，写出在仅完成了第一条载入指令并已将其结果写到CDB总线时的信息表:

L.D     F6,32 (R2)
L.D     F2,44(R3)
MUL.D   F0,F2,F4
SUB.D   F8,F2,F6
DIV.D   F10,F0,F6
ADD.D   F6,F8, F2

表3-3用3个表显示了其结果。Add、 Mult和Load之后附加的数字表示保留站的标签——Add1是第一加法单元计算结果的标签。此外，我们还给出了一个指令状态表。之所以列出这个表是为了帮助读者理解这一算法；它不是硬件的实际组成部分，而是由保留站来保存每个已发射运算的状态。

表3-3当所有指令都已经被发射， 但只有第一-条载入指令已经完成而且已将其结果写到CDB时的保留站与寄存器标签。

与先前的较简单方案相比，Tomasulo方案有两点优势：

1. 冒险检测逻辑的分布；
2. 消除了可能产生WAW和WAR冒险的停顿。

第一个优势源于分布式保留站和CDB的使用。如果多条指令正在等待同一个结果，而每条指令的其他操作数均已准备就绪，那么在CDB上广播这一结果就可以同时释放这些指令。如果使用集中式的寄存器堆，这些单元必须在寄存器总线可用时从寄存器中读取自己的结果。

第二个优势（消除WAW和WAR冒险）的实现是利用保留站来重命名寄存器，并在操作数可用时立即将其存储在保留站中。

例如，尽管存在涉及F6的WAR冒险，但表3-3中的代码序列发射了DIV.D和 ADD.D。这一冒险通过两种方法之一消除。第一种方法：如果为DIV. D提供操作数的指令已经完成，则Vk中会存储这个结果，使DIV.D不需要ADD.D就能执行（表中所示的就是这种情况）。另一方面，如果L.D还没有完成，则Qk将指向Load1保留站，DIV.D指令不再依赖于ADD.D。因此，在任一情况下，ADD.D都可以发射并开始执行。在用到DIV.D的结果时，都会指向保留站，使ADD.D能够完成，并将其值存储在寄存器中，不会影响到DIV.D。

稍后将会看到一个消除WAW冒险的例子。但先来看看前面的示例是如何继续执行的。在这个例子以及本章后面的例子中，假定有如下延迟值：载入指令为1个时钟周期，相加指令为2个时钟周期，乘法指令为6个时钟周期，除法指令为12个时钟周期。

对于上例中的同一代码段，给出当MUL.D做好写出结果准备时的状态表。

其结果如表3-4中的3个表格所示。注意，在复制DIV.D的操作数时ADD.D已经完成，所以克服了WAR冒险问题。注意，既然F6的载入操作被延迟，在执行对F6的加法操作时也不会触发WAW冒险。

Tomasulo 算法：细节

表3-5给出了每条指令都必须经历的检查和步骤。前面曾经提到，载入指令和存储指令在进入独立载入或存储缓冲区之前，要经过一个进行有效地址计算的功能单元。载入指令会进入第二执行步骤，以访问存储器，然后进如“写结果”阶段，将来自存储器的值写入寄存器堆以及（或者）任何正在等待的保留站。存储指令在写结果阶段完成其执行，将结果写到存储器中。注意，无论目标是寄存器还是存储器，所有写入操作都在“写结果”阶段发生。这一限制简化了Tomasulo算法，是其扩展到支持推测功能的关键。

对于发射指令，rd是目的地、rs和rt是源寄存器编号、imm是符号扩展立即数字段，r是为指令指定的保留站或缓冲区。RS 是保留站数据结构。FP 单元或载入单元返回的值称为result。RegisterStat是寄存器状态数据结构（不是寄存器堆，寄存器堆应当是Regs[]）。当发射指令，目标寄存器的Qi字段被设置为向其发射该指令的缓冲区或保留站编号。如果操作数巳经存在于寄存器中，就将它们存储在V字段中。否则，设置Q字段，指出将生成源操作数值的保留站。指令将一直在保留站中等待，直到它的两个操作数都可用为止，当Q字段中的取值为0时即表示这一状态。当指令已被发射，或者当这一指令所依赖的指令已经完成并写回结果时，这些Q字段被设置为0。当一条指令执行完毕，并且CDB可用时，它就可以进行写回操作。任何一个缓冲区、寄存器和保留站，只要其Qj或Qk值与完成该指令的保留站相同，都会由CDB更新其取值，并标记Q字段，表明已经接收到这些值。因此，CDB可以在一个时钟周期中向许多目标广播其结果，如果正在等待这一结果的指令已经有了其他操作数，那就都可以在下一个时钟周期开始执行了。载入指令要经历两个执行步骤，存储指令在写结果阶段稍有不同，它们必须在这一阶段等待要存储的值。记住，为了保持异常行为，如果按照排在程序顺序前面的分支还没有完成，就不应允许执行后面的指令。由于在发射阶段之后不再保持任何有关程序顺序的概念，因此，为了实施这一限制，在流水线中还有未完成的分支时，通常不允许任何指令离开发射步骤。

Tomasulo算法: 基于循环的示例

为了理解通过寄存器的动态重命名来消除WAW和WAR胃险的强大威力，我们需要看一个循环。考虑下面的简单序列，将一个数组的元素乘以F2中的标量：

Loop:   L.D      F0,0(R1)
        MUL. D   F4,F0,F2
        S.D      F4,0(R1)
        DADDIU   R1,R1,-8
        BNE      R1, R2, Loop; branches if R1 | R2

如果我们预测会执行这些分支转移，那使用保留站可以同时执行这个循环的多条指令。不需要修改代码就能实现这一好处——实际上，这个循环是由硬件使用保留站动态展开的，这些保留站经过重命名获得，充当附加寄存器。

假定已经发射了该循环两个连续迭代中的所有指令，但一个浮点载入存储指令或运算也没有完成。表3-6显示了在此时刻的保留站、寄存器状态表和载入缓冲区与存储缓冲区。（整数ALU运算被忽略，假定预测选中该分支。）一旦系统达到这一状态，如果乘法运算可以在4个时钟周期内完成，则流水线中可以保持该循环的两个副本，CPI接近1.0。在达到稳定状态之前，还需要处理其他一些迭代，延迟为6个时钟周期。这需要有更多的保留站来保存正在运行的指令。在本章后面将会看到，在采用多指令发射对Tomasulo方法进行扩展时，它可以保持每个时钟周期处理一条以上指令的速度。

表3-6 还没有指令完成时，循环的两个活动迭代

乘法器保留站中的项目指出尚未完成的载入指令是操作数来源。存储保留站指出乘法运算的目标位置是待存储值的来源。

只要载入指令和存储指令访问的是不同地址，就可以放心地乱序执行它们。如果载入指令和存储指令访问相同地址，则会出现以下两种情况之一：

• 根据程序顺序，载入指令位于存储指令之前，交换它们会导致WAR冒险;
• 根据程序顺序，存储指令位于载入指令之前，交换它们会导致RAW冒险。

依此类似，交换两个访问同一地址的存储指令会导致WAW冒险。

因此，为了判断在给定时刻是否可以执行一条载入指令，处理器可以检查：根据程序顺序排在该载入指令之前的任何未完成存储指令是否与该载入指令共享相同数据存储器地址。对于存储指令也是如此，如果按照程序顺序排在它前面的载入指令或存储指令与它访问的存储器地址相同，那它必须等到所有这些指令都执行完毕之后才能开始执行。

为了检测此类冒险，处理器必须计算出与任何先前存储器运算有关的数据存储器地址。为了保证处理器拥有所有此类地址，一种简单但不一定最优的方法是按照程序顺序来执行有效地址计算。（实际只需要保持存储及其他存储器引用之间的相对顺序，也就是说，可以随意调整载入指令的顺序。）

首先来考虑载入指令的情况。如果按程序顺序执行有效地址计算，那么当一条载入指令完成有效地址计算时，就可以通过查看所有活动存储缓冲区的A字段来确定是否存在地址冲突。如果载入地址与存储缓冲区中任何活动项目的地址匹配，则在发生冲突的存储指令完成之前，不要将载入指令发送到载入缓冲区。（有些实施方式将要存储的值直接传送给载入指令，减少了因为这一RAW冒险造成的延迟。）

存储指令的工作方式类似，只是因为发生冲突的存储指令不能调整相对于载入或存储指令的顺序，所以处理器必须在载入与存储两个缓冲区中检查是否存在冲突。

如果能够准确预测分支（这是在上一节解决的问题），动态调度流水线可以提供非常高的性能。这种方法的主要缺点在于Tomasulo方案的复杂性，它需要大量硬件。具体来说，每个保留站都必须包含一个必须高速运转的相关缓冲区，还有复杂的控制逻辑。它的性能还可能受到单个CDB的限制。尽管可以增加更多CDB，但每个CDB都必须与每个保留站进行交互，必须在每个保留站为每个CDB配备相关标签匹配硬件。

在Tomasulo方案中，可以组合使用两种不同技术：对体系结构寄存器重命名，提供更大的寄存器集合；缓冲来自寄存器堆的源操作数。源操作数缓冲消除了当操作数在寄存器中可用时出现的WAR冒险。后面将会看到，通过对寄存器重命名，再结合对结果的缓存，直到对寄存器早期数据的引用全部结束，这样也有可能消除WAR冒险。在我们讨论硬件推测时将会用到这一方法。

从20世纪90年代开始在多发射处理器中采用，原因有如下几个。

1. 尽管Tomasulo算法是在缓存出现之前设计的，但缓存的出现以及其固有的不可预测的延迟，已经成为使用动态调度的主要动力之一。乱序执行可以让处理器在等待解决缓存缺失的同时继续执行指令，从而消除了全部或部分缓存缺失代价。
2. 随着处理器的发射功能变得越来越强大，设计人员越来越关注难以调度的代码（比如，大多数非数值代码）的性能，所以诸如寄存器重命名、动态调度和推测等技术变得越来越重要。
3. 无需编译器针对特定流水线结构来编译代码，Tomasulo 算法就能实现高性能。

基于硬件的推测

当我们尝试开发更多指令级并行时，控制相关的维护就会成为一项不断加重的负担。分支预测减少了由于分支导致的直接停顿，但对于每个时钟周期要执行多条指令的处理器来说，仅靠正确地预测分支可能不足以生成期望数量的指令级并行。宽发射处理器可能需要每个时钟周期执行一个分支才能维持最高性能。因此，要开发更多并行，需要我们克服控制相关的局限性。

通过预测分支的输出，然后在假定猜测正确的前提下执行程序，可以克服控制相关问题。这种机制对采用动态调度的分支预测进行了一种虽细微但很重要的扩展。具体来说，通过推测，我们提取、发射和执行指令，就好像分支预测总是正确的；而动态调度只是提取和发射这些指令。当然，我们需要一些机制来处理推测错误的情景。

基于硬件的推测结合了3种关键思想：

1. 用动态分支预测选择要执行哪些指令；
2. 利用推测，可以在解决控制相关问题之前执行指令（能够撤消错误推测序列的影响）；
3. 进行动态调度，以应对基本模块不同组合方式的调度。（与之相对，没有推测的动态调度需要先解析分支才能实际执行后期基本模块的操作，因为只能部分重叠基本模块。）

基于硬件的推测根据预测的数据值流来选择何时执行指令。这种执行程序的方法实际上是一种数据流执行：操作数一旦可用就立即执行运算。

为了扩展Tomasulo算法，使其支持推测，我们必须将指令结果的旁路（以推测方式执行指令时需要这一操作）从一条指令的实际完成操作中分离出来。进行这种分离之后，就可以允许执行一条指令，并将其结果旁路给其他指令，但不允许这条指令执行任何不能撤消的更新操作，直到确认这条指令不再具有不确定性为止。

使用旁路值类似于执行一次推测寄存器读取操作，因为在提供源寄存器值的指令不再具有不确定性之前，我们无法知道它是否提供了正确值。当一个指令不再具有不确定性时，允许它更新寄存器堆或存储器；我们将指令执行序列中的这个附加步骤称为指令提交。实现推测之后的关键思想在于允许指令乱序执行，但强制它们循序提交，以防止在指令提交之前采取任何不可挽回的动作（比如更新状态或激发异常）。因此，当我们添加推测时，需要将完成执行的过程与指令提交区分开来，这是因为指令执行完毕的时间可能远远早于它们做好提交准备的时间。在指令执行序列中添加这一提交阶段需要增加一组硬件缓冲区，用来保存已经完成执行但还没有提交的指令结果。这一硬件缓冲区称为重排序缓冲区，也可用于在可被推测的指令之间传送结果。

重排序缓冲区（ROB）像Tomasulo算法通过保留站扩展寄存器集一样，提供了附加寄存器。ROB会在一定时间内保存指令的结果，这段时间从完成该指令的相关运算算起，到该指令提交完毕为止。因此，ROB是指令的操作数来源，就像Tomasulo算法中的保留站提供操作数一样。

两者之间的关键区别在于：在Tomasulo算法中，一旦一条指令写出其结果之后，任何后续发射的指令都会在寄存器堆中找到该结果。而在采用推测时，寄存器堆要等到指令提交之后才会更新（我们非常确定该指令会被执行）；因此，ROB是在指令执行完毕到指令提交这段时间内提供操作数。ROB类似于Tomasulo 算法中的存储器缓冲区，为简单起见，我们将存储器缓冲区的功能集成到ROB中。

ROB中的每个项目都包含4个字段：指令类型、目的地字段、值字段和就绪字段。指令类型字段指定这个指令是分支（没有目的地结果）、存储指令（含有存储器地址目的地），还是寄存器操作（ALU运算或载入指令，它含有寄存器目的地）。目的地字段提供了应当向其中写入指令结果的寄存器编号（对于载入指令和ALU运算）或存储器地址（对于存储指令）。值字段用于在提交指令之前保存指令结果值。我们稍后将会看到ROB项目的一个例子。最后一个就绪字段指出指令已经完成执行，结果值准备就绪。

图3-5给出包含ROB的处理器的硬件结构。ROB包含存储缓冲区。存储指令仍然分两步执行，但第二步是由指令提交来执行的。尽管保留站的重命名功能由ROB代替，但在发射运算之后仍然需要一个空间来缓冲它们（以及操作数），直到它们开始执行为止。这一功能仍然由保留站提供。由于每条指令在提交之前都在ROB拥有一个位置，所以我们使用ROB项目编号而不是保留站编号来标记结果。这种标记方式要求必须在保留站中跟踪为一条指令分配的 ROB。

图3-5 使用 Tomasulo箅法的FP单元的基本结构，为处理推测而进行了扩展。将此图与实施Tomasulo算法的图3-4对比，主要变化是添加了ROB，去除了存储器缓冲区，后者的功能被集成到ROB中。如果拓宽CDB，以允许每个时钟周期完成多条指令，则可以将这一机制扩展为支持多发射方案

在指令执行时涉及以下4个步骤。

1. 发射——从指令队列获得一条指令。如果存在空保留站而且ROB中有空插槽，则发射该指令；如果寄存器或ROB中已经含有这些操作数，则将其发送到保留站。更新控制项，指明这些缓冲区正在使用中。为该结果分配的ROB项目编号也被发送到保留站，以便在将结果放在CDB上时，可以使用这个编号来标记结果。如果所有保留站都被占满或者ROB被占满，则指令发射过程停顿，直到这两者都有可用项目为止。
2. 执行——如果还有一个或多个操作数不可用，则在等待计算寄存器的同时监视CDB。这一步骤检查RAW冒险。当保留站中拥有这两个操作数时，执行该运算。指令在这一阶段可能占用多个时钟周期，载入操作在这一阶段仍然需要两个步骤。此时执行存储指令只是为了计算有效地址，所以在这一阶段只需要有基址寄存器可用即可。
3. 写结果——当结果可用时，将它写在CDB上（还有在发射指令时发送的ROB标签），并从CDB写到ROB并写到任何等待这一结果的保留站。将保留站标记为可用。对于存储指令需要执行一些特殊操作。如果要存储的值已经准备就绪，则将它写到ROB项目的Value字段，以备存储。如果要存储的值还不可用，CDB必须进行监视，直到该数值被广播时再更新该存储指令ROB项目的Value字段。为简单起见，我们假定这一过程在存储操作的写结果阶段进行；
4. 提交——这是完成指令的最后一个阶段，在此之后将仅留下它的结果。（一些处理器将这一提交阶段称为“完成”或“毕业”。）根据要提交的指令是预测错误的分支、存储指令，或是任意其他指令（正常提交），在提交时共有3种不同的操作序列。当一个指令到达ROB的头部而且其结果出现在缓冲区中，则进行正常提交；此时，处理器用结果更新其寄存器，并从ROB清除该指令。提交存储指令与正常提交类似，但更新的是存储器而不是结果寄存器。当预测错误的分支到达ROB的头部时，它指出推测是错误的。ROB被刷新，执行过程从该分支的后续正常指令处重新开始。如果对该分支的预测正确，则该分支完成提交。

指令一旦提交完毕，它在ROB的相应项将被收回，寄存器或存储器目的地被更新，不再需要ROB项。如果ROB填满，那么只需要停止发射指令，直到有空闲项目为止。下面，我们研究一下这一机制如何处理前面为Tomasulo算法所举的示例。

假定浮点功能单元的延迟与前面示例中相同：加法为2个时钟周期、乘法为6个时钟周期、除法为12个时钟周期。使用下面的代码段（也就是前面用于生成表3-4的代码段），写出当MUL.D做好提交准备时的状态表。

L.D        F6,32(R2)
L.D        F2,44(R3)
MUL.D      F0,F2,F4
SUB.D      F8,F2,F6
DIV.D      F10,F0,F6
ADD.D      F6,F8,F2

表3-7用3个表给出了结果。注意，尽管SUB.D指令已经完成执行，但它不会在MUL.D提交之前提交。保留站和寄存器状态字段中的基本信息与Tomasulo算法中相同（见3.5节中关于这些字段的描述）。区别在于，Qj和Qk字段以及寄存器状态字段中的保留站编号被ROB项目编号代替，我们已经将Dest字段加到保留站中。Dest字段指定一个ROB项目，也就是这个保留站项目所生成结果的目的地。

MUL.D位于ROB的头部，此处两个L.D指令只是为了便于理解。尽管SUB.D和ADD.D指令的结果已经可用，而且可以用作其他指令的数据源，但它们在MUL.D指令提交之前不会提交。DIV.D正在执行过程中，但由于它的延迟要比MUL.D长，所有不会独自究成。“值”列表示所保存的值；#X格式表示ROB项目X的值字段。重排序缓冲区1和2实际上已经完成，但为了提供更多信息，也一并列在表中。

上面的例子说明了采用推测的处理器与采用动态调度的处理器之间的关键区别。对比表3-7与表3-4中的内容，后者显示的是同一代码序列在采用Tomasulo算法的处理器上的执行情况。关键区别在于：在上面的例子中，MUL.D是排在最前面的未完成指令，它之后的所有指令都不允许完成。而在表3-4中，SUB.D和ADD.D指令也已经完成。

这一区别意味着具有ROB的处理器可以在维持精确中断模式的同时动态执行代码。例如，如果MUL.D指令导致一个中断，我们只需要等待它到达ROB的头部并生成该中断，刷新ROB中的任意其他未完成指令。由于指令提交是按顺序进行的，所以这样会生成一个精确异常。

而在使用Tomasulo算法的例子中，SUB.D和ADD.D指令都可以在MUL.D激发异常之前完成。结果就是寄存器F8和F6（SUB.D和ADD.D指令的目的地）可能被改写，中断可能不准确。

一些用户和架构师认为不准确的浮点异常在高性能处理器中是可接受的，因为程序可能会终止。而其他类型的异常，比如页面错误，由于程序必须在处理此类异常之后透明地恢复执行，所以很难容忍这些异常出现不准确情况。

在循序提交指令时使用ROB，除了支持推测执行之外，还可以提供准确的异常，如下例所示。

考虑前面Tomasulo算法使用的示例，表3-6显示了其执行情况:

Loop:
        L.D      F0,0(R1)
        MUL.D    F4,F0,F2
        S.D      F4,0(R1)
        DADDIU   R1,R1,#-8.
        BNE      R1,R2,Loop   ;branches if R1|R2

假定这个循环中所有指令已经发射了两次。还假定第一次迭代的L.D和MUL.D指令已经提交，并且所有其他指令都已经完成执行。正常情况下，存储指令将在ROB中等待有效地址操作数（本例中为R1）和值（本例中为F4）。由于我们只考虑浮点流水线，所以假定存储指令的有效地址在发射该指令时计算。

表3-8用两个表给出了结果。

由于在提交指令之前，寄存器值和存贮器值都没有实际写入，所以在发射分支预测错误时，处理器可以很轻松地撤销其推测操作。假定在表3-8中第一次没有选中分支BNE。当该分支之前的指令到达ROB的头部之后，直接提交即可；当分支到达缓冲区的头部时，将会清除缓冲区，处理器开始从其他路径提取指令。

在实践中，进行推测的处理器会在错误预测一个分支后尽早恢复。将预测错误的分支之后的所有ROB项目清空，使该分支之前的ROB项目继续执行，并在后续的正确分支处重新开始提取指令，从而完成恢复操作。在推测处理器中，由于错误预测的影响更大一些，所以性能对分支预测也更敏感。因此，分支处理的各个方面（预测准确度、预测错误的检测延迟、预测错误的恢复时间）都变得更为重要。

在处理异常时，要等到做好提交准备时才会识别异常。如果推测的指令产生异常，则将异常记录在ROB中。如果出现分支预测错误，而且指令还没有执行，则在清除ROB时将异常连同指令一直刷新。如果指令到达ROB的头部，我们就知道它不再具有不确定性，应当激发该异常。我们还可以在异常出现之后、所有先前指令都已处理完毕的情况下立即处理异常，但异常要比分支预测错误的处理更难一些，而且由于异常的发生概率要更低一些，所以其重要性也要低一些。

表3-9给出了一条指令的执行步骤，以及为了继续执行这些步骤和要采取的动作而必须满足的条件。我们给出了到提交时才解决预测错误分支时的情景。尽管推测似乎只是对动态调度添加了非常简单的一点儿内容，但通过对比表3-9和表3-5中Tomasulo算法的相应内容，可能看出推测大大增加了控制复杂度。此外，还要记住分支预测也要更复杂一些。

在推测处理器处理存储指令时与Tomasulo算法中有一点非常重要的不同。在Tomasulo算法中，一条存储指令可以在到达“写结果”阶段（确保已经计算出有效地址）且待存储值可用时更新存储器。在推测处理器中，只有当存储指令到达ROB的头部时才能更新存储器。这一区别可以保证当指令不再具有不确定性时才会更新存储器。

表3-9大幅简化了存储指令，在实践中不需要这一简化。表3-9需要存储指令在写结果阶段等待寄存器源操作数，它的值就是要存储的内容；随后将这个值从该存储指令的保留站的Vk字段移到该存储指令ROB项目的“值”字段。但在现实中，待存储值只需要在提交存储指令之前到达即可，可以直接将源指令放到存储指令的ROB项目中。其实现方法为：用硬件来跟踪要存储的源值什么时候在该存储指令的ROB项目中准备就绪，并在每次完成指令时搜索ROB，查看相关存储指令。

对于发射的指令，rd为目的地、rs和rt为源、r为分配的保留站、b是分配的ROB项目、h是ROB的头项目。RS是保留站数据结构。保留站返回的值被称为result。RegisterStat 是寄存器数据结构，Regs表示实际寄存器，ROB是重排序缓冲区数据结构。

这一补充并不复杂，但添加之后有两个效果：需要向ROB中添加一个字段，表3-9尽管已经采用了小字体，但仍然会变得更长!尽管表3-9进行了简化，但在本示例中，我们将允许该存储指令跳过写结果阶段，只需要在准备提交前得到要保存的值即可。和Tomasulo算法一样，我们必须避免存储器冒险。用推测可以消除存储器中的WAW和WAR冒险，这是因为存储器更新是循序进行的，当存储指令位于ROB头部时，先前不可能再有尚未完成的载入或存储指令。通过以下两点限制来解决存储器中的RAW冒险。

• 如果一条存储指令占用的活动ROB项目的“目的地”字段与一条载入指令的A字段取值匹配，则不允许该载入指令开始执行第二步骤。
• 在计算一条载入指令的有效地址时，保持相对于所有先前存储指令的程序顺序。

这两条限制条件共同保证了：对于任何一条载入指令，如果它要访问由先前存储指令写入的存储器位置，在这条存储指令写入该数据之前，该载入指令不能执行存储器访问。在发生此类RAW冒险时，一些推测处理器会直接将来自存储指令的值旁路给载入指令。另一种方法是采用值预测方式预测可能出现的冲突；我们将在3.9节考虑这一方法。尽管这里对推测执行的解释主要是针对浮点运算的，但这些技术可以很容易地扩展到整数寄存器和功能单元。事实上，推测在整数程序中可能更有用一些，因为这些程序中的代码可能更难预测一些。此外，只要允许在每个周期内发射和提交多条指令，就可以将这些技术扩展到能够在多发射处理器中工作。事实上，在这些处理器中，一些实用技术可能会在编译器的支持下在基本模块中开发足够的指令级并行，所以对这些处理器来说，推测技术可能是最有意义的。

以多发射和静态调度来开发ILP

前面几节介绍的技术可以用来消除数据与控制停顿，使用CPI到达理想值1。为了进一步提高性能，我们希望将CPI降低至小于1，但如果每个时钟周期仅发射一条指令，那CPI是不可能降低到小于1的。

多发射处理器的目标就是允许在一个时钟周期中发射多条指令。多发射处理器主要有以下3类。

1. 静态调度超标量处理器。
2. VLIW（超长指令字）处理器。
3. 动态调度超标量处理器。

两种超标量处理器每个时钟发射不同数目的指令，如果它们采用静态调度则采用循序执行，如果采用动态调度则采用乱序执行。

与之相对，VLIW处理器每个时钟周期发射固定数目的指令，这些指令可以设置为两种格式之一：一种格式是一个长指令；另一种是一个固定的指令包，指令之间具有一定的并行度，由指令显式表示出来。VLIW处理器由编译器进行静态调度。Intel和HP在创建IA-64体系结构时，它们还将这种体系结构命名为EPIC（显式并行指令计算机）。尽管静态调度超标量处理器在每个周期内发射的指令数是可变的，而不是固定的，但它们在概念上实际与VLIW更接近一些，这是因为这两种方法都依靠编译器为处理器调度代码。

由于静态调度超标量的收益会随着发射宽度的增长而逐渐减少，所以静态调度超标量主要用于发射宽度较窄的情况，通常仅有两条指令。超过这一宽度之后，大多数设计人员选择实现VLIW或动态调度超标量。由于两者的硬件要求和所需要的编译器技术是类似的，所以这一节将主要介绍VLIW。深入理解这一节的内容之后，可以很轻松地将相关道理扩展到静态调度超标量。

表3-10总结了多发射的基本方法和它们的突出特征，并给出了使用每一方法的处理器。

基本VLIW方法

VLIW使用多个独立功能单元。VLIW没有尝试向这些单元发射多条独立指令，而是将多个操作包装在一个非常长的指令中，或者要求发射包中的指令满足同样的约束条件。由于这两种方法之间没有本质性的区别，所以假定将多个操作放在一条指令中，原始VLIW方法即是如此。

由于VLIW的收益会随着最大发射率的增长而增长，所以我们主要关注宽发射处理器。实际上，对于简单的两发射处理器，超标量的开销可能是最低的。许多设计人员可能会说：四发射处理器的开销是可控的，但在本章后面将会看到，开销的增长是限制宽发射处理器的主要因素。

本章主要讨论硬件操作密集的技术，它们都采用某种超标量形式。EPIC方法扩展了早期VLIW方法的主要概念，将静态与动态方法结合在一起。

我们考虑一个VLIW处理器，在上面运行包含5种运算的指令，这5种运算是：一个整数运算（也可以是一个分支）两个浮点运算和两个存储器引用。这些指令可能拥有与每个功能单元相对应的一组字段，每个单元可能为16~24位，得到的指令长度介于80~120位之间。作为对比，Intel Itanium 1和2的每个指令包中包含6个运算（也就是说，它们允许同时发射两个3指令包）。

为使功能单元保持繁忙状态，代码序列必须具有足够的并行度，以填充可用操作插槽。这种并行是通过展开循环和调度单个更大型循环体中的代码而展现的。如果展开过程会生成直行代码，则可以使用局部调度技术，它可以对单个基本模块进行操作。如果并行的发现与开发需要在分支之间调度代码，那就必须使用可能更为复杂的全局调度算法。全局调度算法不仅在结构上更为复杂，而且由于在分支之间移动代码的成本很高，所以它们还必须进行非常复杂的优化权衡。

而现在，我们将依靠循环展开来生成一个长的直行代码序列，所以可以使用局部调度来构建VLIW指令，并集中研究这些处理器的运行情况。

假定有一个VLIW，它可以在每个时钟周期中发射两个存储器引用、两个浮点运算和整数运算或分支。写出针对这样一个处理器展开循环x[i] = x[i] + S的版本。可进行任意次展开，以消除所有停顿。忽略延迟分支。

表3-11给出了这一代码。该循环被展开后，形成循环体的7个副本，消除了所有停顿（即，全空发射周期），运行9个时钟周期。这一代码的运行速度为9个周期生成7个结果，也就是每个结果需要1.29个周期，与3.2节使用非展开调度代码的两发射超标量相比，速度差不多是它的两倍。

在假定没有分支延迟的情况下，这一代码需要9个周期；通常，分支延迟也需要进行调度。其发射速率为9个时钟周期发射23个运算，或者说每个周期2.5个运算。其效率为大约60%（也就是包含操作的可用插槽比例）。为了实现这一发射速率，需要更多寄存器，远远超过MIPS通常在处理这一循环时使用的寄存器数目。上面的VLIW代码序列需要至少8个浮点寄存器，而在基本MIPS处理器上，同一代码序列可以仅使用2个浮点寄存器，在使用未展开调度时，也只需要使用5个。

原始VLIW模块中既存在一些技术问题，也存在一些逻辑问题，从而降低了其效率。技术问题包括代码大小的增大和锁步（clockstep）操作的局限性。有两个不同因素共同造成VLIW代码大小的增大。

• 第一，要在直行代码段中生成足够操作，需要大量展开循环（如前面的示例所示），从而增大了代码大小。
• 第二，只要指令未被填满，那些没有用到的功能单元就会在指令编码时变为多余的位。为了应对这种代码大小的增长，有时会使用智能编码。比如，一条指令中可能只有一个很大的立即数字段供所有功能单元使用。另一种技术是在主存储器中压缩指令，然后在到达缓存或进行译码时再展开它们。

早期的VLIW是锁步工作的，根本就没有冒险检测硬件。在这种结构中，由于所有功能单元都必须保持同步，所以任意功能单元流水线中的停顿都必然导致整个处理器停顿。尽管一个编译器也许能够调度起决定作用的功能单元，以防止停顿，但要想预测哪些数据访问会遭遇缓存停顿，并对它们进行调度，那是非常困难的。因此，应当对缓存进行分块，并能导致所有功能单元停顿。由于发射速度和内存引用数目都变得很大，所以这一同步限制变得不可接受。在最近的处理器中，这些功能单元以更独立的方式工作，在发射时利用编译器来避免冒险，而在发射指令之后，可以通过硬件检测来进行非同步执行。

二进制代码兼容性也是VLIW的主要逻辑问题。在严格的VLIW方法中，代码序列既利用指令集定义，又要利用具体的流水线结构，包括功能单元及其延迟。因此，当功能单元数目和单元延迟不同时，就需要不同的代码版本。与超标量设计相比，由于这一要求而更难以在先后实施版本之间或者具有不同发射带宽的实施方式之间移植代码。当然，要想通过新的超标量设计而提高性能，可能需要重新编译。不过，能够运行旧版本二进制文件是超标量方法的一个实际优势。EPIC方法解决了早期VLIW设计中遇到的许多问题，包括扩展到更积极主动的软件推测与方法，在保证二进制兼容性的前提下克服硬件依赖的局限性。

所有多发射处理器都要面对的重要挑战是尝试开发大量ILP。这种并行是通过展开浮点程序中的简单循环而实现的，而原来的循环很可能可以在向量处理器上高效地运行。对于这类应用程序，目前还不清楚多发射处理器是否优于向量处理器；其成本是类似的，向量处理器的速度可能与多发射处理器相同，或者还会更快一些。多发射处理器相对于向量处理器的潜在优势在于它们能够从结构化程度较低的代码中提取某些并行，以及能够很轻松地缓存所有形式的数据。因为这些原因，多发射方法已经成为利用指令级并行的主要方法，而向量主要作为这些处理器的扩展。

以动态调度、多发射和推测来开发ILP

到目前为止，我们已经看到了动态调度、多发射和推测等各种机制是如何单独工作的。本节，我们将这三种技术结合在一起， 得到一种非常类似于现代微处理器的微体系结构。为简单起见，我们只考虑每个时钟周期发射两条指令的发射速率，但其概念与每个时钟周期发射三条或更多条指令的现代处理器没有什么不同。

假定我们希望扩展Tomasulo算法，以支持具有分离整数、载入存储和浮点单元（包括浮点乘和浮点）加的多发射超标量流水线，每个单元都可以在每个时钟周期启动一个操作。我们不希望向保留站乱序发射指令，这样可能会违犯程序语义。为了获得动态调度的全部好处，允许流水线在一个时钟周期内发射两条指令的任意组合，通过调度硬件向整数和浮点单元实际分配运算。由于整数指令和浮点指令的交互非常关键，所以还会扩展Tomasulo方案，以处理整数和浮点功能单元与寄存器，还能整合推测执行功能。如图3-6，其基本组织结构类似于每个时钟周期发射一条指令、具有推测功能的处理器的组织结构，不过必须改进其发射和完成逻辑，以允许每个时钟周期处理多条指令。

在动态调度处理器中（无论有无推测功能），每个时钟周期发射多条指令都非常复杂，原因很简单，这些指令之间可能存在相关性。因此，必须为这些并行指令更新控制表；否则，这些控制表中可能会出现错误，或者会丢失相关性。

在动态调度处理器中，已经采用两种方法在每个时钟周期内发射多条指令，这两种方法都基于这样一个事实：要在每个时钟周期中发射多条指令，其关键在于保留站的分配和流水线控制表的更新。一种方法是在一个时钟周期的一半时间内运行这一步骤，从而可以在一个时钟周期内运行2条指令；遗憾的是，很难将这一方法扩展为每个时钟周期处理4条指令。

第二种方法是构建必要的逻辑，一次处理两条或更多条指令，包括指令之间可能存在的相关性。可以在每个时钟周期发射四条或更多条指令的现代超标量处理器可能采用这两种方法：都采用流水线方式并拓宽了发射逻辑。一个重要的事实是：仅靠流水线无法解决这一问题。使指令发射占用多个时钟周期时，由于每个时钟周期都会发射新指令，所以必须能够分配保留站，并更新流水线表，使下一个时钟周期进行的相关指令发射能够利用更新后的信息。

在动态调度超标量中，这一发射步骤是最基本的瓶颈之一。为了说明这一过程的复杂性，表3-12给出了一种情景下的发射逻辑：在发射载入命令之后执行一个相关浮点运算。这个逻辑的基础是表3-9，但它仅代表一种情景。在现代超标量中，对于所有可以在同一时钟周期内发射的相关指令的可能组合，都必须加以考虑。这种组合数与一个周期内可发射指令数的平方成正比，所以在尝试突破每时钟周期执行4条指令的速度时，发射步骤可能会成为一个瓶颈。

对于发射指令，rd1和rd2是目的地，rs1、rs2和rt2是源（载入指令仅有一个源），r1和r2是分配的保留站，b1和b2是指定的ROB项目。RS是保留站数据结构。RegisterStat是寄存器数据结构，Regs表示实际寄存器，ROB是重排序缓冲区数据结构。注意，这一逻辑的正常运行需要指定重排序缓冲区项目，还有，别忘了所有这些更新是在单个时钟周期内并行完成的，不是顺序执行！

我们可以推广表3-12的细节，以描述在动态调度超标量中更新发射逻辑和保留表的基本策略，可以在一个时钟周期内发射多达n条指令，如下所示。

1. 为可能在下一个发射包中发射的每条指令指定保留站和重排序缓冲区。这一指定过程可以在知道指令类型之前完成，只需要使用n个可用重排序缓冲区项依次为发射包中的指令预先分配重排序缓冲区项目，并确保有足够的保留站可用于发射整个包（无论包中包含多少指令）即可。通过限制一个给定类别的指令数目（比如，一个浮点运算、一个整数运算、一个载入指令、一个存储指令），就可以预告分配必要的保留站。如果没有足够的保留站可用，比如，当程序中接下来的几条指令都是同一种指令类型时），则将这个包分解，仅根据原始程序顺序，发射其中一部分指令。包中的其余指令可以放在下一个发射包中。
2. 分析发射包中指令之间的所有相关。
3. 如果包中的一条指令依赖于包中的先前指令，则使用指定的重排序缓冲区编号来更新相关指令的保留表。否则，使用已有保留表和重排序缓冲区信息更新所发射指令的保留表项。当然，由于所有这些都要在一个时钟周期中并行完成，所以使上述操作变得非常复杂。

在流水线的后端，必须能够在一个时钟周期内完成和提交多条指令。由于可以在同一时钟周期中实际提交的多条指令必须已经解决了相关性问题，所以这些步骤要比发射问题稍容易一些。从性能的角度来看,我们可以用一个示例来说明这些概念是如何结合在一起的。

考虑以下循环在两发射处理器上的执行情况，它会使整数数组的所有元素递增，一次没有推测，一次进行推测:

Loop:   LD      R2,0(R1)      ; R2=array element
        DADDIU  R2,R2,#1      ; increment R2 
        SD      R2,0(R1)      ; store result
        DADDIU  R1,R1,#8      ; increment poi nter
        BNE     R2,R3, LOOP   ;branch if not last element

假定有独立的整数功能单元用于有效地址计算、ALU运算和分支条件求值。给出这个循环在两种处理器上前3次迭代的控制表。假定可以在每个时钟周期内提交2条任意类型的指令。

表3-13和表3-14给出了一个两发射动态调度处理器在有、无推测情况下的性能。在本例中，分支是一个关键的性能限制因素，推测会很有帮助。推测处理器中的第三分支在时间周期13中执行，而在非推测流水线中是在时钟周期19中执行。由于非推测流水线上的完成速率很快就会落在发射速率的后面，所以在再发射几个迭代之后，非推测流水线将会停顿。如果允许载入指令在决定分支之前完成有效地址计算，就可以提高非推测处理器的性能，但除非允许推测存储器访问，否则这一改进只会在每次迭代中获得一个时钟周期。

注意，跟在BNE后面的LD不能提前开始执行，因为它必须等待分支结果的判断。这种类型的程序（带有不能提前解决的数据相关分支）展示了推测的威力。将用于地址计算、ALU运算和分支条件求值的功能单元分离开来，就可以在同一周期中执行多条指令。表3-14显示的是这个例子带有推测功能
的版本。

这个例子清楚地表明，推测方法在存在数据相关分支时可以带来一些好处，而在没有这种分支时会限制性能。但是，这种好处依赖于分支预测的准确性。错误预测不会提高性能，事实上，它通常会有损于性能，而且后面将会看到，它会极大地降低能耗效率。

用于指令传送和推测的高级技术

在高性能流水线中，特别是在多发射流水线中，仅仅很好地预测分支还不够；实际上还得能够提高带宽的指令流。在最近的多发射处理器中，所谓高带宽发射流意味着每个时钟周期要提交4~8条指令。我们首先研究提高指令提交带宽的方法，然后再转而研究在实现高级推测技术中的一组关键问题，包括寄存器重命名的应用与重排序缓冲区、推测的积极性和一种称为值预测的技术，它尝试预测计算的结果，可以进一步增强ILP。

提高指令提取带宽

多发射处理器需要每个时钟周期提取的平均指令数目至少等于平均吞吐量。当然，提取这些指令需要有足够宽的路径能够连向指令缓存，但最重要的部分还是分支的处理。在本节，我们将研究两种处理分支的方法，然后讨论现在处理器如何将指令预测和预取功能结合在一起。

分支目标缓冲区

为了减少这个简单的五级流水线以及更深流水线的分支代价，必须知道尚未译码的指令是不是分支，如果是分支，则需要知道下一个程序计数器(PC)应当是什么。如果这条指令是一个分支，而且知道下一个PC应当是什么，那就可以将分支代价降为零。分支预测缓存中存储着一条分支之后下一条指令的预测地址，这一缓存被称为分支目标缓冲区或分支目标缓存。图3-7给出了一个分支目标缓冲区。

图3-7分支目标缓冲区。将所提取指令的PC与第一列中存储的一组指令地址进行匹配，这组地址代表的是已知分支的地址。如果PC与其中一项匹配，则所提取的指令为被选中的分支，第二个字段——预测的PC包含了对该分支之后下一个PC的预测值。会立即在该地址处开始提取指令。第三个字段是可选字段，可用于附加的预测状态位

由于分支目标缓冲区中预测下一条指令地址，并在对该指令译码之前把它发送出去，所以必须知道所提取的指令是否被预测为一条选中分支指令。如果所提供指令的PC与预测缓冲区中的一个地址匹配，则将相应的预测PC用作下一个PC。这种分支目标缓冲区的硬件基本上与缓存硬件相同。

如果在分支目标缓冲区中找到一个匹配项，则立即在所预测的PC处开始提取指令。注意，与分支预测目标不同的是，由于在知道一条指令是否为分支之前就要将预测到的PC发送出去，所以预测项必须与这一指令匹配。如果处理器没有查看这一项是否与这个PC匹配，那么就会为不是分支的指令发送错误的PC，导致性能恶化。我们只需要在分支目标缓冲区中存储预测选中的分支，这是因为未被选中的分支应当直接提取下一条顺序指令，就好像它不是分支指令一样。

图3-8显示了在为简单的五级流水线使用分支目标缓冲区时的步骤。从这个图中可以看出，如果在缓冲区中找到了分支预测项，而且预测正确，那就没有分支延迟。否则，至少存在两个时钟周期的代价。我们在重写缓冲区项目时通常会暂停指令提取，所以要处理错误预测与缺失是一个不小的难题。因此，我们希望快速完成这一过程，将代价降至最低。为了评估一个分支目标缓冲区的工作情况，必须首先判断所有可能情景中的代价。表3-15给出了一个简单五级流水线的相关信息。

如果一切都预测正确，而且在目标缓存中找到该分支，那就没有分支代价。如果分支预测错误，那代价就等于使用正常信息更新缓冲区的一个时钟周期(在此期间不能提取指令)，在需要时，还有一个时钟周期用于重新开始为该分支提取下一个正确指令。如果这个分支没有找到，或未被选中，那代价就是两个周期，在此期间会更新缓冲区。

假定各个错误预测的代价周期如表3-15所示，判断一个分支目标缓冲区的总体分支代价。关于预测准确率和命中率作以下假设:

• 预测准确率为90%（对于缓冲区中的指令）；
• 缓冲区中的命中率为90%（对于预测选中的分支）。

通过研究两个事件的概率来计算代价，一个事件是预测分支将被选中但最后未被选中，另一个事件是分支被选中，但未在缓冲区中找到。这两个事件的代价都是两个周期。

概率（分支在缓冲区中，但未被选中）= 缓冲区命中率 x 错误预测比例 = 90% x 10% = 0.09

概率（分支不在缓冲区中，但被实际选中）= 10%

分支代价=(0.09 + 0.10) x 2.

分支代价=0.38

这一代价略低于延迟分支的分支代价，大约为每个分支0.5个时钟周期。记住，当流水线长度增加从而导致分支延迟增加时，通过动态分支预测得到的性能改善也会随之增加；此外，使用更准确的预测器也会获得更大的性能优势。现代高性能处理器的分支错误预测代价大约为15个时钟周期量级，显然，准确预测是非常关键的！

分支目标缓冲区的一种变体是存储一个或多个目标指令，用于作为预测目标地址的补充或替代。这一变体有两个潜在好处。第一，它允许分支目标缓冲区访问花费的时间长于连续两次指令提取之间的时间，从而可能允许采用更大型的分支目标缓冲区。第二，通过缓存实际目标指令可以让我们执行一种称为分支折合（branch folding）的优化方法。分支折合可用于实现0时钟周期的无条件分支，有时可以实现0时钟周期的条件分支。

考虑一个分支目标缓冲区，它缓冲来自预测路径的指令，可以用无条件分支的地址来访问。无条件分支的唯一作用就是改变PC。因此，当分支目标缓冲区发出命中信号并指出该分支是无条件分支时，流水线只需要将分支目标缓冲区中的指令代替从缓存中的返回的指令（它是一个无条件分支）。如果处理器在每个周期发射多条指令，那么缓冲区需要提供多条指令，以获得最大好处。在一些情况下，有可能消除条件分支的成本。

返回地址预测器

当我们试图提高推测的机会和准确性时，就面临着预测间接跳转的挑战，也就是说跳转到那些在运行时变化的目标地址。尽管高级语言程序会为间接过程调用、选择或case语句、FORTRAN计算的goto语句等生成此类跳转，但大多数间接跳转都源于过程的返回操作。对于诸如C++和Java之类的面向对象的语言，过程返回操作甚至还要频繁。因此，将重点放在过程返回操作上似乎是恰当的。

尽管过程返回操作可以用分支目标缓冲区预测，但如果从多个地方调用这个进程，而且来自一个地方的多个调用在时间方面比较分散，那这种预测方法的准确性会很低。例如，在SPECCPU9S中，一个主动分支预测器对于此类返回分支所能达到的准确率不足60%。为了解决这一问题，一些设计使用了一个小型的返回地址缓冲区，它的工作方式相当于一个栈。这种结构缓存最近的返回地址：在调用时将返回地址压入栈中，在返回时弹出一个地址。如果缓存足够大（也就是与最大调用深度相等），它就能准确地预测过程返回操作。图3-9给出了这样的返回缓冲区在进行许多SPEC CPU95基准测试时的性能，缓冲区的元素数目为0~16个。Intel Core处理器和AMD Phenom处理器都有返回地址
预测器。

作为栈运行的返回地址缓冲区在进行大量SPEC CPU95基准测试时的预测准确率。这一准确率是正确预测返回地址所占的比例。若缓冲区中有0项，意味着使用标准分支预测。由于调用深度通常不是很大(当然也有一些例外），所以中等大小的缓冲区就可以取得很好的效果。使用一种改进机制来防止缓存返回地址出现错误

集成指令提取单元

为了满足多发射处理器的要求，近来的许多设计人员选择实现一个集成指令提取单元，作为独立的自主单元，为流水线的其余部分提供指令。实际上，这是因为他们意识到：由于多发射的复杂性，不能再将取指过程视为简单的单一流水级。最近的设计已经开始使用集成了多种功能的集成指令提取单元，包括以下这些功能。

1. 集成分支预测——分支预测器变为指令提取单元的组成部分，它持续预测分支，以驱动提取流水线。
2. 指令预取——为了在每个时钟周期内提交多条指令，指令提取单元可能需要提前提取指令。这一单元自主管理指令的预取，把它与分支预测结合在一起。
3. 指令存储器访问与缓存——在每个时钟周期提取多条指令时会遇到不同的复杂性，包括：提取多条指令可能需要访问多个缓存行，这是一个难题。指令提取单元封装了这一复杂性，尝试使用预取来隐藏跨缓存模块的成本。指令提取单元还可以提供缓存功能，大体充当一个按需单元，用于根据需要向发射级提供相应数量的指令。

几乎所有高端处理器现在都使用了一个独立的指令提取单元，通过一个包含未完成指令的缓冲区与流水线的其余部分连接在一起。

推测：实现问题与扩展

本节，我们将研究涉及推测设计权衡的4个问题，首先从寄存器重命名开始，这一方法经常被用来替代重排序缓冲区。然后讨论控制流推测的一-个重要扩展: 一种被称为值推测的思想。

推测支持：寄存器重命名与重排序缓冲区

ROB（重排序缓冲区）的一种替代方法是明确使用更大的物理寄存器集，并与寄存器重命名方法结合。这一方法以Tomasulo算法中使用的重命名为基础，并对其进行了扩展。在Tomasulo算法中，在执行过程的任意时刻，体系结构可见的寄存器(R0，…，R31和F0，…, F31）都包含在寄存器集和保留站的某一组合中。在添加了推测功能之后，寄存器值还会临时保存在ROB中。在任一情况下，如果处理器在一段时间内没有发射新指令，所有现有指令都会提交，寄存器值将出现在寄存器堆中，寄存器堆直接与在体系结构中可见的寄存器相对应。

在寄存器重命名方法中，使用物理寄存器的一个扩展集来保存体系结构可见寄存器和临时值。因此，扩展后的寄存器取代了ROB和保留站的大多数功能；只需要一个队列来确保循序完成指令。在指令发射期间，一种重命名过程会将体系结构寄存器的名称映射到扩展寄存器集中的物理寄存器编号，为目的地分配一个新的未使用寄存器。WAR和WAR冒险通过目标寄存器的重命名来避免，在指令提交之前，保存指令目的地的物理寄存器不会成为体系结构寄存器，所以也解决了推测恢复问题。重命名映射是一种简单的数据结构，它提供当前与某个指定体系结构寄存器相对应的寄存器的物理寄存器编号，在Tomasulo算法中，这一功能由寄存器状态表完成。在提交指令时，重命名表被永久更新，用于指示一个物理寄存器与实际体系结构寄存器相对应，从而有效地完成对处理器状态的更新。尽管在采用寄存器重命名时并不需要ROB，但硬件仍然必须在一个类似于队列的结构中跟踪信息，并严格按照顺序来更新重命名表。

与ROB方法相比，重命名方法的一个优点是简化了指令提交过程，它只需要两个简单操作：

• 记录体系结构寄存器编号与物理寄存器编号之间的映射不再是推测结果；
• 释放所有用于保存体系结构寄存器“旧”值的物理寄存器。在采用保留站的设计中，当使用一个保留站的指令完成执行后，该保留站会被释放，与一个ROB项目对应的指令提交之后，该ROB项目也被释放。

在采用寄存器重命名时，撤消寄存器分配的工作要更复杂一些，这是因为在释放物理寄存器之前，必须知道它不再与体系结构寄存器相对应，而且对该物理寄存器的所有使用都已完成。物理寄存器与体系结构寄存器相对应，直到该体系结构寄存器被改写为止，此时将使重命名表指向其他位置。也就是说，如果没有重命名项指向一个特定的物理寄存器，那它就不再对应于体系结构寄存器。但是，对该物理寄存器的使用可能仍未结束。处理器可以通过查看功能单元队列中所有指令的源寄存器说明符。如果一个给定物理寄存器没有显示为源寄存器，而且它也没有被指定为体系结构寄存器，那就可以收回该寄存器，重新进行分配。

或者，处理器也可以一直等待，直到对同一体系结构寄存器执行写入操作的另一指令提交为止。此时，对旧值的使用可能都已经完成了。尽管这种方法对物理寄存器的绑定时间可能要稍长于必要时间，但它的实现非常容易，在最近的超标量中得到了应用。

读者可能会问到的一个问题是: 如果寄存器一直都在变化， 那要如何知道哪些寄存器是体系结构寄存器呢？在程序运行的大多数时间内，这是无所谓的。当然，在某些情况下，另一个进程（比如操作系统）必须知道特定的体系寄存器的内容到底在什么位置。为了理解如何提供这一功能，假定处理器在一段时间内没有发射指令。流水线中的所有指令最终都会提交，体系结构可见寄存器与物理寄存器之间的映射变得稳定。这时，物理寄存器的子集包含体系结构可见寄存器，任何未与体系结构寄存器关联的物理寄存器的都不再需要。从而可以很轻松地将体系结构寄存器移到物理寄存器的一个固定子集中，从而可以将这些值发送给另一进程。

寄存器重命名和重排序缓冲区都继续在高端处理器中使用，这些高端处理器现在能够同时运行40或50条指令（包括在缓存中等待的载入指令和存储指令）。无论是使用重命名还是重排序缓冲区，动态调度超标量的关键复杂性瓶颈仍然在于所发射的指令包中包含相关性的情景。具体来说，在发射一个发射包中的相关指令时，必须使用它们所依赖指令的指定虚拟寄存器。在采用寄存器重命名发射指令时，所部署的策略可以类似于采用重排序缓冲区进行多发射时使用的策略，如下所示。

1. 发射逻辑预先为整个发射包保留足够的物理寄存器（比如，当每个指令最多有一个寄存器结果时，为四指令包预留4个寄存器）。
2. 发射逻辑判断包中存在什么样的相关。如果包中不存在相关，则使用寄存器重命名结构来判断哪个物理寄存器保存着（或将会保存）指令所依赖的结果。如果包中指令都不依赖于先前发射包中的结果，寄存器重命名表中将拥有正确的寄存器编号。
3. 如果一条指令依赖于在该发射包中排在前列的某条指令，那么将使用在其中存放结果的预留物理寄存器来为发射指令更新信息。

注意，就像在重排序缓冲区中一样，发射逻辑必须在一个周期内判断包内相关性，并更新重命名表，而且和前面一样，当每个时钟处理大量指令时，这种做法的复杂度就会成为发射宽度中的一个主要限制。

推测的代价

推测的重要优势之一是能够尽早发现那些本来会使流水线停顿的事件，比如缓存缺失。但是，这种潜在优势也带来一个潜在的重大不利条件。推测不是免费的，它需要时间和能量，错误预测的恢复过程还会进一步降低性能。此外，为了从推测中获益，需要支持更高的指令执行速率，为此，处理器必须拥有更多的资源，而这些资源又会占用硅面积、消耗功率。最后，如果推测导致异常事件的发生，比如缓存缺失或转变旁视缓冲区（TLB）缺失，而没有推测时本来不会发生这种事件，那推测造成重大性能损失的可能性就会增大。

为了在最大程度上保持优势、减少不利因素，大多数具有推测的流水线都仅允许以推测模式处理低成本的异常事件（比如，第一级缓存缺失）。如果发生成本高昂的异常事件，比如第二级缓存缺失或TLB缺失，处理器将会一直等待，等引发该事件的指令不再具有推测性时再来处理这一事件。尽管这样会使一些程序的性能稍有降低，但对于其他一些程序，尤其是会频繁出现此类事件且分支预测效果不佳的程序，可以避免性能大幅降低。

在20世纪90年代，推测的潜在不利因素还不是特别明显。随着处理器的发展，推测的实际成本变得越来越明显，宽发射和推测的局限性也变得更为突出。

多分支预测

在本章已经研究过的示例中，在必须推测一个分支之前， 已经有可能解决另一个分支。有三种情景可以通过同时推测多个分支获益：

• 分支出现频率非常高；
• 分支高度汇集；
• 功能单元中的延迟很长。

在前两种情况下，要实现高性能可能意味着对多个分支进行推测，每个时钟周期甚至可能处理一条以上的指令。数据库程序和其他结构化程度较低的整数计算经常呈现这些特性，使多个分支的预测变得非常重要。同样，功能单元中的延迟很长时，也会增加对多个分支进行推测的重要性，用于避免因为流水线延迟过长而造成的停顿。

对多个分支进行推测会使推测恢复过程变得稍微复杂,但在其他方面比较简单。到2011年，还没有处理器能够将推测与每个时钟周期内处理多条分支完全结合在一起， 从性能与复杂性、功率的对比来看，这样做的成本可能有些过高了。

推测与能耗效率的挑战

推测对能耗效率有什么影响呢?乍看起来，有人可能会说推测的使用总是降低能耗效率，因为只要推测错误，就会以下面两种方式消耗更多的性能。

1. 对某些指令进行了推测，但却不需要它们的结果，这些指令会为处理器生成多余工作，浪费能量。
2. 撤销推测，恢复处理器的状态，以便在适当的地址处继续执行，这些操作都会多消耗一部分能量，在没有推测时是不需要消耗这部分能量的。

当然，推测的确会增大功率消耗，如果我们能够控制推测，那就有可能对成本进行测量（至少可以测量动态功率成本）。但是，如果推测过程缩短的执行时间多于它增加的平均功耗，那消耗的总能量仍然可能减少。

因此，为了了解推测对能耗效率的影响，我们需要研究推测生成非必要任务的频繁程度。如果会执行非常大量的非必要指令，那推测就不大可能大幅缩短运行时间！图3-10给出了由于错误预测而执行的指令比例。可以看到，在科技代码中，这一比例很小，而在整数代码中则很高（平均为大约30%）。因此，对于整数应用程序来说，推测的能耗效率不会很高。设计人员可以避免推测，尝试减少错误预测，或者考虑采用新方法，比如仅对那些已经知道可预测性很强的分支进行推测。

值预测

一种提高程序中可用ILP数目的技术是值预测。值预测尝试预测一条指令可能生成的值。显然，由于大多数指令在每次执行时都生成一个不同值（至少是一组取值中的一个不同值），所以值预测的成功率可能非常有限。但是，也有一些特定的指令，可以很轻松地预测它们的结果值，比如从常数池中进行载入的载入指令，或者载入一个不经常变化的取值。此外，如果一条指令只是从一组很少的取值中选择一个，那就有可能结合其他程序行为来预测结果值。

如果值预测能够显著提高可用ILP的数量，那它就是有用的。当某个值被用作一串相关运算的源数据时（比如一个载入操作），这种可能性就很大。因为值预测是用来提高推测能力的，而且错误预测会有不利的性能影响，所以预测的准确性非常关键。

有一种比较简单的与值预测相关的较早思想已经得到了应用，那就是地址别名预测。地址别名预测是一种非常简单的技术，用来预测两个存储指令或者一个载入指令与一个存储指令是否引用同一存储器地址。如果这样两条指令没有引用同一地址，那就可以放心地交换它们的顺序。否则，就必须等待，直到知道这些指令访问的存储器地址为止。因为我们不需要实际预测地址值，只需要知道这些值是否冲突即可，所以这种预测更稳定，也更简单。

ILP 局限性的研究

在20世纪60年代出现第一批流水化处理时，就开始通过开发ILP来提高性能。这一节的数据还为我们提供了一种方法，用来验证本章所讨论思想的价值，这些思想包括存储器消歧、寄存器重命名和推测。

硬件模型

为了了解ILP可能有哪些局限性，我们首先需要定义一种理想处理器。在理想处理器中，去除了对ILP的所有约束条件。在这样一个处理器中， 对ILP仅有的一些限制是由通过寄存器或存储器的实际数据流带来的。对理想或完美处理器作出以下假设。

1. 无限寄存器重命名——有无限个虚拟寄存器可供使用，因此避免了所有WAW和WAR冒险，可以有无数条指令同时执行。
2. 完美分支预测——分支预测非常完美。所有条件分支都被准确预测。
3. 完美跳转预测——所有跳转（包括用于返回和计算跳转的跳转寄存器）都被完美预测。与完美分支预测相结合，这相当于拥有了一种处理器，它可以进行完美预测，并拥有一个极大的可执行指令缓冲区。
4. 完美存储器地址别名分析——所有存储器地址都已确切知道，如果载入指令与存储指令的地址不同，可以将载入指令移到存储指令之前。注意，这就实现了完美的地址别名分析。
5. 完美缓存——所有存储器访问都占用一个时钟周期。在实践中，超标量处理器通常会使用大量ILP，隐藏了缓存缺失，使这些结果变得非常乐观。

假设（2）与假设（3）消除了所有控制相关。而假设（1）和假设（4）消除了除真数据相关之外的所有数据相关。这4条假设结合在起来，就意味着：对于程序执行中的任何一条指令，在它所依赖的先前指令执行完毕之后，可以将该指令调度到紧随其后的时钟周期上。根据这些假设，甚至有可能将程序中最后一条动态执行的指令调度到最前面的时钟周期上！因此，这一组假设同时包含了控制推测与地址推测，在实现时把它们当作是完美的。

我们首先研究一个可以同时发射无数条指令的处理器，能够提前看到运算过程中的任意指令。在我们研究的所有处理器型号中，对于一个时钟周期能够执行哪些类型的指令没有限制。在可以发射无限条指令时，这意味着在一个时钟周期中可能有无数条载入指令或存储指令。此外，所有功能单元的延迟都假定为一个时钟周期，所以任何相关指令序列都可以在连续周期上发射。如果延迟长于一个周期，尽管不会降低任意时刻正在执行的指令数目，但可能会降低每个周期发射的指令数目。（任意时刻正在执行的指令通常被称为是在in flight。）

为了测量可用并行，可以使用标准MIPS优化编译器来编译和优化一组程序。对这些程序交付运行，生成一个指令与数据引用踪迹。然后尽早调度踪迹中的所有指令，仅受数据相关的限制。由于使用了踪迹，所以很容易实现完美分支预测和完美别名分析。利用这些机制，可以大大提前对这些指令的调度，在没有数据相关的大量指令之间进行移动，由于可以完美预测分支，所以这些指令也包括分支指令在内。

图3-11显示了6个SPEC92基准测试的平均可用并行度数目。本节中，始终以平均指令发射率为指标来测试并行。注意，所有指令的延迟为一个时钟周期；延迟较长时会减少每个时钟的平均指令数。这些基准测试中有3个（fppp、doduc和tomcatv）是浮点操作密集的基准测试，另外3个为整数程序。浮点基准测试中有两个（fppp和tomcatv）有大量并行，可供向量计算机或多处理器开发（不过，由于已经对代码进行了一些人工转换，所以fpppp 中的结构十分杂乱）。doduc程序拥有大量并行，但这些并行不会在简单的并行循环中出现，这一点与fpppp和omcatv中不同。程序li是-个拥有许多短相关的LISP解释程序。

图3-11 一个完美处理器中运行6个SPEC92基准测试时的可用ILP。前3个程序是整数程序，后3个是浮点程序。浮点程序中循环数量很多，有大量循环级并行

可实现处理器上ILP的局限性

本节中，我们将研究一些处理器的性能，具体来说，我们将假定以下固定属性。

1. 每个时钟周期最多发射64条指令、没有发射限制，或者是2011年最宽处理器总发射宽度的10倍以上。后面将会讨论，超大发射宽度对时钟频率、逻辑复杂度和功率产生的实际影响可能才是对ILP开发的最重要限制。
2. 一个竞赛预测器，拥有1000项和一个16项返回预测器。这个预测器可以与2011年的最佳预测器相媲美；这个预测器不是主要瓶颈。
3. 对于动态完成的存储器引用能够完全消除歧义——这项要求是比较高的，但当窗口较小时（因此，发射速度和载入存储缓冲区也较小），或者通过地址别名预测，还是有可能做到的。
4. 具有64个附加整数寄存器和64个浮点寄存器的寄存器重命名，这一数目要略小于2011年的最强劲处理器。

图3-12给出了这一配置在窗口大小变化时的结果。这一配置比任何已有实现方式都要复杂和昂贵，特别是在指令发射数方面，它要比2011年任意处理器上的最大可用发射数大10倍以上。不过，它对未来实施方式所能生成的内容给出了一个非常有用的范围。由于另一个原因，这些图形中的数据可能是非常乐观的。在64条指令中没有发射限制：它们可能都是存储器引用。在不远的将来，甚至没有人会在处理器中设计这一功能。遗憾的是，用合理的发射限制来界定处理器的性能是十分困难的，这不仅是因为存在各种各样的可能性，而且发射限制的存在需要用准确的指令调度器来评估并行，在研究具有大量发射指令的处理器时，其成本会非常昂贵。

另外还请记住，在解读这些结果时，没有考虑缓存缺失和长于1个时钟周期的延迟，这两个因素都可能产生严重影响!

图3-12：对于各种整数与浮点程序，每个时钟周期发射64个任意指令时，可用并行数随窗口大小的变化情况。尽管重命名寄存器的数目少于窗口大小，但所有操作的延迟为一个时钟周期 、重命名寄存器的数目等于发射宽度，这一事实使处理器能够在整个窗口中开发并行。在实际实现中，必须平衡窗口大小和重命名寄存器的数目，以防止这些因素中的某一个过度限制发射速率

图3-12中最令人吃惊的观测结果是:考虑到以下所列的实际处理器约束条件，窗口大小对整数程序的影响不像对浮点程序那么严重。这一结果指向了这两种程序之间的关键区别。两个浮点程序中能够利用循环级并行，这意味着可以开发的ILP数目较高，而对于整数程序，其他因素（比如分支预测、寄存器重命名、并行较少，等等）都是重要的限制情况。从万维网和云计算于20世纪90年代中期开始爆发式发展以来，人们增加了对整数性能的重视，所以这一观察结果非常关键。事实上，在过去10年里，大多数市场增长（事务处理、Web 服务器等）都依赖于整数性能，而不是浮点性能。

由于在实际硬件设计中，提高指令速率具有一定的难度，所以设计人员面临着一项挑战：决定如何更好地利用集成电路上有限的可用资源。是采用具有更大缓存和更高时钟速率的较简单处理器，还是将重点放在具有较慢时钟和较小缓存的指今级并行上，这是最重要的设计权衡之一。下面的例子演示了这些挑战。

考虑以下3种假设的非典型处理器，我们将在上面运行SPEC gcc基准测试。

1. 一个简单的MIPS双发射静态流水线，其时钟速率为4 GHz，所实现的流水线CPI为0.8。这一-处理器的缓存系统每条指令发生0.005次缺失。
2. 一个双发射MIPS处理器的深度流水线版本，缓存稍小一些，时钟速率为5 GHz。处理器的流水线CPI为1.0，缓存较小，平均每条指令生成0.0055次缺失。
3. 一个推测超标量处理器，具有一个64项窗口。它能实现的发射率为这一窗口大小理想发射率的一半。这一处理器的缓存最小，每条指令产生0.01次缺失，但通过动态调度可以隐藏每次缺失25%的缺失代价。这个处理器的时钟为2.5 GHz。

假定主存储器时间（这一时间决定了缺失代价）为50ns。判断这3种处理器的相对性能。

首先，我们使用缺失代价和缺失率信息计算每一种配置中缓存缺失对CPI的影响。计算公式如下:

缓存CPI=每条指令的缺失数x缺失代价

我们需要为每个系统计算缺失代价:

缺失代价=存储器访问时间/时钟周期

这3种处理器的时钟周期时间分别为250 ps、200 ps和400 ps。因此，缺失代价是:

缺失代价1 = 50ns / 250ps = 200周期

缺失代价2 = 50ns / 250ps = 250周期

缺失代价3 = 0.75x50ns / 400ps = 94周期

为每一缓存应用此公式:

缓存CPI1=0.005 x 200=1.0

缓存CPI2=0.0055 x 250=1.4

缓存CPI3=0.01 x 94=0.94

除了处理器3之外，我们知道了其他处理器的流水线CPI影响；它的流水线CPI给出如下:

流水线CPI3 = 1 / 发射速率 = 1 / (9x0.5) = 1 / 4.5 = 0.22

现在可以通过添加流水线和缓存CPI因素来求出每个处理器的CPI:

• CPI1=0.8+1.0=1.8
• CPI2=1.0+1.4=2.4
• CPI3=0.22+0.94=1.16

由于这是同一体系结构，所以可以对比指令执行速度以确定相对性能:

指令执行速度=CR/CPI

指令执行速度1=4000MHz/1.8=2222 MIPS

指令执行速度2=5000MHz/2.4=2083 MIPS

指令执行速度3=2500MHz/1.16=2155 MIPS

在这个例子中，简单的双发射静态超标量看起来是最好的。在实践中，性能取决于CPI和时钟频率两项假设。

超越本研究的局限

和所有极限研究一样，即使在完美推测处理器中也会存在的局限性；在一或多种现实模型中存在的局限性。当然，第一类中的所有局限性也适用于第二类。适用于完美模型的最重要局限性包括以下几个。

（1）访问存储器的WAW和WAR冒险——这一研究通过寄存器重命名消除了WAW和WAR冒险，但却没有消除存储器使用中的冒险。尽管乍看起来，此类情况很少会出现（特别是WAW冒险），但它们的确会因为栈帧分配而出现。某种被调用过程重复利用栈中上一过程使用的存储器位置，这样可能会导致WAW和WAR冒险，造成不必要的限制。

（2）不必要的相关——在有无数个寄存器时，就可以消除真寄存器数据相关之外的所有其他数据相关。但是，由于递归或代码生成约定而造成的相关仍然会引入一些不必要的真数据相关。其中一个例子就是在一个简单的 for 循环中对于控制变量的相关。由于控制变量在每次循环迭代时都会递增，所以循环中包含至少一个相关。Wall 的研究中包含了数量有限的一些此类优化，但更积极地应用这些优化方式有可能增加ILP的数目。此外，特定的代码生成约定也会引入一些不必要的相关，特别是在使用返回地址窗口和栈指针寄存器时（它会在调用/返回序列中递增和递减）。Wall消除了返回地址寄存器的影响，但在链接约定中使用规模指针可能会导致“不必要的”相关。

（3）克服数据流限制——如果值预测的精度很高，那就可能克服数据流限制。显然，完美的数据值预测可以得到高效的无限并行，因为每个指令的每个值都可能提前预测得出。

对于不够完美的处理器，已经提出了几种可以发现更多ILP的思想。其中一个例子是沿多条路径进行推测。通过在多条路径上进行推测，可以降低错误恢复的成本、发现更多的并行。由于所需硬件资源呈指数增长，所以只有对有限个分支评估这一方案才有意义。

交叉问题：ILP方法与存储器问题

硬件推测 与软件推测

下面列出这些硬件密集的推测方法的一些权衡与局限性。

• 为了能够大范围进行推测，必须能够消除存储器引用的歧义。对于包含指针的整数程序，很难在编译时实现这一功能。在基于硬件的方案中，存储器地址的动态运行时消歧是使用前面介绍的Tomasulo算法的技术完成的。这一消歧功能可以在运行时把载入指令移到存储指令之后。对推测存储器引用的支持可以帮助克服编译器的保守性，但如果使用这些方法时不够仔细，那恢复机制的开销可能会大于它们所能带来的收益。
• 当控制流不可预测时，当基于硬件的分支预测优于在编译时完成的软件分支预测时，基于硬件的推测效果较佳。这些特性对于许多整数程序都是成立的。例如，一个好的静态预测器，对4个主要整数SPEC92程序的错误预测率大约为16%，而硬件预测器的错误预测率低于10%。因为当预测不正确时，推测错误的指令可能会拖慢计算速度，所以这一差别非常明显。因为这一差别而导致了一个结果：即使是静态调度的处理器中通常也会包含动态分支预测器。
• 即使对于被推测的指令，基于硬件的推测也能保持完全精确的异常模型。最近的基于软件的方法也添加了这一特殊支持，同样可以做到这一点。
• 基于硬件的推测不需要补充或记录代码，而那些雄心勃勃的软件推测机制则需要这一条件。
• 基于编译器的方法能够深人了解代码序列，从中获益，从而在代码调度方面要优于纯硬件驱动的方法。
• 对于一种体系结构的不同实现方式，采用动态调度的硬件推测不需要采用不同代码序列就能实现好的性能。尽管这一收益很难量化，但从长期来看，这一收益可能是最重要的。有意思的是，它曾经是设计IBM 360/91的动机之一。另一方面，最近的显式并行体系结构(比如IA-64)已经增加一定的灵活性，可以减少代码序列中固有的硬件相关。

在硬件中支持推测的主要缺点是需要更多、更复杂的硬件资源。必须针对两个方面对这一硬件成本进行评估，一是与软件方法中编译器的复杂性相对比，一是与依赖此类编译器的处理器简化程度相对比。

一些设计人员已经尝试将动态方法和基于编译器的方法结合起来，以期达到两种方法的最佳效果。这种组合方式可以产生一些有趣但不够明确的交互。例如，如果将条件移动与寄存器重命名结合起来，就会出现一种微妙的副作用。由于之前已经在指令流水线中更改了目标寄存器的名称，所以一个被撤消的条件移动操作仍然会向目标寄存器中复制一个值。这种微妙的交互使设计与验证过程都变得非常复杂，还可能会降低性能。

迄今为止，在采用软件方法支持ILP和推测的计算机中，Intel Itanium处理器是最强大的。它没有像设计人员所希望的那样提供硬件支持,对于通用、非科学代码尤为如此。意识到3.10节讨论的困难之后，设计人员开发ILP的热情已经减退，因此，在大多数体系结构最终采用的硬件方案中，发射速率为每个时钟周期发射3~4条指令。

推测执行与存储器系统

在一个支持推测执行或条件指令的处理器中，自然可能生成一些在没有 推测执行时就不会用到的无效地址。如果激发了保护异常，那这不仅是一种错误行为，而且推测执行的收益还可能会被错误异常的开销抵消。因此，存储器系统必须识别推测执行的指令和条件执行的指令,并抑制相应的异常。

此类指令可能会导致缓存因缺失而停顿，这些不必要的停顿仍然可能超过推测带来的收益，出于和前面类似的原因，我们不能允许这种现象的发生。因此，这些处理器必须与非阻塞缓存相匹配。

在实际中，由于L2缺失的代价非常大，所以编译器通常都仅对L1缺失进行推测。

多线程:开发线程级并行提高单处理器吞吐量

多线程是一个真正的交叉主题，它同流水线与超标量相关、与图形处理器相关，还与多处理器有关。利用多线程来隐藏流水线和存储器延迟，从而提高单处理器的吞吐量。

尽管使用ILP来提高性能具有很大的优势：它对编程人员是适度透明的，但我们已经看到，在某些应用程序中，ILP可能受到很大的限制或者难以开发。具体来说，当指令发射率处于合理范围时，那些到达存储器或片外缓存的缓存缺失不太可能通过可用ILP来隐藏。当然，当处理器停顿下来等待缓存缺失时，功能单元的利用率会激剧下降。由于人们在试图通过更多的ILP来应对很长的存储器停顿时，效果非常有限。

多线程技术支持多个线程以重叠方式共享单个处理器的功能单元。而与之相对的是，开发线程级并行(TLP)的更一般方法是使用多处理器，它同时并行运行多个独立线程。但是，多线程不会像多处理器那样复制整个处理器。而是在一组线程之间共享处理器核心的大多数功能，仅复制私有状态，比如寄存器和程序计数器。

要复制一个处理器核心中每个线程的状态，就要为每个线程创建独立的寄存器堆、独立的PC和独立的页表。存储器本身可以通过虚拟存储器机制共享，这些机制已经支持多重编程了。此外，硬件必须支持对不同线程进行较快速的修改；具体来说，线程切换的效率应当远远高于进程切换，后者通常需要数百个到数千个处理器周期。当然，为使多线程硬件实现性能改进，一个程序中必须包含能够以并发形式执行的多个线程（有时说这种应用程序是多线程的）。这些线程既可由编译器识别（通常是来自具有并行结构的语言），也可能由程序员识别。实现多线程的硬件方法主要有3种。细粒度多线程每个时钟周期在线程之间进行一次切换，使多个线程的指令执行过程交织在一起。这种交织通常是以轮询方式完成的，当时发生停顿的所有进程都会被跳过。在细粒度多线程情况下，当一个线程停顿时，哪怕这停顿只有几个周期，也可以执行其他线程中的指令，所以这种多线程的一个重要好处是它能够隐藏因为长、短停顿而导致的吞吐量损失。细粒度多线程的一个主要不足是它会减缓个体线程的执行速度，因为一个做好执行准备、没有停顿的线程可能会被其他线程的执行延迟。它用单个进程的性能损失（这里所说的性能是以延迟来衡量的）来换取多线程吞吐量的一致性。

粗粒度多线程的设计目的就是用来作为细粒度的替代选项。粗粒度多线程仅在发生成本较高的停顿时才切换线程，比如第2级或第3级缓存缺失时。通过这一变化， 只有当一个线程遇到成本高昂的停顿时才会发射其他线程的指令，这样就不再严格要求线程切换操作必须是无成本的，同时也大大降低了减缓任一线程执行速度的可能性。不过，粗粒度多线程也有一个严重不足：克服吞吐量损失的能力非常有限，特别是由于较短停顿导致的损失。这一局限性源于粗粒度多线程的流水线启动成本。由于采用粗粒度多线程的CPU仅发现来自单个线程的指令，所以当流水线发生停顿时，在新线程开始执行之前会出现“气泡”。由于这一启动开销，粗粒度多线程更多是用来应对那些成本超高的停顿，当发生此类停顿时，重新填充流水线的时间与停顿时间相比可以忽略不计。已经有几个研究项目对粗粒度多线程进行了探索，但现在的主流处理器中都还没有使用这一技术。

最常见的多线程实施方式称为同时多线程（SMT）。同时多线程是细粒度多线程的一种变体，它是在多发射、动态调度处理器的顶层实现细粒度多线程时自然出现的。和其他形式的多线程一样，SMT利用线程级并行来隐藏处理器中的长延迟事件，从而提高功能单元的利用率。SMT的关键在于认识到通过寄存器重命名和动态调度可以执行来自独立线程的多个指令，而不用考虑这些指令之间的相关性；这些相关性留给动态调度功能来处理。

图3-13从概念上给出了处理器在以下不同配置中开发超标量源的能力差异:

• 不支持多线程的超标量;
• 支持粗粒度多线程的超标量;
• 支持细粒度多线程的超标量;
• 支持同时多线程的超标量。

图3-13 4种不同方法在应用一个超标量处理器功能单元执行槽的表现状况。水平维度表示每个时钟周期中的指令执行能力。垂直维度代表时间周期序列。空白框（白色）表示该时钟周期的相应执行槽未被使用。灰色和黑色的阴影框对应多线程处理器中的4个不同线程。黑色框表示在不支持多线程的超标量中被占用的发射槽。SunT1和T2（akaNiagara）处理器是细粒度多线程处理器，而Intel Core i7 和IBM Power7 处理器使用SMT。T2有8个线程、Power7有4个、Intel i7有2个。在所有现有SMT中，每次只发射一个线程中的指令。SMT的区别在于：在后面决定执行哪条指令时不需要考虑相互之间的影响，可以在同-一个时钟周期执行来自几个不同指令的操作

在不支持多线程的超标量中，由于缺乏ILP（包括用于隐藏存储器延迟的ILP），所以发射槽的使用非常有限。由于L2和L3缓存缺失的长度原因，处理器在大多数时间内可能保持空闲。

在粗粒度多线程超标量中，通过切换到另一个利用处理器资源的线程来部分隐藏长时间的停顿。这一切换减少了完全空闲的时钟周期数。但是，在粗粒度多线程处理器中，仅当存在停顿时才会进行线程切换。由于新线程有一个启动时间，所以仍然可能存在一些完全空闲的周期。

在细粒度情况中，线程的交织可以消除全空槽。此外，由于每个时钟周期都会改变发射线程，所以可以隐藏较长延迟的操作。由于指令发射和执行联系在一起，所以线程所能发射的指令数目仅限于准备就绪的指令。当发射宽度较窄时，没有什么问题（某个时钟周期要么被占用，要么不被占用），这就是细粒度多线程在单发射处理器中能够完美运行的原因，SMT没有什么意义。事实上，在SunT2中，每个时钟周期会有两次发射，但它们来自不同线程。这样就不再需要实施复杂的动态调度方法，而是依靠更多线程来隐藏延迟。

如果在多发射动态调度处理器的顶层实现细粒度线程，所得到的结果就是SMT。在所有现有SMT实现方式中，尽管来自不同线程的指令可以在同一时钟周期内开始执行，但所有发射都来自一个线程，使用动态调度硬件来决定哪些指令已经准备就绪。尽管图3-13极大地简化了这些处理器的实际操作，但它仍然能够说明在发射宽度较宽的动态调度处理器中，一般多线程和SMT的潜在性能优势。

同时多线程的出现是因为深刻地认识到：动态调度处理器已经拥有支持这一方案所需要的大量硬件方案，包括大量虚拟寄存器。通过为每个线程添加专用的重命名表、保持独立的PC、支持提交来自多个不同线程的指令，也可以在乱序处理器上实现多线程。

细粒度多线程在Sun T1上的效果

在这一节，我们利用Sun T1处理器来研究多线程隐藏延迟的能力。T1 是Sun公司在2005年发布的-种细粒度多线程多核微处理器。人们之所以特别关注T1，是因为它几乎将全部重心都放在开发线程级并行（TLP）上，而不是用于开发指令级并行（ILP）。T1 不再强调对ILP的调度（就在此前不久，刚刚发布了更积极的ILP处理器），回归一种简单的流水线策略，着力开发TLP，使用多核和多线程技术来提高吞吐量。

每个T1处理器包含8个处理器核心，每个核心支持4个线程。每个处理器核心包括一个简单的六级、单发射流水线。T1使用细粒度多线程（但不是SMT），每个时钟周期切换到一个新的线程，在调度过程中，会跳过那些因为流水线延迟或缓存缺失而处于等待状态的空闲线程。只有在所有4个线程全部空闲或停顿时，处理器才会空闲。载入指令和分支指令都会导致一个长度为3个时钟周期的延迟，这一延迟只能由其他线程来隐藏。由于浮点性能不是T1的重点，所以它只提供了一组浮点功能单元，由所有8个核心共享。表3-16总结了T1处理器的各个特性。

T1多线程单核性能

T1把自己的重点放在TLP上，既在各个核心上实施了多线程，又在单个晶片上使用了多个简单核心。在这一节，我们将研究T1通过细粒度多线程提升单核心性能的效果。为了研究T1的性能，我们使用3种面向服务器的基准测试: TPC-C、SPECJBB （SPEC Java业务基准测试）和SPECWeb99。由于多个线程会增大单个处理器对存储器的需求，所以可能会使存储器系统过载，从而降低多线程的潜在收益。图3-14是TPC-C基准测试中，在每个核心执行1个线程和每个核心执行4个线程时缺失率及所观测到的缺失延迟的相对增长情况。由于存储器系统的争用增加，缺失率和缺失延迟都会增大。缺失延迟的增幅较小，表示存储器系统仍然有未用空间。

图3-14在TPC-C基准测试中，每个核心执行1个线程和每个核心执行4个线程时缺失率与缺失延迟的相对增长情况。这些延迟是指在一次缺失之后返回所请求数据的实际时间。在4线程情况中，其他线程的执行可能会隐藏这一延迟的大部分时间通过研究一个一般线程的行为，可以了解线程之间进行交互以及它们使核心保持繁忙状态的能力。图3-15给出了3种时钟周期所占的百分比：一种是有线程正在执行，一种是有线程准备就绪，但尚未执行，还有一种是线程没有准备就绪。注意，没有准备就绪并不意昧着拥有该线程的核心处于停顿状态，只有当所有4个线程都未准备就绪时，该核心才会停顿。

囹3-15 一般线程的状态细分。“正在执行”是指该线程在该时钟周期内发射了一条指令。“就绪但未被选中”是指它可以发射指令，但另一线程已被选中；“未就绪”是指该线程正在等待一个事件（例如，一次流水线延迟或缓存缺失）的完成线程未准备就绪可能是因为缓存缺失、流水线延迟（由于一些延迟较长的指令导致，比如分支、载入、浮点或整数乘/除）以及各种影响较小的因素。图3-16显示了这些不同原因的发生频率。在50% ~ 70%的时间里，线程未准备就绪是由缓存原因造成的，L1 指令缺失、L1数据缺失和L2缺失造成的影响大致相同。在SPECJBB中，由于流水线造成的潜在延迟（称为“流水
线延迟”）是最严重的，可能是由于它的分支频率较高所致。

图3-16 线程的未就绪原因细分。“其他”类别的原因是变化的。在TPC-C 中，存储器缓冲区满是最主要的因素；在SPEC-JBB中，原子指令是最主要的因素；而在SPECWeb99中，这两个因素都有影响

表3-17显示了每个线程的CPI和每个核心的CPI。由于T1是一种细粒度多线程处理器，每个核心有4个线程，当有足够的并行时，每个线程的理想有效CPI为4，这意味着每个线程占用每4个时钟周期中的1个周期。每个核心的理想CPI为1。2005年，在积极采用ILP的核心上运行这些基准测试的IPC就已经可以达到T1核心上观测到的类似数据。但是，与2005年更积极的ILP核心相比，T1核心的大小非常合适，这就是为什么T1拥有8个核心，而同一时期的其他处理器只提供了2~4个核心。因此，在2005年发布SunT1处理器时，它在处理TLP密集、存储器性能需求较高的的整数应用程序和事务处理工作负载时，具有最佳性能。

同时多线程在超标量处理器上的效果

一个关键问题是：通过实施SMT可以使性能提高多少？在2000 ~ 2001年研究这一问题时，研究人员认为动态超标量会在接下来的5年里大幅改进，每个时钟周期可以支持6~8次发射，处理器会支持推测动态调度、许多并行载入和存储操作、大容量主缓存、4~8种上下文，可以同时发射和完成来自不同上下文的指令。到目前为止，还没有处理器能够接近这一水平。因此，那些认为多编程工作负载可以使性能提高2 ~ 3倍的模拟研究结果是不现实的。实际中，现有的SMT实现只能提供2~4个带有取值的上下文，只能发射来自一个上下文的指令，每个时钟周期最多发射4条指令。其结果就是：由SMT获得的收益是非常有限的。

例如，在Pentium 4 Extreme中（在HP-Compaq服务器中实现）使用SMT时，运行SPECintRate基准测试时可以使性能提高1.01，运行SPECfpRate基准测试时可以使性能提高1.07。

我们可以使用一组多线程应用程序来研究在单个i7核心中使用SMT时获得的性能与能耗收益。我们使用的基准测试包括一组并行科学应用程序和一组来自DaCapo和SPEC Java 套件的多线程Java程序，在表3-18中对其进行了总结。Intel i7支持拥有两个线程的SMT.图3-17给出了SMT分别为关闭与开启状态时，在i7的-个核心上运行这些基准测试的性能比与能耗效率比。（我们绘制了能耗效率比曲线，能耗效率是能耗的倒数，所以和加速比一样，这个比值越大越好。）

尽管这两个Java基准测试的性能增益较小，但其加速比的调和均值为1.28。在采用多线程时，两个基准测试（pjbb2005和tradebeans）的并行非常有限。之所以包含这些基准测试是因为它们是典型的多线程基准测试，可以在一个指望提高性能的SMT处理器上运行，它们提升效果非常有限。PARSEC 基准测试的加速比要比全套Java基准测试好一些（调和均值为1.31）。如果省略tradebeans和pjbb2005， Java 工作负载的实际加速比（1.39）要比PARSEC基准测试好得多。

融会贯通: Intel Core i7和ARM Cortex-A8

本节，我们研究两种多发射处理器的设计：一种是ARM Cortex- A8核心，它是iPad中AppleA9处理器、Motorola Droid和iPhone 3GS、4中处理器的基础，另一种是Intel Core i7，一种高端、动态调度、推测处理器，主要为高端桌面应用程序和服务器应用程序设计。我们首先从较简单的处理器开始。

ARM Cortex-A8

A8是一种双发射、静态调度超标量处理器，具有动态发射检测功能，允许处理器在每个时钟周期内发射一条或两条指令。图3-18显示了13级流水线的基本流水线结构。A8使用一种动态分支预测器，具有一个512项2路组相联分支目标缓冲区和一个4K项全局历史缓冲区，由分支历史和当前PC进行索引。当出现分支目标缓冲区缺失时，则在全局历史缓冲区中进行预测，然后用预测值计算分支地址。此外，还维护一个8项返回栈，用于跟踪返回地址。一次错误预测会导致13个时钟周期的代价，用于刷新流水线。图3-19显示了指令译码流水线。利用循序发射机制，每个时钟周期最多可以发射两条指令。可以使用一种简单的记分板结构来跟踪何时能够发射一条指令。通过发射逻辑可以处理一对相关指令，当然，除非它们的发射方式能使转发路径消除两者之间的相关，否则会在记分板上对它们进行序列化。

图3-19 A8的5级指令译码。在第一级中，使用取指单元生成的PC（或者来自分支目标缓冲区，或者来自PC递增器）从缓存中提取大小为8字节的块。最多对两条指令进行译码，并将它们放在译码队列中；如果两条指令都不是分支，则将PC递增，为下一次取指做准备。一旦进入译码队列，则由记分板逻辑决定何时可以发射这些指令。在发射时，读取寄存器操作数；回想在简单的记分板中，操作数总是来自寄存器。寄存器操作数和操作码被发送到流水线的指令执行部分

图3-20显示了A8处理器的执行流水线。指令1或指令2可以进入这个载入存储流水线。在这些流水线之间支持完全旁路。ARM Cortex-A8流水线使用简单的双发射靜态调度超标量，可以在较低功率下实现相当高的时钟频率。与之相对，i7 使用一种相当积极的4发射动态调度推理流水线结构。

A8流水线的性能

由于A8采用双发射结构，所以它的理想CPI为0.5。可能会因为以下3种来源而产生流水线停顿。

（1）功能冒险，如果被选择同时发射的两个相邻指令使用同一功能流水线，就会出现功能冒险。由于A8是静态调度的，所以避免此类冲突是编译器的任务。如果不能避免此类冲突，A8在这个时钟周期内最多只能发射一条指令。

（2）数据冒险，在流水线的早期进行侦测，可能使两条指令停顿（如果第一条指令不能发射，第二条总是会被停顿），也可能是一对指令中的第二条指令停顿。编译器负责尽可能防止此类停顿。

（3）控制冒险，仅在分支预测错误时发生。

除了流水线停顿之外，L1和L2缺失都会导致停顿。

图3-21是影响Minnespec基准测试实际CPI的各项因素的估计值，我们在第2章曾经见过这些基准测试。可以看到，这一CPI的主要影响因素是流水线延迟，而不是存储器停顿。出现这一结果的部分原因是Minnespec的缓存印记要小于全套SPEC或其他大型程序。流水线停顿会造成性能大幅下降，深刻认识到这一点，可能对于决定将ARM Cortex-A9设计为动态调度超标量处理器起到了重要作用。A9和A8相似，每个时钟最多发射两条指令，但它使用了动态调度和推测。在一个时钟周期内可以开发执行多达4条未完成指令（2个ALU、1个载入存储或浮点/多媒体指令、1个分支指令）。A9使用一种功能更为强劲的分支预测器、指令缓存预取和非阻塞L1数据缓存。图3-22表明，在使用相同时钟频率和几乎相同的缓存配置时，A9的平均性能是A8的1.28倍。

图3-21对 ARM A8.上CPI各组成分量的估计值表明：流水线停顿是增大基本CPI的主要因素。eon值得专门一提，它完成基于整数的图形计算（光线跟踪），而且缓存缺失很少。由于大量使用乘法，计算非常密集，所以单个乘法流水线可能会成为主要瓶颈。这一估计值是利用L1和L2缺失率与代价来计算每个指令中因为L1和L2生成的停顿而获得的。从具体模拟器测得的CPI中减去这些估计值即可获得流水线停顿。流水线停顿包含所有这3种冒险再加上一些次要影响，比如路预测错误等

图3-22在时钟频率均为 1 GHz、L1 与L2缓存大小相同时，A9与A8的性能比表明: A9大约快1.28倍。两者都使用32KB主缓存和1MB次级缓存，A8采用8路组相关，A9使用16路组相联。A8处理器缓存中的块大小为64字节，A9为32字节。在图3-21的图题中曾经提及， eon 大量使用了整数乘法，动态调度与快速乘法流水线的组合使用显著提高了A9的性能。由于A9的L1块较小，所以twoif的缓存表现不佳，可能是由于这一因素， twoif 的速度略有减缓

Intel Core i7

i7采用非常积极的乱序推测微体系结构，具有较深的流水线，目的是通过综合应用多发射与高时钟速率来提高指令吞吐量。图3-23显示了i7流水线的整体结构。我们在研究流水线时，按照如下步骤，首先从指令提取开始，接下来是指令提交。

图3-23 Intel Core i7流水线结构，一同给出了存储器系统组件。总流水线深度为14级，分支错误预测成本为17个时钟周期。共有48个载入缓冲区和32个存储缓冲区。6个独立功能单元可以在同一时钟周期分别开始执行准备就绪的微操作

（1）指令提取——处理器使用一个多级分支目标缓冲区，在速度与预测准确度之间达到一种平衡。还有一个返回地址栈，用于加速函数返回。错误预测会损失大约15个时钟周期。利用预测地址，指令提取单元从指令缓存中提取16个字节。

（2）16个字节被放在预译码指令缓冲区中——在这一步，会执行一个名为微指令融合的进程。微指令融合接收指令组合（比如先对比后分支），然后将它们融合为一个操作。这个预译码过程还将16个字节分解为单独的x86指令。由于x86指令的长度可能是1 ~ 17字节中的任何一种长度，所以这一预译码非常重要，预译码器必须查看许多字节才能知道指令长度。然后将单独的x86指令（包括一些整合指令）放到包含18项的指令队列中。

（3）微指令译码——各个x86指令被转换为微指令。微指令是一些类似于MIPS的简单指令，可以直接由流水线执行；这种方法将x86指令集转换为更容易实现流水化的简单操作，1997 年在Pentium Pro中引入，一直使用至今。3个译码器处理可以直接转换为一个微指令的x86指令。对于那些语义更为复杂的x86指令，有-一个微码引擎可供用于生成微指令序列；它可以在每个时钟周期中生成多达4条微指令，并一直持续下去，直到生成必要的微指令序列为止。按照x86指令的顺序，将这些微指令放在一个包含28项的微指令缓冲区中。

（4）微指令缓冲区执行循环流检测和微融合——如果存在一个包含循环的小指令序列（长度少于28条指令，或不足256个字节），循环流检测器会找到这个循环，直接从缓冲区中发射微指令，不再需要启动指令提取与指令译码级。微整合则合并指令对，比如载入ALU运算和ALU运算/存储，并将它们发射到单个保留站（在保留站仍然可以独立发射这些指令），从而提高了缓冲区的利用率。在对Intel Core体系结构的一项研究中（这种结构也合并了微整合和宏融合），Bird等人[2007]发现微整合几乎对性能没有什么影响，而宏融合则对整数性能有一定的下面影响，对浮点性能也几乎没有什么影响。

（5）执行基本指令发射——在寄存器表中查看寄存器位置，对寄存器重命名、分配重排序缓冲区项，从寄存器或重排序缓冲区中提取任意结果，然后向保留站发送微指令。

（6）i7使用一个包括36项的集中保留站，供6个功能单元共享。每个时钟周期最多可以向这些功能单元分发6个微指令。

（7）微指令由各个功能单元执行，然后将结果发送给任何正在等待的保留站以及寄存器退回单元，一旦知道指令不再具有推测之后，将在这里更新寄存器状态。重排序缓冲区中与该指令相对应的数目被标记为完成。

（8）当重排序缓冲区头部的一条或多条指令被标记为完成之后，则执行寄存器退回单元中的未完成写入操作，并将这些指令从重排序缓冲区中删除。

i7的性能

在前面几节中，我们研究了i7分支预测器的性能和SMT的性能。在这本节，我们将研究单线程流水线性能。由于积极推测与非阻塞缓存的存在，所以很难准确描述理想性能与实际性能之间的差距。我们将会看到，因为指令不能发射而导致的停顿很少。例如，只有大约3%的载入指令是因为没有可用保留站而导致的。大多数损失不是来自分支错误预测就是来自缓存缺失。分支预测错误的成本为15个时钟周期，而L1缺失的成本大约为10个时钟周期; L2 缺失的成本比L1缺失的3倍略多一些，而L3缺失的成本大约是L1缺失成本的13倍（130~135个时钟周期）!尽管在发生L3缺失和某些L2缺失时，处理器会尝试寻找一些替代指令来执行，但有些缓冲区会在缺失完成之前填满，从而导致处理器停止发射指令。

为了研究错误预测和错误推测的成本，图3-24给出了未退回工作（即它们的结果未被取消）相对于所有微指令分发指令所占的比例（根据分发到流水线中的微指令数目来测量）。比如，对sjeng来说，由于在所分发的微指令中，有25%从来未被退回，所以浪费了25%的工作。注意，在某些情况下，被浪费的工作与图3-3所示的分支错误预测率吻合，而在几种实例中，比如mcf中，被浪费的工作似乎要高于错误预测率。从存储器行为的角度也许能够解释这些情况。当数据缓存缺失率非常高时，只要有足够的保留站可供停顿存储器引用使用，mcf就将在错误的推测期间分发许多指令。在检测到分支预测错误时，与这些指令相对应的微指令将被刷新，但当推测存储器引用试图完成时，可能会产生缓存争用。对处理器来说，在启动缓存请求之后，没有一种简单方法可以使其停止。

图3-24通过计算所有已分发微指令中未退回微指令所占的比值，绘制了“被浪费工作”的数量。例如，sjeng的比值为25%，也就是说在已分发、执行的微指令中有25%被抛弃。

图3-25显示了19 个SPECCPU2006基准测试的总CPI。整数基准测试的CPI为1.06，方差很大（标准偏差为0.67）。MCF和OMNETPP是两个主要例外，它们的CPI都大于2.0，而其他基准测试都接近或小于1.0（gcc是第二高，为1.23）。这种偏差是由于分支预测准确度和缓存缺失率方面的差别造成的。对于整数基准测试，L2缺失率是CPI的最佳预测值，L3缺失率（非常小）几乎没有什么影响。

图3-25 19个SPECCPU2006的CPI表明，尽管行为表现有很大不同，但浮点与整数基准测试的平均CPI都是0.83。整数基准测试的CPI值变化范围为0.44 ~ 2.66，标准偏差为0.77，而浮点基准测试的变化范围为0.62 ~ 1.38，标准偏差为0.25。

浮点基准测试的性能较高:平均CPI较低（0.89）标准偏差较低（0.25）。对于浮点基准测试来说，L1和L2对于确定CPI是同等重要的，而L3则扮演着小而重要的角色。尽管i7的动态调度和非阻塞功能可以隐藏一些缺失延迟，但缓存存储器表现仍然是重要因素。这进一步强化了多线程作为另一种方法来隐藏存储器延迟的作用。

谬论与易犯错误

这里介绍的几点谬论主要集中在根据单一测量值（比如时钟频率或CPI）来预测性能、能耗效率以及进行推断的难度。我们还将表明：对于不同基准测试，不同体系结构方法可能会有截然不同的表现。

谬论：CPI较低的处理器总是要更快一些。

谬论：时钟频率较快的处理器总是要更快一些。

要点在于：性能是由CPI与时钟频率的乘积决定的。在通过实现CPU的深度流水化获得高时钟频率后，还必须保持较低的CPI， 才能全面体现快速时钟频率的优势。同理，一个时钟频率很高、CPI 很低的简单处理器也可能更慢一些 。

在前面讨论的谬论中已经看到，在为不同环境设计的处理器中，即使它们采用相同的ISA，也可能在性能与能耗效率方面有很大不同。事实上，即使是同一公司为高端应用程序设计的同一处理器系列，在性能方面也会有很大差异。表3-20显示的是Intel公司对x86体系结构两种不同实现方式的整数与浮点性能，还有一个是Itanium体系结构，也是Intel出品。

图3-26 一组单线程基准测试的相对性能与功耗效率表明，i7 920比Atom 230快10倍以上，而功率系数平均只有它的二分之一。柱形条中显示的性能是i7与Atom的比值，即执行时间（i7）/执行时间（Atom）。能耗以曲线显示，为能耗（Atom）/能耗（i7）。i7在能耗效率方法从来都没有打羸Atom，不过在4个基准测试方面的性能基本相当，其中有3个是浮点。SPEC基准测试是使用标准Intel编译器在打开优化的情况下编译的，Java 基准测试使用Sun （Oracle） Hostpot Java VM。i7. 上只有一个核心是活动的，其余核心处于深度节能模式。i7上使用了Turbo Boost，这一功能可以提高其性能优势，但相对的能耗效率会略有降低

Pentium 4是Intel公司生成的最积极的流水线处理器。它使用深度超过20级的流水线，有7个功能单元，还有缓存微指令，而不是x86指令。在这种积极的实施方式中，它的性能相对较差一些，这清楚地表明它在开发更多ILP方面的努力失败了（很容易就会同时有50条指令正在执行）。Pentium 的功耗与i7相似，不过它的晶体管数较少，主存储器大约是i7的一半，包括仅有2 MB的次级缓存，没有第三级缓存。

Intel Itanium是一种 VLIW风格的体系结构，尽管调度超标量相比，它的复杂度可能增加，但它的时钟频率从来都不能与主流x86处理器相提并论（尽管它的总CPI与i7类似）。在研究这些结果时，读者应当明白它们不同的实现技术，对于同等流水线的处理器来说，i7 在晶体管速度上具有优势，从而在时间频率方面也占据上风。不过，性能方面的巨大变化（Pentium和i7之间相差3倍以上）还是令人吃惊的。

谬论：有时越大、越被动就越好。

在2000年前期，人们大多把注意力都放在构建更积极的处理器，用于开发ILP，其中就包括Pentium 4体系结构（它在一个微处理器中使用了当时最深的流水线）和Intel Itanium （它每个时钟周期的峰值发射率是当时最高的）。后来人们很快发现在开发ILP时，主要限制因素是存储器系统造成的。尽管推测乱序流水线可以很好地隐藏第一级缺失中10~ 15个时钟周期的大部分缺失代价，但它们在隐藏第二级缺失代价方面几乎是无能为力的，由于涉及主存储器访问，所以第二级缺失代价可能达到50 ~ 100个时钟周期。

结果就是，尽管使用了数目庞大的晶体管和极为高级、聪明的技术，但这些设计从来未能接近峰值指令吞吐量。下一 节将讨论这一两难选择，并从更积极的ILP方案转向多核技术，但过去还出现了另外一个变化，放大了这一缺陷。设计人员不再尝试用ILP来隐藏更多的存储器延迟，而是直接利用晶体管来创建更大的缓存。Itanium 2和i7使用三级缓存，而Pentium 4使用了两级缓存，三级缓存为9MB和8MB，而Pentium 4的二级缓存为2 MB.不用说，构建更多的缓存要比设计20多级的Pentium 4流水线容易得多。

结语: 前路何方

在2000年初，人们对开发指令级并行的关注达到顶峰。Intel 当时要发布Itanium，它是一种高发射率的静态调度处理器，依靠一种类似于VLIW的方法，支持强劲的编译器。采用动态调度推测执行的MIPS、Alpha和IBM处理器正处于其第二代，已经变得更宽、更快。那一年还发布了Pentium 4，它采用推测调度，具有7个功能单元和1个深度超过20级的流水线，然而它的发展前景浮现出一些乌云。

诸如3.10节介绍的研究表明，要想进一步推动ILP是极为困难的，大约三到五年前的第一代推测处理器已经实现了峰值指令吞吐量，而持续指令执行速度的增长要慢得多。接下来的五年真相大白。人们发现Itanium是一个很好的浮点处理器，但在整数处理方面表现泛泛。Intel 仍在生成这一产品，但它的用户不是很多，时钟频率要落后于主流Intel处理器，微软不再支持其指令集。Intel Pentium 4实现了很好的性能，但在性能/瓦特（也就是能量利用）方面的效率很低，这种处理器的复杂程度也使它很难通过提高发射率来进一步提高性能。 这条通过开发ILP来进一步提高处理 器性能的20年之路已经走到尽头。人们普遍认为Pentium 4已经超越了回报递减点，积极、复杂的Netburst微体系结构被放弃。

到2005年， Intel和所有其他主要处理器制造商都调整了自己的方法，将重点放在多核心上。往往通过线程级并行而不是指令级并行来实现更高的性能，高效运用处理器的责任从硬件转移到软件和程序员身上。从流水线和指令级并行的早期发展以来（大约是25年之前），这是处理器体系结构的最重大变化。在同一时间，设计人员开始探索利用更多数据级并行来作为提高性能的另一方法。 SIMD扩展使桌面和服务器微处理器能够适当地提高图形功能及类似功能的性能。更重要的是，GPU追求更积极地使用SIMD，用大量数据级并行来实现应用程序的极大性能优势。对于科学应用程序，这些方法可以有效地替代在多核心中开发的更具一般性但效率较低的线程级并行。

许多研究人员预测ILP的应用会大幅减少，预计未来会是双发射超标量和更多核心的天下。但是，略高的发射率以及使用推测动态调度来处理意外事件（比如一级缓存缺失）的优势，使适度ILP成为多核心设计的主要构造模块。SMT的添加及其有效性（无论是在性能方面还是在能耗效率方面）都进一步巩固了适度发射、乱序、推测方法的地位。事实上，即使是在嵌入市场领域，最新的处理器（例如ARM Cortex-A9）已经引入了动态调度、推测和更宽的发射速率。

未来处理器几乎不会尝试大幅提高发射宽度。因为从硅利用率和功率效率的角度来看，它的效率太低了。在过去10年里， Power处理器对ILP的支持已经有了一定的改进，但所增加的大部分晶体管（从Power 4到Power7增加了差不多7倍）用来提高每个晶片的缓存和核心数目。甚至对SMT支持扩展的重视也多于ILP吞吐量的增加：从Power4到Power7的ILP结构由5发射变为6发射，从8个功能单元变为12 个（但最初的2个载入存储单元没有变化），而SMT支持从零变为4个线程/处理器。显然，即使是2011年最高级的ILP处理器（Power7），其重点也超越了指令级并行。