指令级并行及其动态开发

第三章 指令级并行及其动态开发

“谁第一？” “美国。” “谁第二？” “没有第二，先生”

对话发生于观看帆船竞赛的两个人之间，这个后来叫做“美国杯”的帆船竞赛每几年就要举行一次。

灵感来自John Cocke命名的，由IBM公司研制的称为“美国” 的处理器，这个处理机就是第一个采用超标量结构的RS/6000系列微处理器。

3.1 指令级并行：概念及挑战

1985年以来，包括那些嵌入式处理器在内的所有处理器，都使用流水线方式使指令的执行可以重叠进行以提高效率。这种潜在的重叠被称为指令级并行（ILP），因为在这里指令可以并行处理。在本章和下一章中，我们将深入探讨扩展并行思想的一系列技术，这些技术主要表现在增加指令之间的并行度。本章的内容比附录A的内容更加深入，如果你们对附录A中的内容还不够熟悉的话，请先复习其中的内容。

在本章的开始部分，先介绍由数据冒险和控制冒险所带来的一些限制，然后进入我们的主题，学习如何才能通过提高处理器的并行性以最终提高处理器的运算能力。这一小节将介绍很多这两章要用到的基本概念，本章也有一些基础知识并不建立在这一小节上，但这些概念对本章的其他小节和第四章来说也是十分重要的。

提高指令级并行度有两种不同的方法，本章主要介绍动态的和以硬件为主的技术，而静态的和更依赖于软件的一些技术将在下一章中介绍。实际上，这种动态和静态，以硬件为主和以软件为主的划分并不是绝对的，其中的一种技术常常对另一种技术也有用。不过，为了清楚起见，我们还是把他们分开来研究，并在适当的地方会指出那些方法是可以借鉴过来的。

以硬件为主的动态技术被用在以桌面电脑和服务器为主的许多处理器中，包括PentiumⅢ和Pentium4，Athlon，MIPS R10000/12000，Sun UltraSPARCⅢ，PowerPC603、G3、G4和Alpha21264等等。而我们下一章所关注的静态的以软件为主的相关技术则被更多地用在嵌入式处理器中，虽然一些桌面和服务器产品，如IA-64体系和Intel的Itanium也使用了很多这种静态技术。

本章我们将分别从程序和处理器两个方面来讨论它们对指令级并行性的限制。我们还将研究程序结构和硬件结构之间的一些相当重要的映射关系，这对我们理解和掌握某些问题是至关重要的，这些问题包括一个程序实体是否会影响，和在什么情况下会影响处理器的性能。

4－1

我们知道，流水线机器的CPI（执行每条指令所用的时钟周期数）等于基本CPI加上各种暂停所使用周期数的和：

流水线CPI = 理想流水线CPI + 结构暂停 + 写读暂停 + 读写暂停 + 写写暂停 + 控制暂停

其中，理想流水线CPI是指可实现的最大指令流量。减少等式右边的每一项，可以减少总

的流水线CPI，从而增加IPC（每个时钟周期的指令流量）。在本章中将看到，我们要介绍的增加IPC的技术使得处理结构、数据和控制方面的问题如何显得更为重要。上面的等式描述了本章中将要讨论的用以减少流水线实际CPI的各种技术。图3.1表示一些将要讨论的技术及它们对CPI的影响。 技术

继续执行和绕行 延迟分支和简单分支调度 基本动态调度（记分板） 重命名的动态调度 动态分支预测 每个周期发射多条指令 预测

动态内存非二义化 循环展开

基本编译器流水线调度 编译器进行相关性分析 软件流水和路径调度 编译器预测

减少等式右边的某项 潜在的数据暂停 控制暂停

由真相关性产生的数据暂停

章节 A.2 A.2 A.8

数据暂停、反依相关和输出相关产生的3.2 暂停

3.4 控制暂停 理想CPI

所有数据暂停和控制暂停 涉及内存的写读暂停 控制暂停 写读暂停

理想CPI和数据暂停 理想CPI和数据暂停 理想CPI和数据暂停

3.6 3.7 3.2，3.7 4.1 A.2，4.1 4.4 4.3 4.4

图3.1 附录A、第三章和第四章将要讨论的主要技术及影响到的上面CPI等式中的相关项

目。其中，数据暂停是指各种各样的数据冒险造成的暂停，就是写读（先写后读）暂停、读写（先读后写）暂停或写写（写后再写）暂停。

在详细讨论上述技术以前，需对这些技术所涉及到的概念加以解释说明，它们决定了指令级并行性可以被开发的程度。

3.1.1 指令级并行性

在本章和下一章中讨论的所有技术都是用于开发指令序列中的并行性的。从上面可以看出，这种类型的并行性就叫做指令级并行性或ILP（instruction-level parallelism）。在一个基本块（除了入口和出口之外没有其它分支的线性指令序列）中可开发的并行性是很小的。例如，在第三章中看到的定点程序中平均动态转移频率在15%到20%之间，即每4条到7条指令中间将执行一条分支指令。由于这些指令很可能是相互关联的，所以我们在一个基本块中可以开发的指令重叠数将会远小于7。为了能够取得更大性能的提高，就必须开发多个基本块之间的指令级并行性。

4－2

提高指令级并行性的最简单也最常用的方法，是一个循环中的不同循环体并行执行。这类并行即通常所说的循环级并行。以下是一个简单的循环程序，完成由1000个元素组成的两个数组的相加，此程序是完全可并行的：

for (I = 1; i <= 1000; i = I + 1) x[i] = x[i] + y[i];

这个循环的每一个循环体都可以与其它任何一个循环体重叠执行，虽然在每一个循环

体内部可重叠的机会几乎没有。

有多种技术可以将上述循环级的并行转化成指令级并行，这些技术基本上要么由编译器静态地（下一章的内容）或由硬件动态地（本章要讨论的内容）对循环展开。

开发循环级并行的另一种重要方法是使用向量指令（见附录G）。基本上，一条向量指令是对一系列数据项进行操作。例如，上述代码可以在一个典型的向量处理机上用4条指令执行：2条从内存中读取向量x和向量y的指令、一条加法指令和一条保存结果的指令。当然，这些指令可以采用流水线方式执行，虽然有相对比较长的延迟时间，但这些延迟时间是可以被重叠的。向量指令和向量处理机的操作在附录G中有详细描述。虽然向量处理的思想要早于本章中大部分将要讨论的指令级并行技术，但是，采用指令级并行技术的处理机还是正在取代着基于向量处理的处理机，而向量指令集则有望在图象处理、数字信号处理和多媒体技术中得到应用。

3.1.2 数据相关性和数据冒险

判断指令之间是否有相关关系，对于判断程序中有多少并行性以及如何开发并行性是十分重要的。具体说来，要开发指令之间的指令级并行性，就必须清楚哪些指令是可以并行执行的。如果两条指令是可并行的，那么它们可以在流水线上同时执行而不会造成暂停，当然这里假定流水线资源部件是充足的（因此不存在任何资源冲突）。若两条指令是相关的，那么是不可并行的，虽然有时它们可以部分地重叠执行。因此，最重要的问题就是要判断指令之间是否存在有相关关系。

3.1.2.1 数据相关

有3种不同类型的相关：数据相关（也叫真数据相关）、命名相关和控制相关。如果下面的条件之一成立，则指令j数据相关于指令i：

? 指令i产生的结果为j引用。

? 指令j数据相关于指令k，而指令k数据相关于指令i。

第2个条件指出，如果两条指令之间存在有上述一条相关链的话，即它们之间也是相关的。这条相关链甚至可以贯穿整个程序。

举个例子，考虑如下使数组元素增值的一段代码。在下面的代码段中，0(R1)存放数组元素的首地址，8(R2)存放数组元素的尾地址，F2中存放增加量S。

Loop: L.D

ADD.D S.D DADDUI BNE

F0, 0(R1) F4, F0, F2 F4, 0(R1) R1, R1, # -8 R1, R2, Loop

