计算机系统结构

计算机系统结构第一章基本概念第二章指令系统第三章存储系统第四章输入输出系统第五章标量处理机第六章向量处理机第七章互连网络第八章并行处理机第九章多处理机1第五章标量处理机标量处理机--只有标量数据表示和标量指令系统的处理机提高指令执行速度的主要途径提高处理机的工作主频采用更好的算法和设计更好的功能部件采用指令级并行技术三种指令级并行处理机流水线处理机和超流水线(Super-pipelining)处理机超标量(Superscalar)处理机超长指令字(VLIW:VeryLongInstructionWord)处理机三种基本技术先行控制技术流水线技术相关性分析技术动态调度技术2本章主要内容5.1先行控制技术5.2流水线技术5.3相关性分析技术5.4动态调度技术5.5超标量处理机5.6超流水线处理机5.7超标量超流水线处理机35.1先行控制技术先行控制(Lookahead)技术最早在IBM公司的STRETCH机器中采用。先行控制技术的关键是缓冲技术和预处理技术。目前，许多处理机中都已经采用了先行控制技术。45.1先行控制技术5.1.1指令的重叠执行方式1、顺序执行方式执行n条指令所用的时间为：如每段时间都为t，则执行n条指令所用的时间为：T=3nt主要优点：控制简单，节省设备。主要缺点：执行指令的速度慢，功能部件的利用率低取指令k分析k执行k取指令k+1分析k+1执行k+152、一次重叠执行方式如果两个过程的时间相等，则执行n条指令的时间为：T=(1+2n)t一种最简单的流水线方式主要优点：指令的执行时间缩短功能部件的利用率明显提高主要缺点：需要增加一些硬件控制过程稍复杂取指k分析k执行k取指k+1分析k+1执行k+1取指k+2分析k+2执行k+263、二次重叠执行方式如果三过程的时间相等，执行n条指令的时间为：T=(2+n)t理想情况下同时有三条指令在执行处理机的结构要作比较大的改变，必须采用先行控制方式取指k+2分析k+2执行k+2取指k+1分析k+1执行k+1取指k分析k执行k71、采用二次重叠执行方式，必须解决两个问题(1)有独立的取指令部件、指令分析部件和指令执行部件一个集中的指令控制器，分解成三个相对独立的控制器：存储控制器、指令控制器、运算控制器(2)要解决访问主存储器的冲突问题取指令、分析指令、执行指令都可能要访问存储器5.1.2先行控制方式的原理和结构8(1)两个独立的存储器：独立的指令存储器和数据存储器。如果再规定，执行指令所需要的操作数和执行结果只写到通用寄存器，那么，取指令、分析指令和执行指令就可以同时进行。在许多高性能处理机中，有独立的指令Cache和数据Cache。这种结构被称为哈佛结构。(2)采用低位交叉存取方式：这种方法不能根本解决冲突问题。取指令、读操作数、写结果。(3)采用先行控制技术。先行控制技术的关键是缓冲技术和预处理技术。缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作。在采用了缓冲技术和预处理技术之后，运算器能够专心于数据的运算，从而大幅度提高程序的执行速度。2、解决访存冲突的方法95.1.2.1处理机结构在处理机内部设置一定容量的指令缓冲栈把指令分析器所需要的指令事先取到指令缓冲栈中，而不必访问主存储器使取指令、分析指令和执行指令重叠起来执行三个独立的控制器存储控制器指令控制器运算控制器四个缓冲栈先行指令缓冲栈先行读数缓冲栈先行操作栈后行写数栈10先行控制方式中的一次重叠执行指令分析器每次取指令能够在先行指令缓冲栈中得到，则取指令只需要很短的时间就能够完成可以把取指令与分析指令合并到一起构成一次重叠执行方式11先行指令缓冲栈的组成只要指令缓冲栈没有充满，就自动发出取指令的请求。设置两个程序计数器：先行程序计数器PC1，用来指示取指令，现行程序计数器PC，记录指令分析器正在分析的指令地址12存在的主要问题(1)各类指令“分析”和“执行”所需要的时间相差很大。(2)数据相关和变址相关。(3)转移或转子程序指令。135.1.2.2先行控制方式的指令执行时序设置了指令缓冲栈，取指令的时间就可以忽略不计。1、分析指令和执行指令时间不相等时的情况142、采用先行缓冲栈的指令执行过程先行读数栈，先行操作栈，后行写数栈。153、指令执行过程的时空图表示方法理想情况下，指令执行部件应该一直忙碌连续执行n条指令的时间为：165.1.2.3先行缓冲栈设置先行缓冲栈的目的：使指令分析器和指令执行部件独立工作。171、先行指令缓冲栈位置：主存储器与指令分析器之间。作用：用它来平滑主存储器取指令和指令分析器的工作。运算、移位、数据传送等指令都处理成RR型指令，送入先行操作栈。RR型指令，不必处理，直接送先行缓冲栈；RS和RX型指令，主存有效地址送先行读数栈，用该先行读数栈的寄存器编号替换指令中的主存地址码部分，形成RR*指令送先行缓冲栈；RI型指令，指令中的立即数送先行读数栈，用该先行读数栈的寄存器编号替换指令中的立即数部分，形成RR*指令送先行缓冲栈。无条件转移及条件转移指令，一般在指令分析器中直接执行。182、先行操作栈位置：指令分析器和运算控制器之间。作用：使指令分析器和运算器能够各自独立工作。采用先进先出方式工作，由指令寄存器堆和控制逻辑组成。193、先行读数栈位置：主存储器与运算器之间。作用：平滑运算器与主存储器的工作。每个缓冲寄存器由地址寄存器、操作数寄存器和标志三部分组成。也可以把地址寄存器和操作数寄存器合为一个。当收到从指令分析器中送来的有效地址时，就向主存申请读操作数。读出的操作数存放在操作数寄存器中或覆盖掉地址寄存器中的地址。204、后行写数栈每个后行缓冲寄存器由地址寄存器、数据寄存器和标志三个部分组成。指令分析器遇到向主存写结果的指令，把形成的有效地址送入后行写数栈的地址寄存器中，并用该地址寄存器的编号替换指令的目的地址部分，形成RR*指令送入先行操作栈。当运算器执行这条RR*型写数指令时，只要把写到主存的数据送到后行写数栈的数据寄存器中即可。215、在采用先行控制方式的处理机中，一个程序的执行情况指令地址指令执行情况......k-i-1已经执行完成的指令k-i......k-1在“后行写数栈”中等待把结果写到主存储器中的指令k正在“指令执行部件”中执行的指令k+1......k+j已经由“指令分析器”预处理完成，被存放在“先行操作栈”中的RR*型指令，指令所需要的操作数也已经读到“先行读数栈”中k+j+1......k+j+n指令已经由“指令分析器”预处理完成，存放在“先行操作栈”中，指令所需要的操作数还没有读到“先行读数栈”中k+j+n+1正在“指令分析器”中进行分析和预处理的指令k+j+n+2......k+j+n+m已经从主存储器中预取到“先行指令缓冲栈”中的指令k+j+n+m+1......还没有进入处理机的指令225.1.2.4缓冲深度的设计以采用静态分析方法为主，并通过系统模拟来确定缓冲深度。1、先行指令缓冲栈的设计考虑两种极端情况：(1)先行指令缓冲栈已经充满假设缓冲深度为DI,指令流出的速度最快，例如连续分析RR型指令，设这种指令序列的最大长度为L1，平均分析一条这种指令的时间为t1；指令流入的速度最慢，设平均取一条指令的时间为t2。从主存储器中取到先行指令缓冲栈中的指令条数是L1-DI条。应该满足如下关系：L1t1=(LI-DI)t2计算出缓冲深度为：如果这种指令流的连续长度超过L1，则先行指令缓冲栈将失去作用。23(2)先行指令缓冲栈原来空并假设它的缓冲深度为DI输入端指令流入的速度最快，每次取指令的时间最短；设这种指令序列的最大长度为L2，平均取一条这种指令的时间为t2’；输出端指令流出的速度最慢，指令分析器连续分析最难分析的指令；设平均分析一条指令的时间为t1’。指令分析器分析的指令条数是L2-DI条。应该满足如下关系：(L2-DI)t1’=LIt2’计算出缓冲深度为：如果这种指令流的连续长度超过L2，先行指令缓冲栈就失去了缓冲作用。242、设计举例在一般处理机中连续执行短指令的概率大，另外，还有“吸收型”指令。因此，一般用前一种方法来计算缓冲深度。例5.1：一个采用先行控制方式的处理机，指令分析器分析一条指令用一个周期，到主存储器中取一条指令装入先行指令缓冲栈平均要用4个周期。如果这种指令的平均长度L1=9，即90%的指令是执行时间短的指令。计算先行指令缓冲栈的缓冲深度为：253、先行指令缓冲栈的工作时间关系第1个周期，指令分析器取走指令k+1；向主存请求取指令。第4个周期末尾，指令k+8取到先行指令缓冲栈中。第8个周期末尾，指令k+9取到先行指令缓冲栈中。第9个周期，分析指令k+9，先行指令缓冲栈中没有任何指令。第10个周期，指令分析器没有指令可分析，只好等待。264、其余缓冲栈的设计原则各个缓冲栈的缓冲深度一般有如下关系：DI≥DC≥DR≥DW其中：DI是先行指令缓冲栈的缓冲深度，DC是先行操作栈的缓冲深度，DR是先行读数栈的缓冲深度，DW是后行写数栈的缓冲深度。例如：IBM370/165机，DI=4，DC=3，DR=2，DW=1。我国研制的两台大型计算机，其中一台，DI=8，DC=DR=4，DW=2。另外一台，DI=12，DC=DR=6，DW=2。275.1.3数据相关数据相关：在执行本条指令的过程中，如果用到的指令、操作数、变址量等正好是前面指令的执行结果，则必须等待前面的指令执行完成，并把结果写到主存或寄存器中之后，本条指令才能开始执行。这种相关称为数据相关。控制相关：由条件分支指令、转子程序指令、中断等引起的相关。数据相关有四种：指令相关、主存操作数相关、通用寄存器相关和变址相关解决数据相关的方法有两种：推后分析法和设置专用路径法。285.1.3.1指令相关发生指令相关的情况：n：STORER1,n+1n+1：……满足关系：结果地址(n)=指令地址(n+1)当第n条指令还没有把执行结果写到主存之前，取出的第n+1条指令显然是错误的。29造成的后果：在采用k个流水段的流水线处理机中，第n条指令要修改从第n+1到第n+k指令中的任意一条指令，都可能造成程序执行结果发生错误。在采用先行控制方式的处理机中，如果执行部件正在执行第n条指令，与下面的任意一条指令发生相关，都可能造成程序执行结果发生错误：已经存放在先行操作栈中的指令，正在指令分析器中进行预处理指令，已经预取到先行指令缓冲栈中的指令。更为严重的是：有一些“吸收型”指令，已经在指令分析器执行完成30解决指令相关的根本办法在程序设计中不允许修改指令。现代程序设计方法要求程序具有再入性，可以被递归调用等。在IBM370机中，用“执行指令”来解决指令相关“执行指令”本身并不执行，它执行的是由第二地址((X2)+(B2)+D2)决定的主存单元中的指令。这个主存单元一般不在指令区，而是在数据区315.1.3.2主存操作数相关发生主存操作数相关的指令序列：指令执行结果写到主存，所需要的操作数也来自主存。n：OPA1，A2，A3；A1=(A2)OP(A3)n+1：OPA1，A2，A3；A1=(A2)OP(A3)当出现下列两种情况之一时，就发生主存操作数相关：A1(n)=A2(n+1)A1(n)=A3(n+1)32解决办法运算结果写到通用寄存器，而不写到主存。对于访问主存储器的请求，写结果的优先级高于读操作数。335.1.3.3通用寄存器数据相关发生通用寄存器数据相关：发生的可能性最大，影响面也最大的一种数据相关。n：OPR1，A2；R1=(R1)OP(A2)n+1：OPR1，R2；R1=(R1)OP(R2)如果发生：R1(n)=R1(n+1)称为R1数据相关。如果发生：R1(n)=R2(n+1)称为R2数据相关。34解决通用寄存器数据相关的方法方法一：把读操作数、写运算结果与指令执行合在一个节拍。在数据从寄存器读出，在运算器中完成运算，结果写回寄存器的整个回路中，只有寄存器是时序逻辑。寄存器个数和操作部件个数不多时，是一种最常用的方法。存在问题：寄存器个数比较多时，读、写寄存器的时间长。当功能部件数量比较多时，寄存器堆的读写端口很多。必须使用多级多路选择器。35方法二：把执行与读操作数、写结果分在不同周期典型的方法是：读操作数放在指令分析周期，在执行周期之后，有一个写回结果周期。36结构上，必须在运算器的入口处增加两个锁存器。第k条指令的执行结果，如果写回寄存器堆，然后后再读出来，则第k+1条指令必须推后两个周期。37方法三增加相关专用通路增加相关专用通路之后，第k+1条指令的执行不必推后。实际上节省了两个时钟周期。由于通用寄存器数据相关出现的概率很高，因此增加一条相关专用通路是合适的。指令的执行结果在写回到通用寄存器的时候，同时也写入运算器入口处的锁存器中。在数据从锁存器读出，在运算器中完成运算，结果再写入锁存器的整个回路中，只有锁存器是时序逻辑。另外，在采用变址方式的处理机中，由于变址偏移量是放在寄存器中，因此，与通用寄存器的数据相关类似，有可能发生变址相关。385.1.3.4变址相关通用寄存器作变址寄存器使用，在指令分析时用来计算有效地址k：OPR1，R2 ;R1=(R1)OP(R2)k+1：OPR1，A2(X2) ;R1=(R1)OP((A2)+(X2))k+2：OPR1，A2(X2) ;R1=(R1)OP((A2)+(X2))如果发生：R1(k)=X2(k+1)称为一次变址相关如果发生：R1(k)=X2(k+2)称为二次变址相关变址相关专用通路39LOAD相关在RISC处理机中，只有LOAD操作能够访问存储器。LOAD操作的执行时间可能比较长。n：LOADR1，A ；R1=(A)n+1：ADDR2，R1 ；R2=(R1)OP(R2)如果R1(n)=R1(n+1)，则发生LOAD数据相关。解决方法：方法一：由编译器在LOAD之后插入不发生数据相关的指令由于LOAD操作的执行时间不能确定，依靠插入指令不能根本解决问题方法二：由硬件自动插入空操作，直到LOAD操作完成在只有一条流水线的处理机中，可以采用停止节拍发生器的方法，直到存储器的回答信号到来时，再启动节拍发生器。40各种数据相关的三种主要解决方法1采用硬件或软件的办法尽量避免数据相关发生。例如，为了避免通用寄存器数据相关，只要采用D型触发器构成通用寄存器堆，并且通用寄存器堆在一个节拍中能够读出两个操作数并写回一个结果2在确保指令正确执行的前提下，推后指令分析3设置相关专用通路来解决数据相关415.1.4控制相关指因为程序的执行方向可能被改变而引起的相关可能改变程序执行方向的指令通常有

