指令级并行及其动态开发.doc

第三章 指令级并行及其动态开发“谁第一？”“美国。”“谁第二？”“没有第二，先生”对话发生于观看帆船竞赛的两个人之间，这个后来叫做“美国杯”的帆船竞赛每几年就要举行一次。灵感来自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也使用了很多这种静态技术。本章我们将分别从程序和处理器两个方面来讨论它们对指令级并行性的限制。我们还将研究程序结构和硬件结构之间的一些相当重要的映射关系，这对我们理解和掌握某些问题是至关重要的，这些问题包括一个程序实体是否会影响，和在什么情况下会影响处理器的性能。我们知道，流水线机器的CPI（执行每条指令所用的时钟周期数）等于基本CPI加上各种暂停所使用周期数的和：流水线CPI = 理想流水线CPI + 结构暂停 + 写读暂停+ 读写暂停 + 写写暂停 + 控制暂停其中，理想流水线CPI是指可实现的最大指令流量。减少等式右边的每一项，可以减少总的流水线CPI，从而增加IPC（每个时钟周期的指令流量）。在本章中将看到，我们要介绍的增加IPC的技术使得处理结构、数据和控制方面的问题如何显得更为重要。上面的等式描述了本章中将要讨论的用以减少流水线实际CPI的各种技术。图3.1表示一些将要讨论的技术及它们对CPI的影响。技术减少等式右边的某项章节继续执行和绕行潜在的数据暂停A.2延迟分支和简单分支调度控制暂停A.2基本动态调度（记分板）由真相关性产生的数据暂停A.8重命名的动态调度数据暂停、反依相关和输出相关产生的暂停3.2动态分支预测控制暂停3.4每个周期发射多条指令理想CPI3.6预测所有数据暂停和控制暂停3.7动态内存非二义化涉及内存的写读暂停3.2，3.7循环展开控制暂停4.1基本编译器流水线调度写读暂停A.2，4.1编译器进行相关性分析理想CPI和数据暂停4.4软件流水和路径调度理想CPI和数据暂停4.3编译器预测理想CPI和数据暂停4.4图3.1 附录A、第三章和第四章将要讨论的主要技术及影响到的上面CPI等式中的相关项目。其中，数据暂停是指各种各样的数据冒险造成的暂停，就是写读（先写后读）暂停、读写（先读后写）暂停或写写（写后再写）暂停。在详细讨论上述技术以前，需对这些技术所涉及到的概念加以解释说明，它们决定了指令级并行性可以被开发的程度。3.1.1 指令级并行性在本章和下一章中讨论的所有技术都是用于开发指令序列中的并行性的。从上面可以看出，这种类型的并行性就叫做指令级并行性或ILP（instruction-level parallelism）。在一个基本块（除了入口和出口之外没有其它分支的线性指令序列）中可开发的并行性是很小的。例如，在第三章中看到的定点程序中平均动态转移频率在15%到20%之间，即每4条到7条指令中间将执行一条分支指令。由于这些指令很可能是相互关联的，所以我们在一个基本块中可以开发的指令重叠数将会远小于7。为了能够取得更大性能的提高，就必须开发多个基本块之间的指令级并行性。提高指令级并行性的最简单也最常用的方法，是一个循环中的不同循环体并行执行。这类并行即通常所说的循环级并行。以下是一个简单的循环程序，完成由1000个元素组成的两个数组的相加，此程序是完全可并行的：for (I = 1; i = 1000; i = I + 1)xi = xi + yi;这个循环的每一个循环体都可以与其它任何一个循环体重叠执行，虽然在每一个循环体内部可重叠的机会几乎没有。有多种技术可以将上述循环级的并行转化成指令级并行，这些技术基本上要么由编译器静态地（下一章的内容）或由硬件动态地（本章要讨论的内容）对循环展开。开发循环级并行的另一种重要方法是使用向量指令（见附录G）。基本上，一条向量指令是对一系列数据项进行操作。例如，上述代码可以在一个典型的向量处理机上用4条指令执行：2条从内存中读取向量x和向量y的指令、一条加法指令和一条保存结果的指令。当然，这些指令可以采用流水线方式执行，虽然有相对比较长的延迟时间，但这些延迟时间是可以被重叠的。向量指令和向量处理机的操作在附录G中有详细描述。虽然向量处理的思想要早于本章中大部分将要讨论的指令级并行技术，但是，采用指令级并行技术的处理机还是正在取代着基于向量处理的处理机，而向量指令集则有望在图象处理、数字信号处理和多媒体技术中得到应用。3.1.2 数据相关性和数据冒险判断指令之间是否有相关关系，对于判断程序中有多少并行性以及如何开发并行性是十分重要的。具体说来，要开发指令之间的指令级并行性，就必须清楚哪些指令是可以并行执行的。如果两条指令是可并行的，那么它们可以在流水线上同时执行而不会造成暂停，当然这里假定流水线资源部件是充足的（因此不存在任何资源冲突）。若两条指令是相关的，那么是不可并行的，虽然有时它们可以部分地重叠执行。因此，最重要的问题就是要判断指令之间是否存在有相关关系。3.1.2.1 数据相关有3种不同类型的相关：数据相关（也叫真数据相关）、命名相关和控制相关。如果下面的条件之一成立，则指令j数据相关于指令i：l 指令i产生的结果为j引用。l 指令j数据相关于指令k，而指令k数据相关于指令i。第2个条件指出，如果两条指令之间存在有上述一条相关链的话，即它们之间也是相关的。这条相关链甚至可以贯穿整个程序。举个例子，考虑如下使数组元素增值的一段代码。在下面的代码段中，0(R1)存放数组元素的首地址，8(R2)存放数组元素的尾地址，F2中存放增加量S。Loop: L.DF0, 0(R1)；F0=数组元数ADD.DF4, F0, F2；加上F2中的标量S.DF4, 0(R1)；保存结果DADDUIR1, R1, # -8；数组指针递减8个字节BNE R1, R2, Loop；R1R2时转移在上述例子中，相关序列包括浮点数：Loop:L.DF0, 0(R1)；F0=数组元素ADD.DF4, F0, F2；加上F2中的标量S.DF4, 0(R1)；保存结果和定点数：DADDIUR1, R1, # -8；数组指针递减；8个字节（一个双字）BNER1, R2, Loop；如果R10，则转移图中箭头所示的都是相关序列，每条指令均相关于前面一条指令。此处的箭头及以后例子中将要出现的箭头都表示为了得到正确结果指令之间必须保持的执行顺序。箭头从一条必须先执行的指令指向后执行的指令（即箭头头部所指的指令）。如果两条指令之间有数据相关，那么它们就不能同时执行或是完全重叠执行，这种相关性说明它们之间存在一条有一个或多个写读冒险的相关链，同时执行这些指令会造成正在流水的处理机检测到这种冒险并插入暂停，从而减少甚至取消指令之间的重叠。在一个依靠编译器进行调度来消除冒险的处理机中，编译器不能调度相关的指令使它们完全地重叠执行，因为那样会使执行结果出错。指令序列中存在的数据相关反映出产生该指令序列的程序源代码中也存在有这种相关关系，这种源代码中的相关性一般是不能破坏的。相关性是程序的一个特性，是否一个相关会导致实际的冒险，是否该冒险会造成暂停，这是流水线结构的基本特性。这一特性对于理解指令级并行性如何被开发利用是很重要的。在所举的例子中，指令DADDIU和BNE之间存在有数据相关，由于我们把流水线的分支检测移到了ID流水段，因此相关造成了1次暂停。若分支检测仍保留在EX流水段的话，这个相关就不会引起暂停。当然，循环的延时仍然是两个周期，而不是一个。相关性的存在只是预示着存在有冒险的可能性，而是否确实有冒险及造成多少个暂停周期，则是具体流水线的特性。数据相关性有以下几个重要特性：（1）相关性预示存在有冒险的可能性；（2）相关性决定必须遵循的计算顺序；（3）相关性决定可被开发的并行性的上界。这几个限制在第3.8节中还会详细地展开阐述。由于数据相关性会限制可以开发的指令级并行性，因此本章和下一章的一个主要任务就是克服这些限制。这可以从两个不同的方面来解决：保持相关关系但避免冒险，或通过变换代码来消除相关关系。对代码进行调度是保持相关关系并避免冒险常用的一个最基本方法。在本章中我们将考虑通过硬件策略在程序执行过程中动态调度指令。由此我们可以发现，有一些相关性将被消除，这主要是由软件方法实现的，并在某些情况下使用了一些硬件技术。一个数据在指令中的流动既可能通过寄存器也可能通过内存。当数据流发生在寄存器中时，由于指令中的寄存器名均是固定的，因而相关关系可以简单明了地检测出来，虽然有分支指令存在时会复杂一些，因为为了保证正确性，编译器和硬件的一些功能都会受到限制。而涉及到内存操作的数据流之间的相关关系则相对较难被检测出来，因为即使两个形式上完成不相同的地址，也有可能指向同一个内存单元。例如，100（R4）和20（R6）有可能表示同一个内存地址。此外，load和store指令的有效地址在不同的时刻执行的地址也有可能是不同的（即20（R4）和20（R4）可以是不同的值）。这些都进一步使相关性的检测工作复杂化了。在本章里，我们将研究采用硬件开发存储器中的数据相关性，虽然这种方法也存在有种种限制。检测这种相关的编译器技术将在下一章中讨论，这在开发循环级并行性时也是一个很重要的方法。3.1.2.2 名字相关第二类相关关系是名字相关，当两条指令使用同一个寄存器或是同一个内存地址时，即发生了名字相关，有名字相关的指令之间不存在数据值的流动。对于指令i和j（i在j之前），它们之间可能存在的名字相关有两种类型：1反相关，指令j写一个寄存器或一个内存单元，而指令i则去读该寄存器或内存单元，且i的执行在前。此时必须保证指令的原来顺序，以确保i能读到正确的值。2输出相关，指令i和j对同一个寄存器或内存地址执行写操作，这种操作顺序必须得到保证，以使最后写入的值得以保存。反相关和输出相关都是名字相关，与真正的数据相关性相反，指令间没有相互传递的数值，这也意味着有名字相关的指令是可以同时执行或进行重新排序的。如果指令中的名字可以改变，就能使指令之间不再存在这种冲突，这种换名操作对于寄存器来说比较容易，叫做寄存器换名。寄存器换名可由编译器静态地或由硬件动态地实现。在描述由分支引起的相关性之前，我们先来看看相关性和流水线数据冒险之间的关系。3.1.2.3 数据冒险当指令之间存在相关性，而且它们的执行时间相近时，可能会在流水线中重叠操作，或者指令的重新排序改变了有相关的操作数的访问顺序，这时数据冒险就发生了。正是由于这种相关性的原因，我们必须保持指令的执行顺序，即由源程序决定的指令在正常串行执行（一条一条无重叠执行）时顺序。只有发现和避免数据冒险才能保证程序执行顺序的正确性。数据冒险可以按照指令中读写访问的顺序分为三类。一般来说，数据冒险按在流水线中要保留的读写执行顺序来命名。比如有两条指令i和j，i在j之前执行，则可能的数据冒险有以下几类：l 写读冒险（RAW）：如果j想在i写之前去读数据，读出来的将是旧值。这是最经常发生的一种冒险，对应于真数据相关。要保证执行结果的正确就必须保证j在i之后读取数据。在简单的5段静态流水线（见附录A）中，一个ALU操作想读取在它之前刚写入的数据将导致一个写读冒险。l 写写冒险（WAW）：当j在i写入数据之前写同一个单元（寄存器或内存地址）时就会发生写写冒险。如果写操作以错误的顺序执行，会导致指令结束后的操作数是错误的，在这里操作数本应是j写入的值，但如果j先写，则指令结束后操作数结果为i写入的值。这种冒险对应于输出相关。写写冒险一般在允许多个写操作在流水线中各个阶段都允许发生的情况下，或当允许在前面的指令发生暂停时后续指令继续执行的时候发生。附录A中的典型的5段整数流水线仅仅在WB阶段写寄存器，因而可以避免此类冒险的发生。不过本章介绍的流水线允许对指令进行重新排序，这便使写写冒险成为可能。写写冒险也能在短整数流水线和浮点运算流水线中（见附录A.5和A.6）发生。比如，一个浮点乘指令要写F4，而后面紧接着的指令也要对F4进行load操作，由于load操作可能先于乘法指令完成，这就造成了写写冒险。l 读写冒险（WAR）：当j先于i改写了i的操作数，则i读的时候将读进一个错误的值。这种冒险是由反相关引起的。读写冒险一般不会发生在静态流水线中即使是深度流水线或浮点流水线也没关系因为这种流水线中的所有读操作（ID流水段）都比写回结果操作（WB流水段）来得早（见附录A）。读写冒险发生的情况有两种，要么在流水线中一些写指令提前完成或一些读指令滞后了，要么指令被重组了，而后者则是本章将要讨论的内容。注意：读读相关（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部分中执行。在如第一章那样的流水线中，控制相关可以通过以下两个方面得到保证。第一，指令按顺序执行，这使得分支指令之前的指令只能在该分支指令之前执行。第二，对控制或分支冒险进行检测，保证控制相关于一个分支的指令在分支转移方向没有确定之前不会被执行到。虽然保留控制相关是保证程序正确执行的简单而有效的做法，但控制相关本身并不是限制性能的基本因素。从上面的例子中还看到，编译器可以去掉某些控制相关。在某些情况下，有可能违反控制相关去执行某些还不该轮到执行的指令，仍然能够得到正确的结果。可见控制相关并不是必须保留的关键性因素。实际上，控制相关所要求保证的是对程序正确执行起关键性作用的两个特性：异常行为和数据流。保留异常行为即意味着不管怎么改变指令执行的顺序，都不能改变原先程序中的异常情况。也可说是指令执行顺序的改动不能在程序中引起新的异常，一个简单例子可以说明维持控制相关是如何防止上述问题的。考虑如一下代码：DADDUR2, R3, R4BEQZR2, L1LWR1, 0(R2)L1：在这个例子中，很容易看出，如果不考虑由R2引起的数据相关问题，就可能会改变程序的执行结果。另外一点却不那么明显：如果忽略控制相关而把LW指令移到分支指令之前，则有可能引起内存保护异常的错误。注意，这里没有其它任何数据相关阻止我们调换BEQZ指令和LW指令，有的只是控制相关。如果需要在保持数据相关的情况下重组指令，我们将忽略分支引起的异常。在第3.7节中，我们将采用一种硬件技术预测法来消除这种异常问题，而在下一章中，为了解决这个问题，我们将看到其他一些技术。数据流是维持控制相关所要保证的第二个特性。数据流即指令中确实存在的数据定值和引用的实际数据流动关系。分支指令使得数据流是动态变化的，因为分支指令使得某一指令中的数据可能来自于多个不同的地方。从另一方面讲，仅仅维持数据相关是不够的，因为一条指令可能对多个处理器产生数据相关，究竟那个处理器提供数据给一条指令是由源程序来决定的，而要保证源程序的顺序就需要维持控制相关。考察如下代码段：DADDUR1, R2, R3BEQZR4, LDSUBUR1, R5, R6L:ORR7, R1, R8在这个例中，指令OR中所用到R1中的值取决于分支转移是否成功。数据相关性只能处理静态的读、写顺序，仅仅保留一个数据相关关系并不能保证程序执行结果的正确性。在这个例子中，仅仅保证OR指令数据相关于ADD或SUB指令并不足以保证程序正确执行。在程序正确执行时，数据流关系也是必须保证的：若分支转移不成功，则OR指令引用的是SUB指令中的R1值；反之，引用的是ADD指令计算的R1值。保留SUB指令对于分支转移的控制相关，可以防止对数据流的非法改动。因此，这里的减法操作不能移到分支指令之前执行。在第3.7节中，将会看到，预测法和条件指令是如何在保持数据流不变的情况下，改变控制相关从而解决异常情况的。有时，改变控制相关也可以既不影响异常行为也不影响数据流。看下列代码：DADDUR1, R2, R3BEQZR12, skipnextDSUBUR4, R5, R6DADDUR5, R4, R9skipnext: ORR7, R8, R9如果知道DSUBU指令的目标寄存器R4在标号skipnext之后不会被用到（一个值是否会被将来的指令用到的性质被称为存活性），那么在分支指令之前就改变R4的值也不会影响到数据流的状况，因为R4在skipnext后不会被用到，即相当于死亡了。因此，如果DSUBU指令也不会产生异常的话，就可以把DSUBU指令移到分支之前，程序的执行结果也不会因此而改变。如果分支转移确实成功，那么，虽然SUB指令会无用地执行，但也不会影响到程序的结果。这一类的代码调度有时也叫预测法，编译器这时必须猜测分支运行的结果（在这种情况下，相当于猜测分支转移不成功）。有关编译器的预测机制将在第4.5节中作更详细讨论。对产生控制暂停的控制冒险进行检测可以保证控制相关性。很多软硬件方面的技术都可以消除或减少控制暂停。例如，第一章介绍的延迟转移可以减少控制冒险造成的暂停；调度一个延迟的分支需要编译器保持原先的数据流。本章剩下的内容主要是利用硬件来挖掘潜在的指令级并行性。一个已经编译的程序中的数据相关性决定了指令级并行性在多大程度上能够得到改善。我们面临的挑战就是尽量减少实际的冒险及其引发的暂停。通过维持代码中必要的真数据相关性，我们能在开发可并行性方面更加得心应手。3.2 采用动态调度克服数据冒险一个简单的静态调度的流水线负责取指令并发射指令，当刚取到的指令与已经在流水线中的指令之间存在有数据相关，且不能通过旁路技术或相关直接通路技术予以避免时，就暂停取指令和发射指令。相关直接通路技术能够有效减少流水线的延迟时间使得一些相关关系不会引起冒险。如果存在有实在不可避免的数据相关，那么检测冒险的硬件将停止有相关的指令及其后面的指令进入流水线，直至相关性被消除之前不会再取出和发射新的指令。本节我们将介绍一种重要的方法动态调度法，即由硬件动态调整指令执行顺序以减少暂停的影响。动态调度法有以下几个好处：它能够处理某些在编译阶段无法知道的相关关系（如涉及内存引用时），并简化编译器设计；或许最重要的是，它能够允许在别的流水线机器上编译的指令在不同的流水线上也能有效运行。在第3.7节中，我们将介绍一种建立在动态调度基础上的硬件预测技术，这种技术具有相当好的性能优势。当然，这些优势是以硬件复杂度显著增加为代价的。当一个采用动态调度方法的处理机无法消除真数据相关时，它会尽量避免相关所带来的暂停。相比之下，依赖于编译器的静态流水线调度方法（将在下一章中介绍），则是尽量通过分离有相关的指令使它们不会导致冒险，从而去减少暂停的影响。当然，采用静态调度方法生成的代码也可以在采用动态流水线调度的处理机中运行。3.2.1 动态调度思想附录A所述流水线技术的一个主要限制是它们全部使用按序发射指令的机制，即如果指令在流水线中被暂停，那么后继指令也无法前行。因此，若两条紧挨着的指令存在有相关关系，就会引起流水线的暂停。对于有多个功能部件的机器，就会造成这些功能部件的闲置。如果指令j相关于正在流水线中执行的指令i，而i的运行时间又很长，那么所有j后面的指令也不得不停下来直至i执行完成之后，j才能开始执行。考虑如下例子：DIV.DF0, F2, F4ADD.DF10, F0, F8SUB.DF12, F8, F14ADDD相关于DIVD致使流水线出现暂停，其后面的指令SUBD也因此而不能执行，尽管SUBD所需要的数据并不相关于流水线中的任何指令。如果不要求指令按序发射，就可以消除这种对性能提高的限制。在第一章所讨论的5段流水线中，资源冒险和数据冒险均是在指令译码阶段（ID）进行检测的。若一条指令可以正确执行，才会从ID发射出去。为了使上例中的SUB.D指令能够开始执行，就必须把发射阶段分离成两个阶段：检测资源冒险和等待不存在数据冒险的情况。在发射指令时仍能对资源冒险进行检测，这样既可以使用按序发射指令的方法，又可以要求指令在操作数准备好时就可以开始执行。这时流水线采取的是乱序执行方式，指令的结束也是乱序的。乱序执行引进了WAR和WAW冒险，而这些冒险在5段整数流水线和其扩展的对顺序浮点流水线中是不存在的。考虑如下MIPS浮点代码段：DIV.DF0, F2, F4ADD.DF6, F0, F8SUB.DF8, F10, F14MUL.DF6, 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，正是该机器发展了记分板机制。我们将把注意力集中在一个更成熟的技术上，即Tomasulos算法，这个算法对记分板机制做了几个大的改进。如果需要对这些概念有个粗略的了解，可以参考附录A，在那里完整的讨论了记分板机制并给出了几个例子。3.2.2 用Tomasulo算法进行动态调度在IBM360/91的浮点部件中使用了一种重要的动态调度方法，它能够使指令在有冒险存在的情况下仍能继续执行。这种方法是由Robert Tomasulo 提出的，方法也因此而命名。Tomasulo方法跟踪指令获得操作数的时间，以减少写写冒险和写读冒险。在使用此方法的处理器的众多方案中，始终拥有一个共同的特点，即跟踪指令的相关性，使得指令所需要的操作数一旦准备好就允许执行，同时运用寄存器换名技术来避免读写和写写冒险。IBM360/91的出现在Cache商业化以前。IBM的目标是希望从专门为360系列设计的编译器和指令集中提高浮点计算的性能，而不仅仅依赖专门为尖端处理机而设计的编译器。360系统结构只有4个双精度浮点寄存器，这限制了编译器调度的有效性，也是促使Tomasulo方法出现的一个原因。此外IBM360/91具有较长的内存访问和浮点操作延迟，而Tomasulo方法正好可以弥补这些弱点。在本节的最后，还可以看到Tomasulo方法是如何支持多个循环体重叠执行的。下面，在MIPS指令集上的浮点单元和存取单元上解释该算法。MIPS与360最基本的差别是后者中出现了寄存器存储器指令。由于Tomasulo方法使用了一个取数功能部件，因此对于寄存器存储器寻址模式不需做太大的改动，最基本的变动是增加了一条总线。IBM360/91是采用流水功能部件的，而不是多功能部件，但是这两者不存在本质的区别，以下讨论算法时不妨假设是多功能部件的情形，两者之间只是一个简单的概念性扩展。正如我们将要看到的，当指令所需要的操作数全部到达之后才开始执行指令，就可以避免写读冒险，而通过寄存器换名可以避免由名字相关引起的读写冒险和写写冒险。寄存器换名是对那些相关目标寄存器重新命名，使得乱序执行时的写操作不会影响需要那个被写数以前值的指令的正确执行。为了更好地了解采用寄存器换名技术消除读写冒险和写写冒险的原理，我们可以看下面一段代码，这段代码包括了这两种冒险：DIV.DF0, F2, F4ADD.DF6, F0,F8S.DF6, 0(R1)SUB.DF8, F10, F14MUL.DF6, 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.DF0, F2, F4ADD.DS, F0, F8S.DS, 0(R1)SUB.DT, F10, F14MUL.DF6, F10, T此外，接下来所有使用F8的地方必须用T来代替。在这个代码段里，所有的重命名过程都可以由编译器来完成，不过，要发现以后使用F8的所有地方，需要一个好的编译器或者硬件支持，因为在上述代码段和以后使用F8的地方之间可能存在一些复杂的分支语句。我们将会看到，Tomasulo算法会很好地解决跨分支重命名的问题。在Tomasulo算法中，寄存器重命名的功能是通过保留站来实现的。在保留站中缓存了即将要发射的指令所需要的操作数，其工作的基本思想是尽可能早地取得并缓存一个操作数，从而避免必须读操作数时才去寄存器中读取的情况。此外，即将执行的指令也会由保留站取得所需要的操作数。当出现多个操作写同一个寄存器时，只允许最后一个写操作实际更新寄存器。在指令发射之后，它所需要的操作数对应的寄存器也将换成保留站的名字，这一过程就是寄存器换名技术。由于可以使用比真正的寄存器还多的保留站，因此可以消除原先编译器所不能消除的冒险。在讨论Tomasulo算法的过程中，还将继续讨论寄存器换名技术并介绍如何进行换名，以及换名方法是如何消除冒险的。使用保留站与集中式寄存器堆相比有两个重要的特点。第一，在这里，冒险检测和执行控制是分散的，每一个功能部件的保留站控制该部件中指令的执行时间。第二，结果将从保留站所缓存的地方直接送到功能部件中，而不是通过寄存器传送，为此使用了一条公共结果总线。该总线允许所有等待该操作数的功能部件可以同时取到该数据（在IBM360/91中，这条总线也叫公共数据总线或CDB）。注意，在拥有多个执行部件和每个时钟发射多条指令的流水线中需要多条结果总线。图3.2给出了基于Tomasulo算法的MIPS处理器的基本结构，该结构包括浮点部件和内存部件，但是没有表示出执行控制状态表。保留站中保存着已经发射并等待到功能部件中去执行的指令，此外还有指令所需要的源操作数（这里可能是具体的操作数的值，也可能是可提供操作数的保留站编号）。从指令部件来地址数据内存部件公共数据总线浮点乘法器浮点加法器保留站操作数总线浮点操作读数缓冲站写数缓冲站Load/store操作浮点寄存器指令队列图3.2 基于Tomasulo算法的MIPS浮点部件的基本结构。浮点操作从指令部件以先进先出(FIFO)的方式送至指令队列中，保留站中保存了运算符和操作数，及检测和解决冒险所需要的信息。读数缓冲站有三个功能：负责保存有效地址的各个部分直到地址计算完成，监视正在等待访问内存的其他需求，对于已经执行完成的访问存储器操作，等待保存CDB上出现的结果。同样，写数缓冲站也要保存那些有效地址的各部分直到地址计算完成，保留正在等待数据值的内存目标地址，保留地址和值直到内存单元可以使用。所有从浮点部件(FP)和读数部件出来的结果均送至CDB上，从而可以送至浮点寄存器堆和保留站及写数缓冲站中。浮点加法器具有加法和减法的功能，浮点乘法器则实现乘法和除法运算。在读数缓冲站和写数缓冲站中保存着从内存读出或即将要写到内存中去的数据或数据地址，它们的工作方式与保留站一样，因此，我们在没有必要时就不特意区分它们。浮点寄存器通过一组总线连接到功能部件上，并通过一条总线连到写数缓冲站中。所有从功能部件和存储器中出来的结果均被送到公共数据总线上，并到达所有需要该操作数的地方（不可能是读数缓冲站）。除了读数缓冲站，所有的缓冲站和保留站均设置有标志域，这些标志主要用于冒险控制机制。在开始讨论保留站和算法的细节之前，不妨先看看指令运行所经过的几个阶段正如我们讨论附录A中的5段流水线一样。与前面相比，操作数的传送方式发生了变化，这中间只需要3个阶段：1发射从浮点运算队列中取得一条指令，这条指令按照先进先出(FIFO)的方式保留在队列中，以保持数据流的正确性。若指令的操作数已经准备好，而保留站中还有空位置，就发射该指令至保留站中，并把寄存器中已有的操作数也送至保留站中。如果没有空余的保留站，则说明发生了资源冲突，该指令只好等待保留站或缓冲站出现空闲。如果指令的操作数还不在寄存器里，则跟踪产生操作数的功能单元。在发射阶段，进行寄存器换名工作，以消除读写冒险和写写冒险。2执行若还有操作数没有准备好，则监视公用数据总线(CDB)，等待源操作数。当一个操作数计算出来之后，就放到相应的保留站中。当指令所需要的源操作数均出现之后，就可以执行该运算。由于这里的指令需要等待操作数可以使用后才能执行，所以写读冒险不会产生。必须注意，虽然不同的功能单元可以同时开始执行几条指令，但是，当发生几条指令在同一个功能单元同时变得可以执行时，功能单元必须选择其中的一条指令执行一个功能单元在同一个时钟周期只能执行一条指令。对于浮点保留站，选择可以是任意的，而对读数和写数缓冲站来说，就相对复杂一些。读数和写数需要两个执行步骤：首先在基址寄存器有效时计算有效地址，然后再将数据读入读数缓冲站或从写数缓冲站写入内存。读数缓冲站在内存单元有效时就立即执行读内存操作，而写数缓冲站则保存数据等待内存单元有效时将数据写入内存。这样，通过有效地址计算，读数和写数都得以保留源程序的执行顺序，从而避免了访问内存的冒险。为了维持异常行为，任何指令在它之前的分支指令没有完成之前不得开始执行。这种限制保证了指令只在异常应该被执行时产生。在使用了分支预测技术的处理器（使用动态调度的处理器都使用了分支预测技术）中，这意味着处理器需要知道分支预测是正确的，这样才能允许分支后的指令执行。当然，通过记录指令发生（而不是产生）的异常，我们可以不必暂停指令的执行直到进入写结果阶段。我们发现，预测技术提供了一种更有弹性，也更完整的方法来处理异常，我们将在今后进一步讨论这个问题。3写回结果当结果出来之后，送至CDB，进而写回到寄存器中，或被其他保留站（包括缓冲站）读取。这里，缓冲站会向内存写回数据：当地址和数据值都有效则写入内存单元，并结束缓存。检测并消除冒险的数据结构附在保留站、寄存器堆、读数缓冲站和写数缓冲站中，当然，其功能各不相同，所保存的信息也稍有不同。除了读数缓冲站之外，其他部件均带有一个标志域。标志域本质上是换名时用到的虚拟寄存器的名称。在这个例中，标志域是一个4位结构，它表示5个保留站中的某一个或是6个读数缓冲站中的某一个。下面将会看到这一作用相当于11个结果寄存器（而不是360系统结构中的只有4个双精度寄存器）。在一个需要更多物理寄存器的处理机中，可以通过换名方法取得更多的虚拟寄存器。标志域指明产生源操作数的指令所在的保留站。当指令被发射并等待操作数时，标志域会指向产生该操作数的保留站号，而不是指向目标寄存器。而诸如0等的无用的值，则表示操作数已经存放于寄存器中。由于保留站多于实际寄存器的数量，所以通过使用保留站进行换名，可以减少写写冒险和读写冒险。在Tomasulo方法中，保留站作为扩展的虚拟寄存器使用。在其它方法中，则可能要使用额外的寄存器或类似排序缓冲站的结构等，在第3.7节中会涉及到这类情况。为了描述Tomasulo算法，在不引起混淆的情况下，仍将使用记分板机制中的术语，IBM360/91的术语也列出如下。值得重新强调的一点是，Tomasulo算法中的标志域指向的是产生所需结果的缓冲站或功能部件，而不再是寄存器名。指令发射到保留站之后，寄存器名即被抛弃。每一个保留站有7个域：l OP对源操作数S1和S2所做的运算。l Qj，Qk产生相应源操作数的保留站。若值为0则表示Vj或Vk中的值是有效的，或是不需要的。（在IBM360/91中称为接收部件(SINK unit)或源部件(SOURCE unit)。）l Vj，Vk源操作数的值。在IBM360/91中称为接收端和来源，并注意到对每次操作，V域或Q域中仅有一个是有效的（在IBM360/91中称这些域为接收域和源域）。l A读数和写数时计算内存地址的信息。一开始，指令的立即数域被保存在这里。地址计算后，这里保存的是有效地址。l Busy指示该保留站及相关的功能部件正在使用。对于寄存器堆，则对应一个域Qi。l Qi保存保留站号。在该保留站中进行的运算，其结果值将存入该寄存器或缓冲站中。若Qi为空（或0），则表示当前不会有运算结果要存到该寄存器或缓冲站中。对于寄存器，这也意味着寄存器中的内容不会被改变。读数和写数缓冲站还各自要求一个A指示域，用于在第一步执行结束后保存有效地址的结果。在下一节中，我们将首先看一个例子，通过这个例子我们将了解以上所说的那些机制是如何工作的，并详细学习Tomasulo算法。3.3 动态调度：算法及举例在详细讨论Tomasulo算法之前，首先考察如下代码序列在各个表中所对应的状态信息。例题3.1：首先考察当第一条LOAD指令完成并写回结果时，状态表中信息是怎样的：1：L.DF6, 34(R2)2：L.DF2, 45(R3)3：MUL.DF0, F2, F44：SUB.DF8, F6, F25：DIV.DF10, F0, F66：ADD.DF6, F8, F2解：图3.3给出保留站、读数缓冲站、写数缓冲站及寄存器标志信息。跟在指令名add、mult和load之后的数字代表该保留站的标志域Add1是第一个加法部件取得结果的标志，这里还加进了指令状态表，其作用仅仅是帮你理解算法原理，它并不是实际硬件的一部分。在每发射一条指令之后，运算操作的状态都保存在保留站中。指令状态指令发射执行写回结果L.D F6, 34(R2)L.D F2, 45(R3)MUL.D F0, F2, F4SUB.D F8, F6, F2DIV.D F10, F0, F6ADD.D F6, F8, F2保留站站名忙操作VjVkQjQkA取数1否取数2是Load45RegsR3加法1是SUBMem34+RegsR2取数2加法2是ADD加法1Load2加法3否乘法1是MULRegsF4取数2乘法2是DIVMem34+RegsR2乘法1寄存器状态域名FOF2F4F6F8F10F12F30Qi乘法1取数2加法2加法1乘法2图3.3 所有指令都已经发射，只有第一条load指令已经执行完成并把结果送至CDB时，保留站及寄存器标志的状态。第二条load指令已经完成有效地址计算，正在等待从内存单元读出数据。我们用Regs数组表示寄存器堆，用Mem数组表示内存。注意到一个操作数在任何时候均可以由Q域或V域具体确定。注意，已经发射出去的加法指令在WB阶段有一个读写冒险，它应该在除法指令初始化之前完成。与其他更早、更简单的算法相比，Tomasulo算法的主要优点在于：（1）分散了冲突检测机制；（2）消除了写写和读写冒险造成的暂停。第一个优点来自于分布式的保留站结构和CDB的使用。如果多条指令等待同一个结果，且每条指令均已经读到另一个操作数，那么CDB的广播机制，可以使得这些指令能够同时得到这一个操作数，并同时开始运行。而使用集中式寄存器堆时，等待着的指令只能竞争使用寄存器总线去读取所需要的寄存器中的值。第二个优点是：在保留站中，寄存器换名技术将操作数尽可能早地存入保留站中，从而消除写写和读写冒险。例如，在图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：在上例的代码中：考察当代码执行到M