；F0=数组元数 ；加上F2中的标量 ；保存结果

；数组指针递减8个字节 ；R1≠R2时转移

在上述例子中，相关序列包括浮点数：

4－3

Loop: L.D ADD.D S.D

和定点数：

DADDIU BNE

F0, 0(R1) F4, F0, F2 F4, 0(R1) ；F0=数组元素 ；加上F2中的标量 ；保存结果

R1, R1, # -8 R1, R2, Loop ；数组指针递减

；8个字节（一个双字） ；如果R1≠0，则转移

图中箭头所示的都是相关序列，每条指令均相关于前面一条指令。此处的箭头及以后例子中将要出现的箭头都表示为了得到正确结果指令之间必须保持的执行顺序。箭头从一条必须先执行的指令指向后执行的指令（即箭头头部所指的指令）。

如果两条指令之间有数据相关，那么它们就不能同时执行或是完全重叠执行，这种相关性说明它们之间存在一条有一个或多个写读冒险的相关链，同时执行这些指令会造成正在流水的处理机检测到这种冒险并插入暂停，从而减少甚至取消指令之间的重叠。在一个依靠编译器进行调度来消除冒险的处理机中，编译器不能调度相关的指令使它们完全地重叠执行，因为那样会使执行结果出错。指令序列中存在的数据相关反映出产生该指令序列的程序源代码中也存在有这种相关关系，这种源代码中的相关性一般是不能破坏的。

相关性是程序的一个特性，是否一个相关会导致实际的冒险，是否该冒险会造成暂停，这是流水线结构的基本特性。这一特性对于理解指令级并行性如何被开发利用是很重要的。

在所举的例子中，指令DADDIU和BNE之间存在有数据相关，由于我们把流水线的分支检测移到了ID流水段，因此相关造成了1次暂停。若分支检测仍保留在EX流水段的话，这个相关就不会引起暂停。当然，循环的延时仍然是两个周期，而不是一个。

相关性的存在只是预示着存在有冒险的可能性，而是否确实有冒险及造成多少个暂停周期，则是具体流水线的特性。数据相关性有以下几个重要特性：（1）相关性预示存在有冒险的可能性；（2）相关性决定必须遵循的计算顺序；（3）相关性决定可被开发的并行性的上界。这几个限制在第3.8节中还会详细地展开阐述。

由于数据相关性会限制可以开发的指令级并行性，因此本章和下一章的一个主要任务就是克服这些限制。这可以从两个不同的方面来解决：保持相关关系但避免冒险，或通过变换代码来消除相关关系。对代码进行调度是保持相关关系并避免冒险常用的一个最基本方法。在本章中我们将考虑通过硬件策略在程序执行过程中动态调度指令。由此我们可以发现，有一些相关性将被消除，这主要是由软件方法实现的，并在某些情况下使用了一些硬件技术。

一个数据在指令中的流动既可能通过寄存器也可能通过内存。当数据流发生在寄存器中时，由于指令中的寄存器名均是固定的，因而相关关系可以简单明了地检测出来，虽然有分支指令存在时会复杂一些，因为为了保证正确性，编译器和硬件的一些功能都会受到限制。而涉及到内存操作的数据流之间的相关关系则相对较难被检测出来，因为即使两个形式上完成不相同的地址，也有可能指向同一个内存单元。例如，100（R4）和20（R6）有可能表示同一个内存地址。此外，load和store指令的有效地址在不同的时刻执行的地址也有可能是不同的（即20（R4）和20（R4）可以是不同的值）。这些都进一步使相关性的检测工作复杂化了。在本章里，我们将研究采用硬件开发存储器中的数据相关性，虽然这种方法也存在有种种限制。检测这种相关的编译器技术将在下一章中讨论，这在开发循环级并行性时也是一个很重要的方法。

4－4

3.1.2.2 名字相关

第二类相关关系是名字相关，当两条指令使用同一个寄存器或是同一个内存地址时，即发生了名字相关，有名字相关的指令之间不存在数据值的流动。对于指令i和j（i在j之前），它们之间可能存在的名字相关有两种类型：

1．反相关，指令j写一个寄存器或一个内存单元，而指令i则去读该寄存器或内存单元，且i的执行在前。此时必须保证指令的原来顺序，以确保i能读到正确的值。 2．输出相关，指令i和j对同一个寄存器或内存地址执行写操作，这种操作顺序必须得到保证，以使最后写入的值得以保存。

反相关和输出相关都是名字相关，与真正的数据相关性相反，指令间没有相互传递的数值，这也意味着有名字相关的指令是可以同时执行或进行重新排序的。如果指令中的名字可以改变，就能使指令之间不再存在这种冲突，这种换名操作对于寄存器来说比较容易，叫做寄存器换名。寄存器换名可由编译器静态地或由硬件动态地实现。在描述由分支引起的相关性之前，我们先来看看相关性和流水线数据冒险之间的关系。

3.1.2.3 数据冒险

当指令之间存在相关性，而且它们的执行时间相近时，可能会在流水线中重叠操作，或者指令的重新排序改变了有相关的操作数的访问顺序，这时数据冒险就发生了。正是由于这种相关性的原因，我们必须保持指令的执行顺序，即由源程序决定的指令在正常串行执行（一条一条无重叠执行）时顺序。只有发现和避免数据冒险才能保证程序执行顺序的正确性。

数据冒险可以按照指令中读写访问的顺序分为三类。一般来说，数据冒险按在流水线中要保留的读写执行顺序来命名。比如有两条指令i和j，i在j之前执行，则可能的数据冒险有以下几类：

? 写读冒险（RAW）：如果j想在i写之前去读数据，读出来的将是旧值。这是最经

常发生的一种冒险，对应于真数据相关。要保证执行结果的正确就必须保证j在i之后读取数据。在简单的5段静态流水线（见附录A）中，一个ALU操作想读取在它之前刚写入的数据将导致一个写读冒险。

? 写写冒险（WAW）：当j在i写入数据之前写同一个单元（寄存器或内存地址）时

就会发生写写冒险。如果写操作以错误的顺序执行，会导致指令结束后的操作数是错误的，在这里操作数本应是j写入的值，但如果j先写，则指令结束后操作数结果为i写入的值。这种冒险对应于输出相关。写写冒险一般在允许多个写操作在流水线中各个阶段都允许发生的情况下，或当允许在前面的指令发生暂停时后续指令继续执行的时候发生。附录A中的典型的5段整数流水线仅仅在WB阶段写寄存器，因而可以避免此类冒险的发生。不过本章介绍的流水线允许对指令进行重新排序，这便使写写冒险成为可能。写写冒险也能在短整数流水线和浮点运算流水线中（见附录A.5和A.6）发生。比如，一个浮点乘指令要写F4，而后面紧接着的指令也要对F4进行load操作，由于load操作可能先于乘法指令完成，这就造成了写写冒险。

? 读写冒险（WAR）：当j先于i改写了i的操作数，则i读的时候将读进一个错误

的值。这种冒险是由反相关引起的。读写冒险一般不会发生在静态流水线中——即使是深度流水线或浮点流水线也没关系——因为这种流水线中的所有读操作（ID流水段）都比写回结果操作（WB流水段）来得早（见附录A）。读写冒险发生的情况有两种，要么在流水线中一些写指令提前完成或一些读指令滞后了，要么指令被重组了，而后者则是本章将要讨论的内容。

4－5

注意：读读相关（RAR）不是一种冒险。

3.1.3 控制相关

最后一种相关类型是控制相关。控制相关决定了跟分支指令有关的指令的执行顺序，即非分支指令只能在该执行的时候才能执行。程序中除了第一个基本块的每一条指令之外，均控制相关于某条分支指令，通常情况下，这些控制相关关系是必须保留的。一个控制相关的最简单例子是程序语句“then”部分对于“if”分支的相关。如下面例子：

if p1 { S1; }

if p2 { S2; }