无条件转移、一般条件转移、复合条件转移、子程序调用、中断等数据相关称为局部相关，影响到的仅仅是本条指令附近的少数几条指令控制相关称为全局相关，影响的范围要大得多，它可能引起程序执行方向的改变425.1.4.1无条件转移无条件转移指令在程序中一般如下：

k：……

k+1：JMPL

…：……

L：……在流水线处理机中，无条件转移指令不进入执行流水段，一般在指令译码(或称为指令分析)阶段就实际执行完成如果在处理机中设置有指令先行缓冲栈，无条件转移指令一般能够在指令分析阶段就执行完成，形成转移地址L同时送入先行程序计数器PC1和现行程序计数器PC中，指令缓冲栈按照PC1的指示重新开始向存储控制器申请取指令。43如果转移距离比较远指令L不在指令缓冲栈中，则要将指令缓冲栈中的所有指令全部作废指令分析器要等待一个“取指令L”周期之后才能开始“分析L”如果转移的距离比较近有可能指令L已经被取到了指令缓冲栈中只要作废指令缓冲栈中的部分指令，即作废从k+3到L-1之间的所有指令指令分析器在完成“分析k+1”之后，可以接着进行“分析L”，即指令分析器仍然可以不停顿地连续工作在指令缓冲栈的入口处增设一个专门处理无条件转移指令的指令分析器44在设置有先行操作栈的处理机中，无条件转移指令一般对指令执行部件的工作不会造成影响。为了进一步减少无条件转移指令造成的影响，在先行指令缓冲栈的入口处增设一个专门处理无条件转移指令的指令分析器。就不会再发生作废先行缓冲栈中指令的情况。455.1.4.2一般条件转移条件转移指令有两种:一般条件转移指令的转移条件来自上一条指令，或更前面的指令而复合型条件转移指令直接根据本条指令的执行结果决定是否转移k：…… ;置条件码CC