S1控制相关于P1，S2控制相关于P2而不是P1。 控制相关有两方面的限制：

1．控制相关于一个分支的指令不能被移到分支之前执行。如if … then程序中，then后面的语句不能移至if之前执行。

2．没有控制相关于一个分支的指令不能移至受这个分支控制的指令之间执行，如if … then程序中，if前的指令不能移至then部分中执行。

在如第一章那样的流水线中，控制相关可以通过以下两个方面得到保证。第一，指令按顺序执行，这使得分支指令之前的指令只能在该分支指令之前执行。第二，对控制或分支冒险进行检测，保证控制相关于一个分支的指令在分支转移方向没有确定之前不会被执行到。

虽然保留控制相关是保证程序正确执行的简单而有效的做法，但控制相关本身并不是限制性能的基本因素。从上面的例子中还看到，编译器可以去掉某些控制相关。在某些情况下，有可能违反控制相关去执行某些还不该轮到执行的指令，仍然能够得到正确的结果。可见控制相关并不是必须保留的关键性因素。实际上，控制相关所要求保证的是对程序正确执行起关键性作用的两个特性：异常行为和数据流。

保留异常行为即意味着不管怎么改变指令执行的顺序，都不能改变原先程序中的异常情况。也可说是指令执行顺序的改动不能在程序中引起新的异常，一个简单例子可以说明维持控制相关是如何防止上述问题的。考虑如一下代码：

DADDU BEQZ LW L1：

R2, R3, R4 R2, L1 R1, 0(R2)

在这个例子中，很容易看出，如果不考虑由R2引起的数据相关问题，就可能会改变程序的执行结果。另外一点却不那么明显：如果忽略控制相关而把LW指令移到分支指令之前，则有可能引起内存保护异常的错误。注意，这里没有其它任何数据相关阻止我们调换BEQZ指令和LW指令，有的只是控制相关。如果需要在保持数据相关的情况下重组指令，我们将忽略分支引起的异常。在第3.7节中，我们将采用一种硬件技术——预测法——来消除这种异常问题，而在下一章中，为了解决这个问题，我们将看到其他一些技术。

4－6

数据流是维持控制相关所要保证的第二个特性。数据流即指令中确实存在的数据定值和引用的实际数据流动关系。分支指令使得数据流是动态变化的，因为分支指令使得某一指令中的数据可能来自于多个不同的地方。从另一方面讲，仅仅维持数据相关是不够的，因为一条指令可能对多个处理器产生数据相关，究竟那个处理器提供数据给一条指令是由源程序来决定的，而要保证源程序的顺序就需要维持控制相关。

考察如下代码段：

DADDU BEQZ DSUBU L: ? OR

R1, R2, R3 R4, L

R1, R5, R6 R7, R1, R8

在这个例中，指令OR中所用到R1中的值取决于分支转移是否成功。数据相关性只能处理静态的读、写顺序，仅仅保留一个数据相关关系并不能保证程序执行结果的正确性。在这个例子中，仅仅保证OR指令数据相关于ADD或SUB指令并不足以保证程序正确执行。在程序正确执行时，数据流关系也是必须保证的：若分支转移不成功，则OR指令引用的是SUB指令中的R1值；反之，引用的是ADD指令计算的R1值。保留SUB指令对于分支转移的控制相关，可以防止对数据流的非法改动。因此，这里的减法操作不能移到分支指令之前执行。在第3.7节中，将会看到，预测法和条件指令是如何在保持数据流不变的情况下，改变控制相关从而解决异常情况的。

有时，改变控制相关也可以既不影响异常行为也不影响数据流。看下列代码：

DADDU BEQZ DSUBU DADDU

skipnext: OR

R1, R2, R3

R12, skipnext R4, R5, R6 R5, R4, R9 R7, R8, R9

如果知道DSUBU指令的目标寄存器R4在标号skipnext之后不会被用到（一个值是否会被将来的指令用到的性质被称为存活性），那么在分支指令之前就改变R4的值也不会影响到数据流的状况，因为R4在skipnext后不会被用到，即相当于死亡了。因此，如果DSUBU指令也不会产生异常的话，就可以把DSUBU指令移到分支之前，程序的执行结果也不会因此而改变。如果分支转移确实成功，那么，虽然SUB指令会无用地执行，但也不会影响到程序的结果。这一类的代码调度有时也叫预测法，编译器这时必须猜测分支运行的结果（在这种情况下，相当于猜测分支转移不成功）。有关编译器的预测机制将在第4.5节中作更详细讨论。

对产生控制暂停的控制冒险进行检测可以保证控制相关性。很多软硬件方面的技术都可以消除或减少控制暂停。例如，第一章介绍的延迟转移可以减少控制冒险造成的暂停；调度一个延迟的分支需要编译器保持原先的数据流。

本章剩下的内容主要是利用硬件来挖掘潜在的指令级并行性。一个已经编译的程序中的数据相关性决定了指令级并行性在多大程度上能够得到改善。我们面临的挑战就是尽量减少实际的冒险及其引发的暂停。通过维持代码中必要的真数据相关性，我们能在开发可并行性方面更加得心应手。

4－7

3.2 采用动态调度克服数据冒险

一个简单的静态调度的流水线负责取指令并发射指令，当刚取到的指令与已经在流水线中的指令之间存在有数据相关，且不能通过旁路技术或相关直接通路技术予以避免时，就暂停取指令和发射指令。相关直接通路技术能够有效减少流水线的延迟时间使得一些相关关系不会引起冒险。如果存在有实在不可避免的数据相关，那么检测冒险的硬件将停止有相关的指令及其后面的指令进入流水线，直至相关性被消除之前不会再取出和发射新的指令。

本节我们将介绍一种重要的方法——动态调度法，即由硬件动态调整指令执行顺序以减少暂停的影响。动态调度法有以下几个好处：它能够处理某些在编译阶段无法知道的相关关系（如涉及内存引用时），并简化编译器设计；或许最重要的是，它能够允许在别的流水线机器上编译的指令在不同的流水线上也能有效运行。在第3.7节中，我们将介绍一种建立在动态调度基础上的硬件预测技术，这种技术具有相当好的性能优势。当然，这些优势是以硬件复杂度显著增加为代价的。

当一个采用动态调度方法的处理机无法消除真数据相关时，它会尽量避免相关所带来的暂停。相比之下，依赖于编译器的静态流水线调度方法（将在下一章中介绍），则是尽量通过分离有相关的指令使它们不会导致冒险，从而去减少暂停的影响。当然，采用静态调度方法生成的代码也可以在采用动态流水线调度的处理机中运行。

3.2.1 动态调度思想

附录A所述流水线技术的一个主要限制是它们全部使用按序发射指令的机制，即如果指令在流水线中被暂停，那么后继指令也无法前行。因此，若两条紧挨着的指令存在有相关关系，就会引起流水线的暂停。对于有多个功能部件的机器，就会造成这些功能部件的闲置。如果指令j相关于正在流水线中执行的指令i，而i的运行时间又很长，那么所有j后面的指令也不得不停下来直至i执行完成之后，j才能开始执行。考虑如下例子：

DIV.D ADD.D SUB.D

F0, F2, F4 F10, F0, F8 F12, F8, F14

ADDD相关于DIVD致使流水线出现暂停，其后面的指令SUBD也因此而不能执行，尽管SUBD所需要的数据并不相关于流水线中的任何指令。如果不要求指令按序发射，就可以消除这种对性能提高的限制。

在第一章所讨论的5段流水线中，资源冒险和数据冒险均是在指令译码阶段（ID）进行检测的。若一条指令可以正确执行，才会从ID发射出去。为了使上例中的SUB.D指令能够开始执行，就必须把发射阶段分离成两个阶段：检测资源冒险和等待不存在数据冒险的情况。在发射指令时仍能对资源冒险进行检测，这样既可以使用按序发射指令的方法，又可以要求指令在操作数准备好时就可以开始执行。这时流水线采取的是乱序执行方式，指令的结束也是乱序的。

乱序执行引进了WAR和WAW冒险，而这些冒险在5段整数流水线和其扩展的对顺序浮点流水线中是不存在的。考虑如下MIPS浮点代码段：

DIV.D ADD.D

F0, F2, F4 F6, F0, F8

4－8

SUB.D MUL.D F8, F10, F14 F6, F10, F8

在ADD.D和SUB.D之间存在反相关关系，如果流水线使得SUB.D先于ADD.D执行的话便会违反反相关性并导致一个读写冒险。同样，如果要避免由MUL.D对F6写操作的输出相关，就要控制写写冒险。下面我们将会看到，这两种冒险可以通过寄存器重命名来避免。

乱序执行的一个主要的困难是在异常处理上。乱序执行的动态调度必须保持程序的异常行为，只允许程序在严格顺序执行的情况下能产生的异常发生。要做到这一点，必须使得在处理器知道能产生异常的指令将要执行时才能产生异常，关于这一点稍候我们便会明白。不过，尽管异常行为必须保持，动态调度处理器仍然会产生一些不精确异常。所谓不精确异常是指当产生异常时处理器状态与程序严格按照串行顺序执行时不一样。不精确异常发生的情况有两种：

1．流水线可能在指令产生异常之前完成了指令的执行，而在程序顺序执行时应该先产生异常后完成指令。

2．流水线没有在指令产生异常之前完成指令，而在程序顺序执行时应该先执行指令后产生异常。

当异常出现不精确时，会使中断后重新开始执行原先的程序变得很困难。在本节中将不讨论这些问题，我们将在第3.7节中，就具有预测机制的处理机所产生的精确异常情况提出解决方案。对于浮点类型的异常问题，还存在有其它可能的解决方法，如附录A中所讨论的那样。

在引入乱序执行这一机制之前，必须先弄清楚构成ID流水段的两个阶段： 1．发射——译码，并检测资源冒险的情况。

2．读操作数——等待直到不存在数据冒险，并读出操作数。

一条指令经过取指令阶段到发射阶段，可以把指令取至一个指令寄存器中或一个待定队列中，然后让指令从寄存器或队列中发射出去。读操作数之后是执行阶段（EX），正如5段流水线中一样，在5段浮点流水线中，根据操作数的不同，可能在执行阶段要使用好几个周期。

我们很容易区分指令的两个边界：开始执行和结束执行，在这两个边界之间就是指令的执行状态。我们的流水线允许几条指令同时并行执行，否则，动态调度的优点也就无从谈起。允许几条指令同时并行执行需要处理器有多个功能部件，或多个流水线功能块，或兼而有之，这两者对于实现流水线控制是等价的，以后我们不妨假设处理机配备了多功能部件。

在动态调度流水线中，指令在发射阶段都是顺序的（顺序发射），但在第二个阶段（读操作数）却可以暂停或提前执行，即进入乱序执行阶段。记分板机制正是在资源部件充足，没有数据相关存在的前提下，允许指令乱序执行的一种技术。其命名取自于CDC6600，正是该机器发展了记分板机制。我们将把注意力集中在一个更成熟的技术上，即Tomasulo’s算法，这个算法对记分板机制做了几个大的改进。如果需要对这些概念有个粗略的了解，可以参考附录A，在那里完整的讨论了记分板机制并给出了几个例子。

3.2.2 用Tomasulo算法进行动态调度

在IBM360/91的浮点部件中使用了一种重要的动态调度方法，它能够使指令在有冒险存在的情况下仍能继续执行。这种方法是由Robert Tomasulo 提出的，方法也因此而命名。Tomasulo方法跟踪指令获得操作数的时间，以减少写写冒险和写读冒险。在使用此方法的

4－9

处理器的众多方案中，始终拥有一个共同的特点，即跟踪指令的相关性，使得指令所需要的操作数一旦准备好就允许执行，同时运用寄存器换名技术来避免读写和写写冒险。

IBM360/91的出现在Cache商业化以前。IBM的目标是希望从专门为360系列设计的编译器和指令集中提高浮点计算的性能，而不仅仅依赖专门为尖端处理机而设计的编译器。360系统结构只有4个双精度浮点寄存器，这限制了编译器调度的有效性，也是促使Tomasulo方法出现的一个原因。此外IBM360/91具有较长的内存访问和浮点操作延迟，而Tomasulo方法正好可以弥补这些弱点。在本节的最后，还可以看到Tomasulo方法是如何支持多个循环体重叠执行的。

下面，在MIPS指令集上的浮点单元和存取单元上解释该算法。MIPS与360最基本的差别是后者中出现了寄存器—存储器指令。由于Tomasulo方法使用了一个取数功能部件，因此对于寄存器—存储器寻址模式不需做太大的改动，最基本的变动是增加了一条总线。IBM360/91是采用流水功能部件的，而不是多功能部件，但是这两者不存在本质的区别，以下讨论算法时不妨假设是多功能部件的情形，两者之间只是一个简单的概念性扩展。

正如我们将要看到的，当指令所需要的操作数全部到达之后才开始执行指令，就可以避免写读冒险，而通过寄存器换名可以避免由名字相关引起的读写冒险和写写冒险。寄存器换名是对那些相关目标寄存器重新命名，使得乱序执行时的写操作不会影响需要那个被写数以前值的指令的正确执行。

为了更好地了解采用寄存器换名技术消除读写冒险和写写冒险的原理，我们可以看下面一段代码，这段代码包括了这两种冒险：

DIV.D ADD.D S.D SUB.D MUL.D

F0, F2, F4 F6, F0,F8 F6, 0(R1) F8, F10, F14 F6, F10, F8

在上面的代码中，ADD.D和SUB.D之间存在反相关关系，ADD.D和MUL.D之间是输出相关，他们可能造成两种冒险：由ADD.D使用的F8产生的读写冒险和由ADD.D和MUL.D完成顺序产生的写写冒险。这里还有三处真数据相关：DIV.D与ADD.D、SUB.D与MUL.D、ADD.D与S.D。

所有名字相关都能通过寄存器换名来消除，简单地讲，假设存在两个暂存寄存器S和T，使用S和T改写以上代码就可以消除那些相关性：

DIV.D ADD.D S.D SUB.D MUL.D

F0, F2, F4 S, F0, F8 S, 0(R1) T, F10, F14 F6, F10, T

此外，接下来所有使用F8的地方必须用T来代替。在这个代码段里，所有的重命名过程都可以由编译器来完成，不过，要发现以后使用F8的所有地方，需要一个好的编译器或者硬件支持，因为在上述代码段和以后使用F8的地方之间可能存在一些复杂的分支语句。我们将会看到，Tomasulo算法会很好地解决跨分支重命名的问题。

在Tomasulo算法中，寄存器重命名的功能是通过保留站来实现的。在保留站中缓存了即将要发射的指令所需要的操作数，其工作的基本思想是尽可能早地取得并缓存一个操作数，从而避免必须读操作数时才去寄存器中读取的情况。此外，即将执行的指令也会由保

4－10

留站取得所需要的操作数。当出现多个操作写同一个寄存器时，只允许最后一个写操作实际更新寄存器。在指令发射之后，它所需要的操作数对应的寄存器也将换成保留站的名字，这一过程就是寄存器换名技术。由于可以使用比真正的寄存器还多的保留站，因此可以消除原先编译器所不能消除的冒险。在讨论Tomasulo算法的过程中，还将继续讨论寄存器换名技术并介绍如何进行换名，以及换名方法是如何消除冒险的。

使用保留站与集中式寄存器堆相比有两个重要的特点。第一，在这里，冒险检测和执行控制是分散的，每一个功能部件的保留站控制该部件中指令的执行时间。第二，结果将从保留站所缓存的地方直接送到功能部件中，而不是通过寄存器传送，为此使用了一条公共结果总线。该总线允许所有等待该操作数的功能部件可以同时取到该数据（在IBM360/91中，这条总线也叫公共数据总线或CDB）。注意，在拥有多个执行部件和每个时钟发射多条指令的流水线中需要多条结果总线。