k+1：JMP(CC)L ;CC为真转向L，否则继续执行k+2

k+2：……

…：……

L：……46一般条件转移指令，相关最严重的情况发生在条件码是由上一条指令产生的:条件码要在“执行k”的末尾才能形成“分析k+1”在一开始就要根据这个条件码判断转移条件是否成立指令分析器分析到条件转移指令时，必须停下来等待所需要的条件码4748无论转移是否成功，条转移指令都在指令分析阶段就已经执行完成。如果转移不成功：指令分析器要停顿一段时间，等待条件码。如果转移成功：指令L已经在先行指令缓冲栈，指令分析器接着“分析L”指令L不在先行指令缓冲栈，指令分析器要等待一个周期。转移不成功，对程序执行影响不大。当转移成功时，不仅指令执行过程变成完全串行，而且要作废先行指令缓冲栈中的大量指令。因此，在采用流水线方式的处理机中，要通过软件与硬件的多种手段来近可能地降低转移成功的概率，减少转移成功造成的影响。495.1.4.3复合条件转移复合型条件转移指令本身就是一条运算指令，并且直接根据本条指令的运算结果决定是否转移。复合型条件转移指令的执行时间关系下：k：OPL;先执行OP操作，根据执行结果产生的条件码决定是否转向Lk+1：………：……L：……复合型条件转移指令不能在指令分析器中执行完成，它必须象其它运算型指令一样经指令执行部件执行无条件转移指令和一般条件转移指令能够在指令分析器中执行完成，称为吸收型指令50如果转移不成功：不造成任何影响，复合型条件转移指令就象一条普通的运算型指令一样。如果转移成功：造成的影响比一般条件转移指令还要大得多，全部作废或部分作废先行指令缓冲栈中已经预取的指令，作废先行操作栈中的指令和先行读数栈中的操作数，作废当前在指令分析器中分析的指令。因此，必须采取策略，减小转移成功造成的影响。515.1.4.4转移预测技术在程序执行过程中，转移预测的方向不能改变的称为静态分支预测。在程序执行过程中能够动态地改变转移预测方向的称为动态分支预测。521、软件“猜测法”转移不成功时，条件转移指令对流水线的影响比较小编译器在对源程序进行编译时，为了达到比较好的效果，要尽量降低转移成功出现的概率优点是不需要改变硬件结构，只要适当修改编译器就能够大幅度降低条件转移指令的影响主要目的：通过编译器尽量降低转移成功的概率。例如：对于普通的循环程序，一般编译器生成的目标代码，转移成功的概率很高，不成功的只有一次。这种编译结果对流水线的影响非常大。53542、硬件“猜测法”基本原理：通过改变硬件结构来降低转移指令对流水线造成的影响。实现方法：在先行指令缓冲栈的人口处设置一个简单的指令分析器，当这个指令分析器检测到转移指令时，就把转移目标地址L送入先行程序计数器PC1中，同时保留当前PC1中的内容到另一寄存器中。如果转移成功，则猜测正确。转移指令对流水线不造成影响。如果转移不成功，用保存下来的地址恢复PC1和PC中的内容，并重新开始取指令。软件和硬件要共同配合，软件与硬件都往同一个方向去猜测。553、两个指令缓冲栈原因：对于循环程序，软件“猜测法”或硬件“猜测法”都能获得很好效果对于普通条件转移指令(向前转移)；转移成功与不成功的概率很难预测。普通条件转移指令；如“IF”语句编译产生的条件转移指令,转移成功与不成功的概率一般各为50%方法：增加一个指令目标缓冲栈当指令分析器分析到条件转移指令时，按照转移成功的方向预取指令到这个指令目标缓冲栈中原来的指令缓冲栈仍然按照转移不成功的方向继续预取指令转移不成功，则继续分析原来指令缓冲栈中指令转移成功，则分析新增设的指令目标缓冲栈中的指令56IBM370/165机就采用了两个先行指令缓冲栈。先行目标缓冲栈AIB的缓冲深度为4。为了简化对两套先行指令缓冲栈的控制，在转移成功时，交换先行目标缓冲栈AIB和原来的先行指令缓冲栈IB中内容，使指令分析器仍然从原来的指令缓冲栈IB中的取指令。575.1.4.5短循环程序的处理开门、关门指令硬件识别585.2流水线处理机空间并行性设置多个独立的操作部件多操作部件处理机超标量处理机时间并行性采用流水线技术。不增加或只增加少量硬件就能使运算速度提高几倍流水线处理机超流水线处理机595.2.1流水线工作原理5.2.1.1从重叠到流水线流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等。会增加指令的执行时间。为了简化，在一般流水线中不画出流水锁存器。分析器分析k+1流水

锁存器执行部件执行k流水