图3.2给出了基于Tomasulo算法的MIPS处理器的基本结构，该结构包括浮点部件和内存部件，但是没有表示出执行控制状态表。保留站中保存着已经发射并等待到功能部件中去执行的指令，此外还有指令所需要的源操作数（这里可能是具体的操作数的值，也可能是可提供操作数的保留站编号）。 从指令部件来 指令队列 浮点寄存器 Load/store操作 浮点操作 读数缓冲站 操作数总线 保留站 写数缓冲站 地址 数据 内存部件 浮点加法器 浮点乘法器 公共数据总线 图3.2 基于Tomasulo算法的MIPS浮点部件的基本结构。浮点操作从指令部件以先进先出

(FIFO)的方式送至指令队列中，保留站中保存了运算符和操作数，及检测和解决冒险所需要的信息。读数缓冲站有三个功能：负责保存有效地址的各个部分直到地址计算完成，监视正在等待访问内存的其他需求，对于已经执行完成的访问存储器操作，等待保存CDB上出现的结果。同样，写数缓冲站也要保存那些有效地址的各部分直到地址计算完成，保留正在等待数据值的内存目标地址，保留地址和值直到内存单元可以使用。所有从浮点部件(FP)和读数部件出来的结果均送至CDB上，从而可以送至浮点寄存器堆和保留站及写数缓冲站中。浮点加法器具有加法和减法的功能，浮点乘法器则实现乘法和除法运算。

4－11

在读数缓冲站和写数缓冲站中保存着从内存读出或即将要写到内存中去的数据或数据地址，它们的工作方式与保留站一样，因此，我们在没有必要时就不特意区分它们。浮点寄存器通过一组总线连接到功能部件上，并通过一条总线连到写数缓冲站中。所有从功能部件和存储器中出来的结果均被送到公共数据总线上，并到达所有需要该操作数的地方（不可能是读数缓冲站）。除了读数缓冲站，所有的缓冲站和保留站均设置有标志域，这些标志主要用于冒险控制机制。

在开始讨论保留站和算法的细节之前，不妨先看看指令运行所经过的几个阶段——正如我们讨论附录A中的5段流水线一样。与前面相比，操作数的传送方式发生了变化，这中间只需要3个阶段：

1．发射——从浮点运算队列中取得一条指令，这条指令按照先进先出(FIFO)的方式保留在队列中，以保持数据流的正确性。若指令的操作数已经准备好，而保留站中还有空位置，就发射该指令至保留站中，并把寄存器中已有的操作数也送至保留站中。如果没有空余的保留站，则说明发生了资源冲突，该指令只好等待保留站或缓冲站出现空闲。如果指令的操作数还不在寄存器里，则跟踪产生操作数的功能单元。在发射阶段，进行寄存器换名工作，以消除读写冒险和写写冒险。 2．执行——若还有操作数没有准备好，则监视公用数据总线(CDB)，等待源操作数。当一个操作数计算出来之后，就放到相应的保留站中。当指令所需要的源操作数均出现之后，就可以执行该运算。由于这里的指令需要等待操作数可以使用后才能执行，所以写读冒险不会产生。必须注意，虽然不同的功能单元可以同时开始执行几条指令，但是，当发生几条指令在同一个功能单元同时变得可以执行时，功能单元必须选择其中的一条指令执行——一个功能单元在同一个时钟周期只能执行一条指令。对于浮点保留站，选择可以是任意的，而对读数和写数缓冲站来说，就相对复杂一些。

读数和写数需要两个执行步骤：首先在基址寄存器有效时计算有效地址，然后再将数据读入读数缓冲站或从写数缓冲站写入内存。读数缓冲站在内存单元有效时就立即执行读内存操作，而写数缓冲站则保存数据等待内存单元有效时将数据写入内存。这样，通过有效地址计算，读数和写数都得以保留源程序的执行顺序，从而避免了访问内存的冒险。

为了维持异常行为，任何指令在它之前的分支指令没有完成之前不得开始执行。这种限制保证了指令只在异常应该被执行时产生。在使用了分支预测技术的处理器（使用动态调度的处理器都使用了分支预测技术）中，这意味着处理器需要知道分支预测是正确的，这样才能允许分支后的指令执行。当然，通过记录指令发生（而不是产生）的异常，我们可以不必暂停指令的执行直到进入写结果阶段。我们发现，预测技术提供了一种更有弹性，也更完整的方法来处理异常，我们将在今后进一步讨论这个问题。

3．写回结果——当结果出来之后，送至CDB，进而写回到寄存器中，或被其他保留站（包括缓冲站）读取。这里，缓冲站会向内存写回数据：当地址和数据值都有效则写入内存单元，并结束缓存。

检测并消除冒险的数据结构附在保留站、寄存器堆、读数缓冲站和写数缓冲站中，当然，其功能各不相同，所保存的信息也稍有不同。除了读数缓冲站之外，其他部件均带有一个标志域。标志域本质上是换名时用到的虚拟寄存器的名称。在这个例中，标志域是一个4位结构，它表示5个保留站中的某一个或是6个读数缓冲站中的某一个。下面将会看到这一作用相当于11个结果寄存器（而不是360系统结构中的只有4个双精度寄存器）。

4－12

在一个需要更多物理寄存器的处理机中，可以通过换名方法取得更多的虚拟寄存器。标志域指明产生源操作数的指令所在的保留站。

当指令被发射并等待操作数时，标志域会指向产生该操作数的保留站号，而不是指向目标寄存器。而诸如0等的无用的值，则表示操作数已经存放于寄存器中。由于保留站多于实际寄存器的数量，所以通过使用保留站进行换名，可以减少写写冒险和读写冒险。在Tomasulo方法中，保留站作为扩展的虚拟寄存器使用。在其它方法中，则可能要使用额外的寄存器或类似排序缓冲站的结构等，在第3.7节中会涉及到这类情况。

为了描述Tomasulo算法，在不引起混淆的情况下，仍将使用记分板机制中的术语，IBM360/91的术语也列出如下。值得重新强调的一点是，Tomasulo算法中的标志域指向的是产生所需结果的缓冲站或功能部件，而不再是寄存器名。指令发射到保留站之后，寄存器名即被抛弃。每一个保留站有7个域：

? OP——对源操作数S1和S2所做的运算。

? Qj，Qk——产生相应源操作数的保留站。若值为0则表示Vj或Vk中的值是有效

的，或是不需要的。（在IBM360/91中称为接收部件(SINK unit)或源部件(SOURCE unit)。）

? Vj，Vk——源操作数的值。在IBM360/91中称为接收端和来源，并注意到对每次

操作，V域或Q域中仅有一个是有效的（在IBM360/91中称这些域为接收域和源域）。

? A——读数和写数时计算内存地址的信息。一开始，指令的立即数域被保存在这

里。地址计算后，这里保存的是有效地址。

? Busy——指示该保留站及相关的功能部件正在使用。

对于寄存器堆，则对应一个域Qi。

? Qi——保存保留站号。在该保留站中进行的运算，其结果值将存入该寄存器或缓

冲站中。若Qi为空（或0），则表示当前不会有运算结果要存到该寄存器或缓冲站中。对于寄存器，这也意味着寄存器中的内容不会被改变。

读数和写数缓冲站还各自要求一个A指示域，用于在第一步执行结束后保存有效地址的结果。

在下一节中，我们将首先看一个例子，通过这个例子我们将了解以上所说的那些机制是如何工作的，并详细学习Tomasulo算法。

3.3 动态调度：算法及举例

在详细讨论Tomasulo算法之前，首先考察如下代码序列在各个表中所对应的状态信息。

例题3.1：首先考察当第一条LOAD指令完成并写回结果时，状态表中信息是怎样的：

1： 2： 3： 4： 5： 6：

L.D L.D MUL.D SUB.D DIV.D ADD.D

F6, 34(R2) F2, 45(R3) F0, F2, F4 F8, F6, F2 F10, F0, F6 F6, F8, F2

4－13

解：图3.3给出保留站、读数缓冲站、写数缓冲站及寄存器标志信息。跟在指令名add、mult和load之后的数字代表该保留站的标志域——Add1是第一个加法部件取得结果的标志，这里还加进了指令状态表，其作用仅仅是帮你理解算法原理，它并不是实际硬件的一部分。在每发射一条指令之后，运算操作的状态都保存在保留站中。

指令

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

指令状态 发射 √ √ √ √ √ √

执行 √ √

写回结果 √

站名 取数1 取数2 加法1 加法2 加法3 乘法1 乘法2

保留站 忙 否 是 是 是 否 是 是

操作 Load SUB ADD MUL DIV

Vj Mem[34+Regs[R2]]

Vk

Qj 取数2 加法1

Qk Load2

A

45＋Regs[R3]

Regs[F4] 取数2 Mem[34+R乘法1 egs[R2]]

域名 Qi

寄存器状态 FO

F2

F4

F6

F8

F10

F12

…

F30

乘法1 取数2

加法2 加法1 乘法2

图3.3 所有指令都已经发射，只有第一条load指令已经执行完成并把结果送至CDB时，

保留站及寄存器标志的状态。第二条load指令已经完成有效地址计算，正在等待从内存单元读出数据。我们用Regs数组表示寄存器堆，用Mem数组表示内存。注意到一个操作数在任何时候均可以由Q域或V域具体确定。注意，已经发射出去的加法指令在WB阶段有一个读写冒险，它应该在除法指令初始化之前完成。

与其他更早、更简单的算法相比，Tomasulo算法的主要优点在于：（1）分散了冲突检测机制；（2）消除了写写和读写冒险造成的暂停。

第一个优点来自于分布式的保留站结构和CDB的使用。如果多条指令等待同一个结果，且每条指令均已经读到另一个操作数，那么CDB的广播机制，可以使得这些指令能够同时得到这一个操作数，并同时开始运行。而使用集中式寄存器堆时，等待着的指令只能竞争使用寄存器总线去读取所需要的寄存器中的值。

4－14

第二个优点是：在保留站中，寄存器换名技术将操作数尽可能早地存入保留站中，从而消除写写和读写冒险。例如，在图3.3中的代码，ADD.D和DIV.D已经同时发射，虽然它们存在有F6的读写相关。在这里，两种方法均可以消除这种冒险。第一，如果为DIV.D提供操作数的指令已经执行完成，那么Vk就会保存该结果，从而允许DIV.D独立于ADD.D执行。

另一方面，若L.D尚未完成，那么Qk便会指向load1保留站。DIV.D也可独立于ADD.D而执行。这样，无论如何，ADD.D都能够发射并执行。任何使用DIVD结果的指令均指向保留站，这也使得ADD.D可以早于DIV.D之前执行结束并把结果存回寄存器而不影响DIV.D的执行。下面还将简要地讨论一下写写冒险的消除。在此之前不妨先看一下上述例子是如何连续执行的。

在本章以下的例子中，将做如下假设：加法2个时钟周期，乘法10个时钟周期，除法40个时钟周期。

例题3.2：在上例的代码中：考察当代码执行到MUL.D开始写回结果时，各状态表中的信息。

解：如图3.4所示，ADDD和DIVD之间的读写冒险不再阻碍流水线正常运行，ADDD可以早于DIVD先执行完成。注意到即使取数到F6的指令有可能被延迟，但是把运算结果写入F6的加法操作还是会正确执行的，而且不会引起写写冒险。

指令

LD F6, 34(R2) LD F2, 45(R3) MUL.D F0, F2, F4 SUBD F8, F6, F2 ADDD F6, F8, F2

指令状态 发射 √ √ √ √ √

执行 √ √ √ √ √

写回结果 √ √ √ √

DIVD F10, F0, F6 √

站名 取数1 取数2 加法1 加法2 加法3 乘法1 乘法2

保留站 忙 否 否 否 否 否 是 是

操作 MULT DIV

Vj

Vk

Qj

Qk

Mem[45+Regs[R3]] Regs[F4]

Mem[34+Regs[R2]] 乘法1

域名 Qi

寄存器状态 FO

F2

F4

F6

F8

F10 F12 …

F30

乘法1 乘法2

图3.4 图中乘法和除法是仅剩的未完成操作。

4－15

1位预测器的复杂之处在于更新次数更多，而后者仅在预测失败时才更新。因为我们每个循环周期要读预测位一次，因此两位预测器需要有两个取数点分别用于读和写。

由两位预测方案引伸开，可以有更多位的带n位计数器的预测方案。n位计数器可以表示0～2n－1之间的值，当计数器的值大于或等于其最大值的一半（2n-1）时，就预测分支转移将被执行；否则，就预测不执行。在两位预测方法里，计数器的值随着分支每执行一次就增加一次。随着分支未被执行就减少一次。对两位预测器的工作机理的研究结果表明，实际上，两位预测器已经工作得很好了。因此在绝大多数系统里，往往采用两位预测方案就够了。

分支预测缓冲站可以用存放指令地址的小的专用Cache来实现，并把它放在流水线的IF段中；也可以作为一对指令位附于指令缓冲站的每一块中，并随指令一起读取。如果指令经过译码判断出是分支指令，并且分支预测是被执行的，那么取指令操作就可以尽快取到下一条指令；否则，只需要按顺序取指令和执行指令即可。如果预测错误，那么预测位将按图3.7所示机制改变。

虽然这一方案对绝大多数流水线是有效的。5段典型流水线可以在同一时间发现分支是否被执行和分支执行的下一个地址。这时假设存取条件分支的具体寄存器不存在冒险（这是因为5段流水线在ID段会对寄存器进行判0比较，此时也正是计算有效地址的时候）。可见这一方案对于简单的5段流水线不会起多大作用，稍后将讨论一种对5段流水线和多指令发射处理器起作用的方案。首先，看看通常情况下分支预测是如何工作的。

在实际应用中对每个入口采用两位预测位机制的分支预测缓冲站方法将会获得怎样的精确度呢？对于SPEC89基准测试程序，有4096个入口的分支预测缓冲站会有82%到99%的预测精确度，或预测错误率在1%到18%之间，如图3.8所示。为更清楚看清这一差别，可以考察预测错误的频率而不是预测正确的频率。一个有着4K个入口的缓冲站可以认为是相当大的规模了，对于更小一些的缓冲站其效果会差一些。

SPEC89 基准测试程序 预测不正确率 图3.8 有4096个入口的两位预测缓冲站对于SPEC89基准测试程序的预测精确度。预测定

点测试程序（gcc、espresso、eqntott和li）的不正确率（平均为11％）要远高于预

4－21

测浮点测试程序（平均为4％），即使忽略了浮点程序的内核操作（nasa7、matrix300和tomcatv），所得到预测精度也会高于定点程序。这些数据及本节中的其他数据，均取自于对IBM Power系统结构的分支预测和对这些系统的代码优化研究，可参考Pan et al.[1992]。

知道了如图3.8所示的预测精确度之后，即使给出了分支所花费的代价及预测不正确所带来的损失，还不能足以判断出分支对性能的影响。另外，还必须考虑到分支发生频率的影响，因为程序中分支发生频率对精确预测是很重要的。比如说，定点程序——li 、eqntott、 espresso和gcc，它们的分支发生频率比那些更易被预测的浮点程序高。