锁存器输入输出Dt1Dt2602、一种指令流水线一般4至12个流水段，等于及大于8个流水段的称为超流水线处理机流水线的连接图表示方法表示流水线的逻辑关系流水线的时空图表示方法表示流水线的时间关系流水线的预约表表示方法将在非线性流水线中介绍取指形成操

作数地址译码取操作数执行保存结果61?IntelP4CPU是否流水线处理机IntelP4CPU使用几级流水线625.2.1.2时空图一条简单流水线的时空图：分析k分析k+1分析k+2分析k+3执行k执行k+1执行k+2执行k+3时间空间0t1t2t3t4t563一个浮点加法器流水线的时空图(由求阶差、对阶、尾数加和规格化4个流水段组成)：ED1时间空间0t1t2t3t4t5ED2ED3ED4ED5EA1EA2EA3EA4EA5MA1MA2MA3MA4MA5NL1NL2NL3NL4NL5t6t7t8NL：规格化MA：尾数加EA：对阶ED：求阶差645.2.1.3流水线的特点1、在流水线中处理的必须是连续任务只有连续不断地提供任务才能充分发挥流水线的效率在采用流水线方式工作的处理机中，特别是当流水线的级数较多时，要在软件和硬件设计等多方面尽量为流水线提供连续的任务，以提高流水线的效率2、把一个任务(一条指令或一个操作)分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现流水线实际上是把一个大的功能部件分解为多个独立的功能部件，并依靠多个功能部件并行工作来缩短程序的执行时间653、在流水线的每一个功能部件的后面要要设置一个缓冲寄存器，或称为锁存器、闸门寄存器等，用于保存本段的执行结果。这是因为流水线中每一段的延迟时间一般不可能都相等在段与段之间传送子任务时，必须通过缓冲寄存器。当某一个流水段的执行时间变化范围比较大时，要设置多个缓冲寄存器664、流水线中各段的时间应尽量相等否则将引起“堵塞”、“断流”等。执行时间长的一段将成为整个流水线的“瓶颈”，这时，流水线中的各个功能部件将不能充分发挥作用。因此，在流水线设计中，当遇到“瓶颈”时，必须采取办法解决一种办法是把“瓶颈”流水段再细分，另一种办法是重复设置瓶颈功能段。具体内容在性能分析一节介绍5、流水线需要有“装入时间”和“排空时间”只有流水线完全充满时，整个流水线的效率才能得到充分发挥在流水线处理机的设计过程中，要充分注意上述问题，以设计出高效率的流水线。在流水线处理机上设计程序时，也必须注意流水线的上述特点，以充分发挥流水线处理机的高效率。675.2.2流水线的分类5.2.2.1线性流水线与非线性流水线流水线的各个流水段之间是否有反馈信号线性流水线(LinearPipelining)

每个流水段都流过一次，且仅流过一次非线性流水线(NonlinearPipelining)

在流水线的某些流水段之间有反馈回路或前馈回路线性流水线能够用流水线连接图唯一表示

非线性流水线必须用流水线连接图流水线预约表等共同表示S1输入S2S3输出前馈回路反馈回路一种简单的非线性流水线685.2.2.2流水线的级别处理机级流水线,又称为指令流水线(InstructionPipelining)例如：在采用先行控制器的处理机中，各功能部件之间的流水线先行指令

缓冲栈输入先行控制方式

中的指令流水线先行指令

分析器先行读数栈

先行操作栈取指译码取操作数指令执行部件后行写数栈输出执行写结果69部件级流水线(操作流水线)，如浮点加法器流水线处理机之间的流水线称为宏流水线(MacroPipelining)

每个处理机对同一个数据流的不同部分分别进行处理求阶差输入输出Dt1对阶尾数加规格化Dt2Dt3Dt4P1输入任务1MM…P2任务2MP3任务3输出705.2.2.3单功能流水线与多功能流水线单功能流水线：只能完成一种固定功能的流水线Cray-1计算机中有12条；YH-1计算机有18条；Pentium有一条5段的定点和一条8段的浮点流水线；PentiumIII有三条指令流水线，其中两条定点指令流水线，一条浮点指令流水线。多功能流水线：流水线的各段通过不同连接实现不同功能Texas公司的ASC计算机中的8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。71725.2.2.4静态流水线与动态流水线静态流水线：同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能。只有连续出现同一种运算时，流水线的效率才能得到充分的发挥。动态流水线：在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。731时间空间023…n123…n123…n123…n123…n123…n1234…123…12……1输入求阶差对阶尾数加规格化尾数乘累加输出静态流水线时空图浮点加法定点乘法741时间空间023…n123…n123…n123…n123…n123…n输入求阶差对阶尾数加规格化尾数乘累加输出动态流水线时空图………………123546123541234123…………浮点加法定点乘法75流水线的其他分类方法按照数据表示方式：标量流水线和向量流水线按照控制方式：同步流水线和异步流水线顺序流水线与乱序流水线：乱序流水线又称为无序流水线、错序流水线或异步流水线等S1就绪回答S2就绪回答S3就绪回答输出就绪回答输入765.2.3线性流水线的性能分析衡量流水线性能的主要指标有：吞吐率、加速比和效率5.2.3.1吞吐率(ThoughPut)求流水线吞吐率的最基本公式：TP=n/Tkn为任务数,Tk为完成n个任务所用时间各段执行时间相等，输入连续任务情况下完成n个连续任务需要的总时间为：Tk=(k+n-1)Dtk为流水线的段数Dt为时钟周期771时间空间S123……n-1nS2S3S4123……n-1n123……n-1n123……n-1nkDt(n-1)DtnDt(k-1)DtT78吞吐率：最大吞吐率为：各段执行时间不相等、输入连续任务情况下：吞吐率为：最大吞吐率为：79流水线各段执行时间不相等的解决办法S1输入Dt1=DtS2Dt2=3DtS3Dt3=DtS4Dt4=Dt输出1时间空间S1S2S3S4SDti(n-1)Dt2Tk23…n123…n123…n123…n80一是将“瓶颈”流水段细分(如果可分的话)：二是将“瓶颈”流水段重复设置：p420级、31级1，2Pentium系统结构的核心是超标量流水线。U,V两条指令流水线，有各自的ALU、地址生成电路、与数据Cache的接口RISC2，4，8，16个整数运算器2??HyperThreading超线程技术S1输入输出DtS2-1DtS2-2DtS2-3DtS3DtS4DtS2(3Dt)S1输入输出Dt1=DtS2-1S2-1S2-1S3S4Dt3=DtDt4=DtDt2=3Dt81流水段重复设置的流水线1时间空间23nS1S2-1456…14…-2-1n-225…n-136…n123n456…-2-1123n456…-2-1S2-2S2-3S3S4825.2.3.2、加速比(Speedup)计算流水线加速比的基本公式：S=顺序执行时间T0/流水线执行时间Tk各段执行时间相等，输入连续任务情况下加速比为：

最大加速比为：

各段执行时间不等，输入连续任务情况下实际加速比为：83K=6K=10任务

个数加速比10246811248163264128845.2.3.3效率(Efficiency)计算流水线效率的一般公式：

各流水段执行时间相等，输入n个连续任务

流水线的效率为：

流水线的最高效率为：85各流水段执行时间不等，输入n个连续任务流水线的效率为：流水线各段的设备量或各段的价格不相等时,流水线的效率为：

即：