随着指令级并行性的进一步开发，分支预测的精确度也显得重要起来。从图3.8也可看出，定点程序中分支预测的精确度比复杂循环的科学计算程序还低，这些定点程序也有更高的分支发生频率。可以通过两方面来解决这一问题：要么增加缓冲站的容量，要么增加预测方案的预测精确度。如图3.9所示，有4K个入口的缓冲站在使用上即可相当于一个无限大的缓冲站，图3.9中的数据也表明缓冲站的命中率不是一个限制性因素。正如上面已经提到的，仅仅增加预测器的位数而不改变其结构也不会有多少影响。因此，我们需要尽力提高预测器的精确度。

SPEC89 基准测试程序 预测不正确率 4096项 无限多项 每项2位 每项2位

4－22

图3.9 采用SPEC89基准测试程序对有4096个入口的两位预测缓冲站与无限大的缓冲站的

预测精确度进行比较。

3.4.2 相关分支预测器

这个两位预测器的方案只依靠最近一次分支的行为来预测将来分支的行为。如果只依靠已经发生过的其他分支的行为来进行预测，而不考虑即将发生的分支，也可以提高预测精的确度。考虑SPEC92基准测试程序eqntott（其两位预测机制的效率最差）中的一小段代码：

if (aa = = 2) aa = 0;

if (bb = = 2) bb = 0;

if (aa != bb) {

以下是对应的MIPS代码，其中，假设寄存器R1、R2分别代表aa和bb：

L1: L2:

DSUBUI BNEZ DADD DSUBUI BNEZ DADD DSUBU R3 BEQZ

R3, R1, #2 R3, L1 R1, R0, R0 R3, R2, #2 R3, L2 R2, R0, R0 R1, R2 R3, L3

；分支b1（aa!=2） ；aa==0

；分支b2（bb!=2） ；bb==0 ；R3=aa-bb

；分支b3（aa==bb）

把分支操作分别标号为b1，b2，和b3。可以观察出分支b3的行为是相关于分支b1和b2行为的。很显然，如果分支b1和b2均未转移成功（即若条件均为真且aa和bb均赋值为0），则b3将会被执行，显然aa和bb是相等的，而只使用单个分支行为去预测分支结果的预测方案是不会有此特点的。

使用其它分支行为来预测的分支预测器即叫做相关预测器或双层预测器。以下用一个简单的多层条件的例子来看清该方案是如何工作的。考虑如下简化了的代码段(假想代码)：

if ( d= = 0) d = 1;

if (d = = 1)

下边是上述程序对应的MIPS代码，假设R1寄存器中的值为d：

BNEZ DADDUI L1: DADDUI BNEZ …… L2:

R1, L1 R1, R0, #1 R3, R1, #1 R3, L2

；分支b1（d!=0） ；d==0, 因此d=1 ；分支b2（d!=1）

4－23

两个分支相应的标志为b1和b2。假设d的取值可为0、1和2，这段代码可能的执行顺序如图3.10所示。为了更好地说明相关预测器的工作原理，我们假设上述代码段重复执行，但不考虑程序中其他使之重复执行的代码。

d的初始值 0 1 2

D==0？ 是 否 否

b1 未执行 执行 执行

执行b2前 d的值 d==1？ 1 是 1 2

是 否

b2 未执行 未执行 执行

图3.10. 该代码段可能的执行顺序

从图3.10可看出，若b1不被执行，则b2也不会被执行。一个相关预测器就可以利用这一点，而标准预测器则无法利用这点。不必考虑所有可能的分支路径，只需要考虑d值介于2与0之间变化的序列。一个初始假设为不转移的一位分支预测器的情形如图3.11所示。由图可见，对所有分支预测均得到了错误的结果。

对b1的 b1的 对b1的 对b2的 b2的 对b2的 d=？ 预测 实际动作 新预测 预测 实际动作 新预测 2 NT T T NT T T 0 2 0

T NT T

NT T NT

NT T NT

T NT T

NT T NT

NT T NT

图3.11 初始假设为不被执行的一位预测器的情况。其中，T代表被执行，NT代表不被执

行。

同样情况下，考虑只使用一位预测位的相关预测器。考察这一方案的最简单方法是思考每一个分支均有两个单独的预测位的情况：一个预测位假定上一次已执行的分支不会被执行，另一预测位假定分支会被执行。注意到，在通常情况下，上一个已执行的分支与正被预测的分支并不是相同指令，虽然在由简单循环构成的单个基本块中往往是这样的（在这些循环中没有其他分支存在）。

现在把这一组预测位写在一起，第一位是当程序中上一个分支未被执行时的预测情况，第二位是上一个分支被执行时的预测情况。图3.12给出了4种可能的组合及其含义：

预测位 NT/NT NT/T T/NT T/T

上次分支未被执行时的预测 NT NT T T

上次分支被执行时的预测 NT T NT T

图3.12 被执行/未被执行的预测位的组合及其含义。其中，T代表被执行，NT代表不被执

行。

4－24

有一位相关位的一位预测器，在初始情况为NT/NT时的工作情况如图3.13所示。 d=？ 2 0 2 0

对b1的 预测 NT/NT T/NT T/NT T/NT

b1的 实际动作 T NT T NT

对b1的 新预测 T/NT T/NT T/NT T/NT

对b2的 预测 NT/NT NT/T NT/T NT/T

b2的 实际动作 T NT T NT

对b2的 新预测 NT/T NT/T NT/T NT/T

图3.13带有一位相关位的一位预测器的动作情况，初始情况为未被执行/未被执行。其

中，T代表被执行，NT代表不被执行。使用了的预测位用黑体字表示。

在这个例中，仅有的一次预测出错是在第一个循环，当时d = 2时。对b1的正确预测是由于d值的选择，因为b1并不明显相关于对b2先前的预测。对b2的正确预测，显出了相关预测的优势。在第一次不正确预测之后，当每次b2执行之后b1均未被执行时，即使选择了不同的d值，也可对b2进行正确的预测。

图3.12和图3.13的预测器均称作（1，1）预测器，它根据前一次分支的行为去从一位分支预测器中进行选择。在通常情况下，一个（m，n）预测器表示使用前m个分支行为去从2m个分支预测中进行选择，每一个预测是对应于单个分支的n位预测器。这种相关分支预测器的吸引人之处，即在于它与两位预测器相比可以取得更高的预测率，并且只需要少量的额外硬件支持。其硬件的简单性表现在：最近m个分支的全局历史记录可以记录在一个m位移位寄存器中，每一位记录着该分支是被执行还是未被执行。对分支预测缓冲站的访问可由分支地址的低位拼接上m位全局历史记录而得到。图3.14给出了一个（2，2）预测器及如何访问预测器的例子。

分支地址 两位分支预测器 XX预测缓冲站 两位全局分支历史记录

图3.14 一个（2，2）分支预测缓冲站使用一个两位全局历史记录去选择4个预测器以得到

每一个分支地址。反过来，所有预测器都是对应于相关分支的两位预测器。此处

4－25

的分支预测缓冲站有64个入口。分支地址用于选择4个入口，全局历史记录从这4个中再选择一个，两位的全局历史记录可由一个移位寄存器实现并在分支的行为确定时移位。

在实际应用时还会有一些轻微的变化，因为预测缓冲站不是Cache，由全局预测器这种独立访问的计数器在某些时候实际上会对应于不同的分支，而不是正好对应于当前的分支，这些情况，我们前面已经可以看到过。在图3.14中，为易于理解，把缓冲站画成了一个2维的物体，实际上，缓冲站可以只是一个两位宽的线性数组，访问地址由全局历史位和分支地址中的相应位拼接而成。在图3.14的简单例子中，一个（2，2）缓冲器的全部入口为64个，因为4个低位地址位和2个全局位合起来就是一个6位地址，可以访问64个计数器。

与标准的2位预测器方案比较起来。相关分支预测器有哪些优点呢？要客观地比较它们，就必须比较使用了相同数量状态位的预测器。在一个（m，n）预测器中，所需要的位数是：

2m × n × 分支地址所能选择的预测数目

而一个没有全局历史记录的两位预测器则仅仅是一个（0，2）预测器。

例题3.4：在前面所举的（0，2）分支预测器中总共有多少数据位？而在图3.14所示的分支预测器中又有多少数据位？

解：前面的预测器有4K个入口可供分支地址选择，故数据位的总共数目是：

20 × 2 × 4K = 8K

在图3.14所示的预测器中有：

22 × 2 × 16 = 128位

而要在性能上比较相关预测器和图3.8的两位预测器，还需要知道相关预测器有多少个入口。

例题3.5：一个有8K数据位预测缓冲站的（2，2）预测器有多少个分支选择入口? 解：由等式：

可知

分支选择的入口数目 = 1K

图3.15给出以前的有4K个入口的两位简单预测器和一个有1K个入口的（2，2）预测器的性能比较。从中可见，这种预测器的性能超过了有相同数目状态位的两位预测器，在很多情况下，它甚至超过有无限个入口的两位预测器。

22 ×2 × 分支选择的入口数目= 8K

4－26

SPEC89 基准测试程序 无限多项 每项2位 4096项 每项2位 预测不正确率 1024项(2,2)

图3.15 两位预测器的比较。第一个是有4096个入口的不相关预测器，接下去是一个有无

限入口的两位不相关预测器，以及一个有两位全局历史位和总共1024个入口的两位预测器。

在所有各种各样的相关预测器中，（0，2）和（2，2）预测器中最有趣的。一个不使用分支地址的预测器其性能将怎样呢？例如一个（12，2）预测器总共有8K数据位，但不使用分支地址来访问，而仅仅使用全局分支历史记录来访问。令人惊奇的是，如果给予足够的全局分支历史记录，且状态表也足够大的话，其性能能够超过不相关的两位预测器。

3.4.3 Tournament预测器：整体局部自适应预测器

从相关分支预测器与标准两位预测器的比较中可以看出，后者只使用了局部信息而没有考虑其他一些重要分支，而前者使用了全局信息，从而改善了性能。

Tournament预测器把这种方法推进了一步，它使用了多个预测器，一个用来记录全局信息，一个记录局部信息，然后用一个选择器综合两个信息进行选择。因此，这种预测器能在中等大小（8K－32K位）和非常大的预测位两种情况下都有很好的表现。

4－27

Tournament预测器是多分支预测器中最受欢迎的一种。多分支预测器同时使用多层分支预测表，并用一种算法在多个预测器中选择结果。接下来我们会看到这种选择的几个因素。现有的Tournament预测器在每个分支依靠一个2位饱和计数器的4个状态对两个预测器做出选择，具体状态转换图见图3.16。

使用预测器1 使用预测器2

图3.16 Tournament预测器的状态转移图，根据使用的预测器的不同有4个状态。当正在预

测的预测器正确，且其他预测器预测错误时，计数器加1，否则减1。

Tournament预测器的优点是能够对被测分支选择出正确的预测器。图3.17给出了Tournament预测器依靠基准测试程序和分支情况来选择局部或全局预测器的方法。这种预测器能够在每个分支上选择出局部预测器或全局预测器，这对于整数基准测试程序非常重要。

使用局部预测器的百分比

图3.17 使用SPEC89基准测试程序测试的Tournament预测器相对于局部预测器的百分比。

Tournament预测器从一个局部两位预测器和一个叫做gshare的两位局部/全局预测器中进行选择。Gshare通过分支地址位和全局历史记录进行索引。它的性能和前面所述的相关预测器相似。在这个例子里，每一个预测器有1024项，每项2位，总共6K位。

4－28

图3.18给出了三种的不同位数的预测器的性能，这些预测器都使用SPEC89基准测试程序。我们知道，局部预测器的位数提高到了一定程度就不能再改善效果，而相关预测器仍有相当的提高，而Tournament预测器更是如此。

局部两位预测器 预测不正确率 相关预测器 Tournament预测器 全部预测器的大小 图3.18 三种不同的预测器使用SPEC89基准测试程序下随着全部预测器位数的增加预测不

正确率的变化。这些预测器是：一个局部的两位预测器，一个在图中每一个点按照最优构造的相关预测器和一个使用图3.17结构的Tournament预测器。

3.4.3.1 Alpha21264的分支预测器

Alpha21264分支预测器是截至到2001年最为成熟的一种分支预测器，它有一个

Tournament预测器，使用4K个两位计数器，分别用分支局部地址来索引，以对局部预测器和全局预测器进行选择。全局预测器也有4K个入口，用最后12个分支索引，且每个入口都是一个标准的两位预测器。

局部预测器有两层，上面一层是个局部历史记录，有1024个入口，每个入口10位，分别对应这个入口最近的10个分支；即一列中分支执行了10次，它们将变成全1，如果分支有时执行有时不执行，记录中就是01相间的。这种10位历史记录允许对10个分支进行记录和预测。从局部历史记录选择出的入口用来对一个1K的入口表进行索引，这些入口由3位计数器构成，以提供本地预测。这种结合共使用了29位，大大提高了分支预测的精度。对于SPECfp95基准测试程序，1000条指令造成不到1次的预测失败，而SPECint95则为平均11.5次预测失败。

3.5 高效的指令传送机制

在高效流水线特别是多发射流水线中，仅仅分支预测还是不够的，还需要一个宽带的指令流。在近年来，每个时钟周期发射4～8条指令才算宽带。为此，我们在这一节中先来认识3个基本概念：分支目标缓冲站、集成的预取指令部件和用于处理间接分支的返回地址预测器。

4－29

3.5.1 分支目标缓冲站

为了减少5段流水线中的分支损失，必须在IF流水段的末尾就知道下一条应该访问的指令地址，此即意味着应该知道下一条指令是否是分支指令，如果是分支指令，则其指令地址又是什么？如果下一条指令是分支指令且可以知道其地址，那么分支造成的延迟就是0。用一个分支预测缓冲站来存储分支后面的下一条指令地址，这种缓冲站就叫做分支目标缓冲站或分支目标高速缓存。

对于标准的5段流水线，分支预测缓冲站是在指定的ID流水段被访问的，所以在ID流水段的末尾才能知道分支目标地址（因为是在ID流水段计算的）、分支未选中时的地址（在IF流水段计算）和预测结果，所以在ID流水段的末尾，就可以知道下一条要访问的指令。对于分支目标缓冲站，其访问操作是在IF流水段使用预取指令的地址来访问的。如果猜中的话，即可在IF流水段的末尾知道下一条指令的地址，这比使用分支预测缓冲站的方法早了一个时钟周期。

因为要在对指令译码之前就得到下一条指令的地址，因此必须知道取到的指令是否是一条将要执行的分支指令。图3.19所示为分支目标缓冲站的样子，如果取来指令的PC与缓冲站中的某一个PC正好相符，则相应的预测的PC即作为下一个PC。在第五章中将进一步详细讨论Cache技术，下面可以看到该分支目标缓冲站在本质上与Cache所对应的硬件是相同的。

预取指令的PC 查找 分支目标缓冲站入口数量 预测的PC 相等，是分支指令，将预测的PC作为下一条指令的PC 不等，被认为不是分支指令，正常执行 分支被预测为转移成功或不成功

图3.19 分支目标缓冲站。将取得的指令地址PC与第一列中的一套指令地址相符合。如果

待取PC与其中某一个入口相符，则待取指令即为一条分支指令，相应的第二个域，即是下一条指令的PC。下一次的取指令操作即可以从该地址开始。第三个域，可用作额外的预测状态位。

如果在分支目标缓冲站中发现一个相符的入口，则取指令操作即可从预测的PC开始执行。必须注意到的是因为预测的PC被送出去时，还尚未知道该指令是否是分支指令，所以该入口必须正好是对应于这条指令的。如果没有检查入口与PC是否相符，那么，对于不是分支的指令，就会对应于错误的PC，从而导致处理机速度的降低。由于转移不成功的分支与非分支情况下顺序执行时的情况是相同的，因此只需要把预测要被执行的分支保

4－30

本文来源：https://www.bwwdw.com/article/8t1t.html