其中，ai<k，且86流水线的吞吐率、加速比与效率的关系因为因此：E=TP·Dt，S=k·E875.2.3.4流水线最佳段数的选择从上面的分析中可以清楚地看到，增加流水线的段数，流水线的吞吐率和加速比都能提高用于在每一个流水段的输出端都必须设置一个锁存器(或称缓冲寄存器、闸门寄存器等)当流水线的段数增多时，锁存器的总的延迟时间也将增加，甚至有可能出现锁存器的总延迟时间超过流水线本身的延迟时间。增加锁存器数量，必然要增加流水线的价格要综合各方面的因素，应该根据最佳性能价格比的要求来选择流水线的最佳段数88

如果流水线段数过多，时钟周期很小，以至于与时钟偏移和锁存器的附加开销相当，会导致在一个时钟周期内没有足够时间用于有效工作，流水线也就失去了作用。

假设在非流水线的机器上采用顺序执行方式完成一个任务所需要的时间为t，那么，在同等速度的有k段流水线的机器上执行一个任务需要的时间为：其中d为锁存器的延迟时间。这样，流水线的最大吞吐率可以表示为：89流水线的总价格粗略地估计为：C=a+bk，其中，a为所有流水段本身的总价格，b为每个锁存器的价格。A.G.Larson把流水线的性能价格比PCR定义为： (5.41)可以通过对自变量k求导，得到性能价格比PCR的极值。由于大于零的极值只有一个，因此，这个极值就是最大值。如图所示，当性能价格比PCR取得最大值时，它所对应的流水线的段数就时最佳段数k0：

(5.42)式中的t为流水线的总的延迟时间。

从(5.42)关系式中可以很清楚地看到，流水线的最佳段数与流水线的延迟时间t和流水线本身的价格a的平方根成正比，而与锁存器的延迟时间d和锁存器的价格b的平方根成反比。90流水线的最佳段数

在设计一条流水线的时候，可以根据(5.42)关系式，在流水线的总延迟时间t一定的情况下，可以通过调整流水线本身的价格a，锁存器的延迟时间d和锁存器的价格b来选取最佳的流水线段数k0。

目前，一般处理机中的流水线段数在2段至10段之间，极少有超过15段的流水线。一般把8段或超过8段的流水线称为超流水线，采用8段以上流水线的处理机称为超流水线处理机。915.2.3.5、流水线性能分析举例对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。例5.1：用一条4段浮点加法器流水线求8个浮点数的和：

Z=A+B+C+D+E+F+G+H92解：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]1时间空间23求阶差4567123456712345671234567对阶尾数加规格化加数ACEGA+BE+FBDFHC+DG+HA+B+C+DE+F+G+H结果A+BC+DE+FG+HA+B+C+DE+F+G+H937个浮点加法共用了15个时钟周期。

流水线的吞吐率为：

流水线的加速比为：

流水线的效率为：945.2.4非线性流水线的调度技术非线性流水线调度的任务找出一个最小的循环周期按照这周期向流水线输入新任务流水线的各个功能段都不会发生冲突流水线的吞吐率和效率最高955.2.4.1非线性流水线的表示线性流水线能够用流水线连接图唯一表示96流水线连接图不能唯一表示非线性流水线的工作流程引入流水线预约表97一张预约表可能与多个流水线连接图相对应与上面的预约表对应的另一种非线性流水线的连接图98一个连接图对应有多张预约表与前一个连接图对应的另一张预约表995.2.4.2非线性流水线的冲突流水线的启动距离：向流水线连续输入两个任务之间的时间间隔流水线的冲突：几个任务争用同一个流水段1001011025.2.4.3无冲突调度方法相关理论由E.S.Davidson及其学生们于1971年提出非线性流水线的禁止向量预约表中每一行任意两个“×”之间的距离都计算出来，去掉重复的例如，上图所示的预约表的禁止向量为(3，4，6)由禁止向量得到冲突向量C=(CmCm-1…C2C1)其中：m是禁止向量中的最大值如果i在禁止向量中，则Ci=1，否则Ci=0例如：对于上面的预约表，C=(101100)由冲突向量构造状态图：把冲突向量送入一个m位逻辑右移移位器，当移位器移出0时，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；否则不作任何处理；如此重复m次对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，当新形成的冲突向量出现重复时可以合并到一起103例一条有4个功能段的非线性流水线，每个功能段的延迟时间都相等1写出流水线的禁止向量和初始冲突向量2画出调度流水线的状态图3求流水线的最小启动循环和最小平均启动距离4求平均启动距离最小的恒定循环104解1.禁止向量为：(2，4，6)初始冲突向量：101010(0)2.初始冲突向量逻辑右移2、4、6位时，不作任何处理逻辑右移1、3、5和大于等于7时，要进行处理初始冲突向量右移1位之后：010101∨101010=111111(0)--1-->(1)初始冲突向量右移3位之后：000101∨101010=101111(0)--3-->(2)初始冲突向量右移5位之后：000001∨101010=101011(0)--5-->(3)初始冲突向量右移7位或大于7位后：还原到它本身。(0)--7-->(0)中间冲突向量101111右移5位之后：000001∨101010=101011(2)--5-->(3)中间冲突向量101011右移3位之后：000101∨101010=101111(3)--3-->(2)中间冲突向量101011右移5位之后：000001∨101010=101011(3)--5-->(3)105预约表与状态图是唯一对应，但不同的预约表也可能有相同的状态图1063.简单循环：状态图中各种冲突向量只经过一次的启动循环简单循环的个数一般是有限的由简单循环可以计算出平均启动距离107最小的启动循环为(1，7)或(3，5)其平均启动距离为4平均启动距离最小的恒定循环为(5)。1081091105.2.4.4优化调度方法L.E.Shar于1972年提出了流水线最小平均启动距离的限制范围1下限是预约表中任意一行里“×”的最多个数2小于或等于状态图中任意一个简单循环的平均启动距离3最小平均启动距离的上限是冲突向量中1的个数再加上11992年，L.E.Shar证明了上述限制范围最有用的是第1条。预约表中“×”最多的行一定是瓶颈流水段采用预留算法来调度非线性流水线，可以实现最优调度第1步：确定最小平均启动距离，为预约表中任意一行中“×”的最多个数。第2步：确定最小启动循环，以恒定循环作为最小启动循环。第3步：采用预留算法，插入非计算延迟段实现最小启动循环111对于上一节的例子：S1、S2、S3对应的行有2个“×”，因此，最小平均启动距离为2。以恒定循环(2)作为最小启动循环。检查每一行中与第1个“×”的距离为2的倍数的位置都要预留出来。S3行的第2个“×”从周期5延迟到周期6。为此，S2行的第2个“×”也要向后延迟一个周期，从周期6延迟到周期7S1行的第2个“×”也要向后延迟一个周期，从周期7延迟到周期8。实际上，只要在S4的输出端到S3的输入端中间插入一个非计算延迟D1，如下表和下图所示112113在非线性流水线中，“×”最多的流水段一定是“瓶颈“流水段。实现最优调度的目标是使“瓶颈”流水段处于忙碌状态，没有空闲的周期最优调度方法能够使非线性流水线的吞吐率、加速比和效率达到最优。1145.2.5局部相关(动态调度技术)由硬件动态调整指令执行顺序以减少数据相关的影响。能够处理在编译阶段无法确定的相关关系，并简化编译器设计；在别的流水线机器上编译的代码也能够高效运行。采用静态调度方法生成的代码也能在采用动态调度法的机器中运行。5.2.5.1顺序流动与乱序流动5.2.5.2乱序流动方式中的数据相关5.2.5.3数据重定向方法5.2.5.4Tomasulo动态调度算法115顺序流动方式，流水线的控制逻辑比较简单

在程序中有“先写后读”数据相关时，流水线可能会“断流”，这将降低流水线的吞吐率和效率乱序流动方式中，除了有“先写后读”数据相关之外，还可能发生“先读后写”数据相关和“写-写”数据相关。“先写后读”数据相关又称为数据相关、写读相关、流相关、WR相关、RAW相关“先读后写”相关又称为变量名相关、读写相关、反相关、RW相关、WAR相关“写-写”数据相关又称为输出相关、WW相关、WAW相关或写后再写相关1165.2.5.1顺序流动与乱序流动顺序流动方式：任务按顺序流入流水线，也按顺序流出流水线把如下一段程序输入到这条流水线中：117其中，指令k与指令k+2之间有数据相关。指令k+2无法继续执行，要在功能段S2中等待。后续的指令k+4、k+5、……等也不能进入流水线。功能段S3、S4、S5将逐渐空闲。缺点：流水线“断流”，有些功能段“空闲”，吞吐率和效率降低。优点：流水线的控制逻辑比较简单。118乱序流动方式：指令流出流水线的顺序与指令原先的顺序不同乱序(Outoforder)流动方式，错序流动方式、无序流动方式、异步流动方式等。造成流水线乱序流动方式的原因不仅仅是“先写后读”数据相关，有些指令执行的时间短或经过的流水段比较少，它们要越过执行时间长或经过流水段多的指令向前流动把指令k+2保存在功能段S2中，而让后续的指令k+3、k+4、k+5进入功能段S2执行，并超越指令k+2进入以后的功能段。从流水线的输出端看，指令流出流水线的顺序与进入流水线的顺序不一样1195.2.5.2乱序流动方式中的数据相关在乱序流动方式中，还有另外两种不同的相关。例如，把下面一小段程序中输入到采用乱序流动方式的流水线中，可能发生三种不同的数据相关。其中，F1、F2和F3是三个浮点寄存器，A和B是两个内存单元。(1)在指令k的F1与指令k+1的F1之间的相关关系称为：数据相关、先写后读相关、写读相关、流相关、WR相关、RAW相关或读后写相关等，我们把它称为写读相关。(2)在指令k+1的F1与指令k+2的左边那个F1之间的相关关系称为：变量名相关、先读后写相关、读写相关、反相关、RW相关、WAR相关或写后读相关等，我们把它称为读写相关。(3)在指令k的F1与指令k+2的左边那个F1之间的相关关系称为：输出相关、写写相关、WW相关、WAW相关或写后再写相关等，我们把它称为写写相关。另外还有：在指令k+2的F1与指令k+3的F1之间之间有写读相关，在指令k+1左边的F2与右边的F1之间有读写相关。120121有些书中把相关称为“冒险”(hazard)、“竟争”(competition)等。

三种数据相关可以用下列关系式来表示：对于写读相关D(i)∩S(j)≠对于读写相关S(i)∩D(j)≠对于写写相关D(i)∩D(j)≠这只是发生相关的必要条件，而不是充分条件；在执行程序过程，只有避免数据相关，程序执行结果才是正确的。通过建立专用路径来避免数据相关的基本原理是数据重定向。首先介绍常用的数据重定向的一般原理和基本方法在此基础上，再介绍一种经典的避免数据相关的Tomasulo算法。1225.2.5.3数据重定向方法1、三种数据相关的重定向方法重定向之前，j只能在i之后执行。重定向之后，分为三种情况：(1)对于写读相关，j与i可以同时执行，就是专用数据通路法。(2)对于写写相关，j与i无先后时间顺序要求。(3)对于读写相关，j与i无先后时间顺序要求。1231242、读写数据相关和写写数据相关的重定向在编译器中称为变量换名技术，只要符合：任何变量只允许定义一次的规则，读写数据相关和写写数据相关就自动消除了。在三种数据相关中，实际上只有写读数据必须依靠硬件来解决：采用推后处理或增加专用数据通路。在上面的数据重定向图中，把B换成了B’，读写数据相关和写写数据相关就不存在了。125一个依靠编译器进行数据重定向的例子1263、一个采用数据重定向的实际例子k：LOADF1,Ak+1：FADDF1,F2k+2：FMULF1,F3k+3：STOREF1,B专门设置A→FADD、FADD→FMUL、FMUL→B三条专用路径，撤消F1→FADD和F1→FMUL的路径，A→F1、FADD→F1的传送路径。1271285.2.5.4Tomasulo动态调度算法在机器中实际使用的动态调度算法主要有两种Tomasulo算法最早在大型机IBM360/91处理机的浮点处理部件中被采用

又称为公共数据总线(CDB：CommonDataBus)法，或令牌法等

分散控制的方法CDC计分牌(scorebord)算法，最先在CDC6600大型机中采用

集中控制方法。1295.2.5.4Tomasulo动态调度算法以上面的一小段程序为例

如果在串行执行的处理机中，必须等待上一条指令执行完后，下一条指令才能开始执行。

由于浮点加法器和浮点乘法器可以同时工作，如果采用乱序流动方式，在上面的这四条指令中可能发生“先写后读”和“写-写”两种数据相关。

指令k的执行结果，把一个浮点操作数从主存储器中读出，送入浮点先行读数站的(FLB1)中，并在执行指令k+1时通过(FLB1)直接送入到浮点加法器的保存站A1，而不是送到浮点通用寄存器F1中，这就相当于建立了一条从主存储器到浮点加法器的专用数据路径。

在执行指令k+1时，把浮点通用寄存器(F2)中的内容通过FLR总线送入浮点加法器的保存站A1中，同时把浮点先行读数站(FLB1)中的操作数通过另一条FLB总线也送入浮点加法器的保存站A1中，并启动浮点加法器开始工作。因为浮点加法器的运算结果要送入F1，因此，要把浮点加法器保存站A1的站号“10”装入浮点通用寄存器F1的站号中；另外，要把F1的“忙位”标志置“1”，表示浮点通用寄存器F1中的内容目前不能读出作为源操作数来使用。130

由于浮点加法器要执行两个时钟周期才能出结果，当执行指令k+2时，虽然可以把浮点通用寄存器(F3)中的内容通过FLR总线送入浮点乘/除法器的保存站M1中；但是，执行浮点乘法所需要的另一个操作数还不能从浮点通用寄存器F1中读出；这时，改为把保存在浮点通用寄存器F1中的站号“10”(浮点加法器保存站A1的站号)读出来，并通过控制总线送入到浮点乘/除法器的保存站M1中，并把F1内的站号改为浮点乘/除法器保存站M1的站号“8”，表示F1改从浮点乘/除法器接收运算结果。

在浮点加法执行完成之后，把运算结果和保存站A1的站号“10”都送上公共数据总线CDB。通过与所有站号中保存的内容进行相等比较，找到浮点乘/除法器的保存站M1；于是，把CDB上的数据送入M1，而不是送入浮点通用寄存器F1；这相当与建立了一条从浮点加法器到浮点乘/除法器的专用数据路径。

浮点乘/除法器收到CDB上的数据之后就可以开始工作。在6个时钟周期之后，浮点乘法的执行结果连同保存站M1的站号都送上CDB。通过与所有站号进行相等比较，把CDB上的数据送入到浮点通用寄存器F1中。

在浮点乘/除法器刚刚开始工作时，指令k+3开始执行。由于浮点乘法的最终运算结果还没有出来，因此，就把保存站M1的站号“8”装入后行写数站的站号中。当浮点乘法操作执行结束之后，在把运算结果通过CDB送入浮点通用寄存器F1的同时，也送入浮点后行写数站SDB，由SDB负责把这个结果写到主存储器的B单元中。1311325.2.6全局相关(相关性分析技术)5.2.6.1条件分支对流水线的影响5.2.6.2动态分支预测技术5.2.6.3提前形成条件码5.2.6.4精确断点与不精确断点1335.2.6.1条件分支对流水线的影响由条件分支或程序中断引起的相关被称为全局相关。全局相关对流水线的吞吐率和效率的影响相对于数据相关要大得多；处理好条件转移和中断的关键问题有两个：一是要确保流水线能够正常工作，二是减少因“断流”引起的吞吐率和效率的下降。1341、条件分支的处理方法在一般程序中，条件转移指令占五分之一左右。条件转移指令对流水线的影响很大，必须采取措施来减少这种影响。可能采取的措施有如下几种：(1)延迟转移技术和指令取消技术只能用于单流水线标量处理机中，而且流水线的级数不能太多；据统计，编译器调度一条指令成功的概率在90%以上，而调度两条指令成功的概率只有40%左右。当没有合适的指令可调度时，编译器只能插入空操作。SUN公司的SPARC处理机，SGI公司的一部分MIPS处理机采用了延迟转移技术。在HPPA处理机种采用了指令取消技术。135(2)静态分支预测技术，转移预测的方向是确定，或者预测转移不成功，或者预测转移成功，在程序实际执行过程中，转移预测的方向不能改变。静态转移预测可以只用软件实现，也可用硬件来实现，还可以在转移的两个方向上都预取指令。TI公司的SuperSPARC处理机采用了静态转移预测技术，而且设置有转移目标缓冲栈，在两个方向上都预取指令。(3)动态分支预测技术，根据近期转移是否成功的历史记录来预测下一次转移的方向。所有的动态转移预测方法都能够随程序的执行过程动态地改变转移的预测方向。1362、条件分支在流水线中的执行过程因为第i条指令所需要的条件码由第i-1条指令给出；在一条由k个功能段的流水线中，第i-1条指令要等到第i+k-2条指令进入流水线时才能形成条件码。137如果转移不成功的，则猜测正确，流水线的吞吐率和效率没有降低，如果转移成功的，则猜测错误，要先作废流水线中已经执行的第i+1、i+2、……、i+k-2条指令；然后，再从分支点开始执行第P、p+1、……条指令。一条k段流水线有k-2个功能段是浪费的。当分支方向猜测错误时，可能造成程序执行结果发生错误例如，若第i+1条指令是：(R1)+(R2)→R1寄存器R1中内容就被破坏，整个程序执行的结果也将是错误的。目前的处理机有两种做法：一种方法是只进行指令译码和准备好运算所需要的操作数，在转移条件没有形成之前不执行运算；另一种方法是一直执行到运算完成，但不送回运算结果1383、条件分支对流水线性能的影响假设条件转移指令在一般程序中所占的比例为p，转移成功的概率为qn条指令的总的执行时间是：TK-IF=(n+k-1)t+npq(k-1)t有条件转移影响的流水线吞吐率为：有条件转移影响的流水线最大吞吐率为：TPMAX-IF=流水线吞吐率下降的百分比为：D=1393、条件分支对流水线性能的影响在典型程序中，转移指令占的比例为p=20%，转移成功的概率为q=60%。对于一条有8个功能段的指令流水线，由于条件转移指令的影响，流水线的最大吞吐率要下降：D8==46%如果指令流水线的功能段数为10，由于条件转移指令的影响，流水线的最大吞吐率将下降到原来的一半以下：

D10==52%条件分支使流水线的吞吐率大约下降50%。1405.2.6.2动态分支预测技术动态转移预测技术的两个问题关键问题：一是记录转移历史信息，二个是根据所记录的转移历史信息预测转移的方向。记录转移历史信息的方法有三种：第一种是把最近一次或几次转移是否成功的信息记录在转移指令中，第二种是用一个小容量的高速缓冲栈保存条件转移指令的转移目标地址，第三种是用Cache保存转移目标地址之后的n条指令。根据三种不同的记录转移历史信息的方法，有三类动态转移预测技术。1411、在指令Cache中记录转移历史信息在指令Cache中专门设置一个字段，称为“转移历史表”。在执行转移指令时，把转移成功或不成功的信息记录在这个表中。当下次再执行到这条指令时，转移预测逻辑根据“转移历史表”中记录的信息预测转移成功或不成功。每一条指令一位的“转移历史表”，只记录最近一次转移是否成功的历史信息。142在执行条件转移指令时，如果“转移历史表”中记录的内容是“T”，则转移预测逻辑预测转移成功，并按照转移成功的方向取指令；如果记录的是“N”，则按照转移不成功的方向继续取下一条指令。用本条转移指令实际转移是否成功的信息来修改“转移历史表”。143记录最近两次转移是否成功的历史信息修改“转移历史表”的规则是采用了一种向左移位的方法转移预测偏向于转移成功的，只有历史上最近两次执行这条转移指令时转移都没有成功，本次才预测转移不成功，对于另外三种情况都预测转移成功。144“转移历史表”的修改规则和转移预测规则可以有多种多样，也可以记录转移预测是否成功的信息。预测本次转移方向时，也可以用最近预测是否成功的信息作为依据当“转移历史表”是空白时，可以有两种做法：一种是在“转移历史表”中预置转移历史信息。另一种是根据指令本身的偏移字段的符号来预测转移的方向；如果偏移字段的符号是负的，则预测转移成功，否则预测转移不成功主要优点：不必专门设置转移缓冲栈，所记录的转移历史信息比较少。DEC公司的Alpha21064超标量超流水线处理机就采用了这种转移预测方法，在它的一级指令Cache中有一个专门的“转移历史表”字段。1452、设置转移目标地址缓冲栈用高速缓冲栈保存最近k条转移指令的“转移历史表”和转移目标地址“转移指令地址”字段采用全相联方式访问。把当前指令地址与转移目标缓冲栈中的所有转移指令地址进行比较；如果发现有相等的，则根据同一行中的“转移历史表”所记录的历史信息预测本次转移的方向。并根据某一种规则修改“转移历史表”。1463、设置转移目标指令缓冲栈把上面方法中的转移目标地址改为存放转移目标地址之后的n条指令。预测转移方向的规则和修改“转移历史表”的规则与上面的方法相同1475.2.6.3提前形成条件码必要性：尽早产生条件码对减少流水线吞吐率和效率的损失非常有效。可能性：对于大多数情况，可以在运算实际开始之前或者在运算中间产生条件码。例如：乘法和除法，两个源操作数符号相同结果为正，相反结果为负；有一个操作数为“0”，则乘积为“0”；被除数为“0”，则商为“0”；除数为“0”，则除法结果溢出。例如：加法和减法，同号相加，异号相减，结果的符号与第一操作数相同；异号相加，同号相减，结果的符号与绝对值大的操作数相同；溢出、是否为“0”可以通过一个比较器提前产生。在绝大多数情况下，只要在运算部件的入口处设置一个比较器，就能够提前形成结果的正负号、是否为“0”、是否溢出等条件码。如果能够在一个时钟之前内就产生条件码，流水线就不会“断流”。Amdahl470V/6在运算部件的入口处设置一个LOCK部件来预判条件码。1481495.2.6.4精确断点与不精确断点对于输入输出设备申请的中断服务，实际上不需要有精确断点。比较简单的处理方法是：让已经进入流水线的所有指令都执行完成，断点就是最后进入流水线的那条指令的地址。

对于程序性错误和机器故障等引起的中断，它们出现的概率很低，处理原则：不在于缩短时间，关键是要正确保存现场和正确恢复断点。不精确断点(Impreciseinterrupt)方法，精确断点(Preciseinterrupt)方法。150采用不精确断点法，流水线可以不“断流”；所需要的硬件比较少，控制逻辑相对比较简单；中断响应时间稍长，要增加一条流水线的时间长度。151采用不精确断点法可能会发生如下两个问题：(1)问题是程序执行的结果可能出错；例如，有如下两条指令：i：FADDR1,R2；(R1)+(R2)→R1i+1：FMULR3,R1；(R3)×(R1)→R3当第i条指令执行到S6段时发现浮点加法结果溢出，于是发出中断服务申请。由于采用不精确断点法，要让已经进入流水线的第i+1条指令也执行完成；因为第i+1条指令使用了不正确的通用寄存器R1中的内容作源操作数，因此，浮点乘法的执行结果一般也是不正确的152(2)程序的调试困难.早期生产的一批大型流水线处理机中，有许多采用了不精确断点法；近期生产的流水线处理机一般都采用精确断点法。采用精确断点法，要设置一定数量的后援寄存器，把整个流水线中所有指令的执行结果和现场都保存下来。1535.3超标量处理机与超流水线处理机超标量处理机：

Intel公司的i860,i960,Pentium处理机

Motolora公司的MC88110

IBM公司的Power6000

SUN公司的SuperSPARC等。超流水线处理机：

SGI公司的MIPSR4000,R5000,R10000等。超标量超流水线处理机：

DEC公司的Alpha等。154k段流水

线基准标

量处理机m度

超标量n度超

流水线(m,n)度

超标量

超流水机器类型机器流水

线周期同时发射

指令条数指令发射

等待时间指令级并

行度ILP1个时

钟周期1条1个时

钟周期11m1m1/n11/nn1/nm1/nm´n超标量、超流水、超标量超流水处理机的主要性能1555.3.1超标量处理机一般流水线处理机：

一条指令流水线，

一个多功能操作部件，每个时钟周期平均执行指令的条数小于1。多操作部件处理机：

一条指令流水线，

多个独立的操作部件，操作部件可以采用流水线，也可以不流水。多操作部件处理机的指令级并行度小于1。超标量处理机典型结构：

多条指令流水线

先进的超标量处理机有：定点处理部件CPU，浮点处理部件FPU,图形加速部件GPU

大量的通用寄存器，两个一级高速Cache

超标量处理机的指令级并行度大于11565.3.1.1基本结构Motorola公司的MC88110：

10个操作部件两个寄存器堆

整数部件通用寄存器堆，32个32位寄存器；

浮点部件扩展寄存器堆，32个80位寄存器。

每个寄存器堆有8个端口，分别与8条内部总线相连接，有一个缓冲深度为4的先行读数栈和一个缓冲深度为3的后行写数栈。两个独立的高速Cache中，各为8KB，采用两路组相联方式。转移目标指令Cache，在有两路分支时，存放其中一路分支上的指令157整数

部件整数

部件位

操作浮点加乘法

部件除法

部件图形

部件图形

部件内部总线读数/存

数部件通用寄

存器堆扩展寄

存器堆目标

指令指令分配

转移部件数据Cache(8KB)指令Cache(8KB)系统总线32位地址总线64位数据总线超标量处理机MC88110的结构1585.3.1.2单发射与多发射单发射处理机：每个周期只取一条指令、只译码一条指令，只执行一条指令，只写回一个运算结果取指部件和译码部件各设置一套可以只设置一个多功能操作部件，也可以设置多个独立的操作部件操作部件中可以采用流水线结构，也可以不采用流水线结构设计目标是每个时钟周期平均执行一条指令，ILP的期望值1159IF时钟

周期指令I1I2I3IDEXWRIFIDEXWRIFIDEXWR123456单发射处理机的指令流水线时空图160161多发射处理机每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时写回多个运算结果需要多个取指令部件，多个指令译码部件和多个写结果部件设置多个指令执行部件，复杂的指令执行部件一般采用流水线结构设计目标是每个时钟周期平均执行多条指令，ILP的期望值大于1162多发射处理机的指令流水线时空图IF时钟

周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR163164超标量处理机：

一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机

必须有两条或两条以上能够同时工作的指令流水线先行指令窗口：

能够从指令Cache中预取多条指令

能够对窗口内的指令进行数据相关性分析和功能部件冲突的检测

窗口的大小：一般为2至8条指令

采用目前的指令调度技术，每个周期发射2至4条指令比较合理165例如：Intel公司的i860、i960、Pentium处理机，Motolora公司的MC88110处理机，IBM公司的Power6000处理机等每个周期都发射两条指令TI公司生产的SuperSPARC处理机以及Intel的PentiumIII处理机等每个周期发射三条指令操作部件的个数多于每个周期发射的指令条数。4个至16个操作部件

超标量处理机的指令级并行度：1＜ILP＜m；m为每个周期发射的指令条数1661675.3.1.3多流水线调度多条流水线的调度问题是一个NP完成问题。顺序发射(in-orderissue)与乱序发射(out-orderissue)指令的发射顺序是按照程序中的指令排列顺序进行的称为顺序发射。顺序完成(in-ordercompletion)与乱序完成(out-ordercompletion)指令的完成顺序按照程序中的指令排列顺序进行的称为顺序完成。多流水线的调度主要有三种方法顺序发射顺序完成顺序发射乱序完成乱序发射乱序完成1681691、顺序发射顺序完成6条指令按顺序分三个时钟周期发射。6条指令共用10个时钟周期完成。除了流水线的装入和排空部分之外，还有8个空闲的时钟周期。1702、顺序发射乱序完成171与顺序发射顺序完成调度方法相比，少了5个空闲时钟周期。6条指令总的执行时间为9个时钟周期与顺序发射顺序完成调度方法相比节省了一个时钟周期。1723、乱序发射乱序完成采用乱序发射的指令调度方法，必须使用先行指令窗口。在采用乱序发射时，指令的完成次序必然也是乱序的。173除了装入和排空之外，已经没有空闲周期，功能部件得到充分利用。6条指令总的执行时间缩短为8个周期比顺序发射顺序完成方法节省两个周期比顺序发射乱序完成方法相比节省一个周期1745.3.1.4资源冲突操作部件采用流水线结构，发生资源冲突的可能性很小；如果不采用流水线结构，发生资源冲突的可能性就大。下面是一个由4条指令程序的程序：I1：FADDR0,R1；R0←(R0)+(R1)I2：FMULR2,R3；R2←(R2)×(R3)