【文档说明】计算机系统结构第五章标量处理机课件.ppt，共(216)页，1.196 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-5255.html

以下为本文档部分文字说明：

第五章标量处理机2022/11/132本章主要内容5.1先行控制技术5.2流水线技术5.3相关性分析技术5.4超标量处理机5.5超流水线处理机5.6超标量超流水线处理机3标量处理机只有标量数据表示和标量指令系统的处理机称为标量处理机，是最常用最普通的处理机。设计处理机的主

要任务就是缩短解释指令的时间，提高处理机指令的执行速度：1.提高处理机的工作主频。5、60年代主要采用这种技术，每3、4年处理机的速度要提高一个数量级。2.采用更好的算法和设计更好的功能部件，如采用RISC等。3.多条指

令并行执行。指令级的并行技术。流水线技术。处理机中设置多个独立的功能部件，如浮点运算器，定点运算器，访存部件等。超长指令技术。45.1先行控制技术先行控制技术的关键是采用缓冲技术和预处理技术，以及两者都采用，通过对指令流和数据流的预处理和缓冲，能够尽量使指令分析器和指令执行部件独立工作并始终处

于忙碌状态。5.1.1指令的重叠执行方式5.1.2先行控制方式的原理5.1.3处理机结构5.1.4指令执行序列5.1.5先行缓冲栈5.1.6缓冲深度的设计方法5指令的重叠执行方式一条指令的执行可以分为多个阶段，具体分法视处理机而定，

一般可以分为三个阶段：取指令是指按照指令计数器的内容访问主存，取出一条指令送到指令寄存器。分析指令是指对指令的操作码进行译码，按照给定的寻址方式和地址字段内容形成操作数地址，并用这个地址读出操作数，操作数可以在主存也可以在寄存器。执行指令是根据操作码的要

求，完成指令规定的功能，把结果写到主存或者寄存器。指令分析或者指令执行阶段还得修改指令计数器的更新，为下一条指令作准备。6指令的重叠执行方式1.顺序执行方式执行n条指令所用的时间为：如果每段时间都为t，则执行n条指令所用的时

间为：T＝3nt主要优点：控制简单，节省设备。主要缺点：速度慢，功能部件的利用率低。Ttttiiiin(取指令分析执行）1取指令k分析k执行k取指令k+1分析k+1执行k+172.一次重叠执行方式如果两个过

程的时间相等，则执行n条指令的时间为：T＝(1+2n)t主要优点：指令的执行时间缩短，功能部件的利用率明显提高。主要缺点：需要增加一些硬件，控制过程稍复杂。取指令k分析k执行k取指令k+1分析k+1执行k+1取指令k+2分析k+2执行k+2指令的重叠执行方式(续)83.二次重叠执行方式如

果三个过程的时间相等，执行n条指令的时间为：T＝(2＋n）t在理想情况下，处理机中同时有三条指令在执行。处理机的结构要作比较大的改变，需要采用先行控制技术。取指令k分析k执行k取指令k+1分析k+1执行k+1取指令k+2分析k+2

执行k+2二次重叠执行方式指令的重叠执行方式(续)9先行控制方式的原理1.采用二次重叠执行方式必须解决两个问题：(1)有独立的取指令部件、指令分析部件和指令执行部件把一个集中的指令控制器，分解成三个独立的控制器：存储控制器、指令控制器、运算控制器。(2)要解决访问主存储器的冲突问题取指令、

分析指令、执行指令都可能要访问存储器。102.解决访存冲突的方法：(1)采用低位交叉存取方式：这种方法不能根本解决冲突问题。取指令、读操作数、写结果。(2)主存分为两个独立的存储器：独立的指令存储器和数据存储器。如果再规定，执行指令所需要的操作数和执行结果只写到通用寄存器，则取指令、分析指令和执

行指令就可以同时进行。在许多高性能处理机中，有独立的指令Cache和数据Cache。这种结构被称为哈佛结构。先行控制方式的原理（续）11(3)采用先行控制技术采用先行控制技术的关键是缓冲技术和预处理技术。缓冲技术通常用在工作速度不固定的两个功能部件

之间。设置缓冲栈的目的是用来以平滑功能部件之间的工作速度。在采用了缓冲技术和预处理技术之后，运算器能够专心于数据的运算，从而大幅度提高程序的执行速度。先行控制方式的原理（续）12处理机结构1.三个独立的控制器：存储控制器、指令控制器、运算控制器。2.四个缓冲栈：先行指令缓冲栈、先行读数缓冲栈

、先行操作栈、后行写数栈。3.处理机组成先行指令缓冲栈指令分析器主存存储先行操作栈通储控先行读数栈用器制运算控制器寄器存后行写数栈运算器器134.先行指令缓冲栈的组成作用：只要指令缓冲栈没有充满，就自动发出取指令的请求。指令分析器每分析完一条指令，自动

向指令缓冲栈发出取下一条指令的请求，指令取出后就把先行指令缓冲栈中的指令作废。分析指令速度和从主存取指令的速度是随机的，指令缓冲栈的指令数目是动态的。设置两个程序计数器：先行程序计数器PC1，用来指示取指令，现行程序计数器PC，记录指令分析器正在分析的指令地址。处理机结

构（续）14处理机结构（续）先行缓冲站的组成先行程序计数器PC1现行程序计数器PC指令分析器指令缓冲存储器堆指令寄存器IR存储控制器控制逻辑指令缓冲存储器堆，采用先进先出的方式，保证指令的执行顺序不致混乱。15处理机结构（续）取指令k分析k执行k取指令k+1分析k+1执行k+1取指令k+2分析k

+2执行k+2先行控制方式中的一次重叠执行•重叠部分，无论谁先结束，都不能提前执行下一条指令，需要等待。•无论任何时刻，在指令分析部件和指令执行部件内都只有相邻的两条指令重叠执行，处理机只需要设置一套指令分析部件，——指令控制器；一套指令执行部件，

——运算控制器和运算器。控制方式简单。•所需要时间为T=（1+n）t16处理机结构（续）5.存在的主要问题：①计算机指令系统复杂，各类指令“分析”和“执行”的时间相差很大，分析指令和执行指令常常相互等待，造成部件的浪费。②分析k+1操作所需要的操作数正好

是执行k的结果，不能重叠执行，发生数据相关，还有控制相关，变址相关。③转移或转子程序指令时，程序的执行过程不是顺序的，先行指令缓冲栈中预取指令和分析的下一条指令都可能要作废。17指令执行时序设置了指令缓冲栈，取指令的时间就可以忽略不计。一条指令的执行可分为2个过程

。1.分析指令和执行指令时间不相等时的情况。分析k执行k分析k+1执行k+1分析k+2执行k+2分析k+3执行k+318指令执行时序2.采用先行缓冲栈的指令执行过程先行读数栈,先行操作栈,后行写数栈。理想情况下，指令执行部件应该一直忙碌。连续执行n条

指令的时间为：分析k执行k分析k+1执行k+1分析k+2执行k+2分析k+3执行k+3niiniitttT111执行执行分析先行19先行缓冲栈设置先行缓冲栈的目的：使指令分析器和指令执行部件能够独立工作。1

.先行指令缓冲栈：处于主存储器与指令分析器之间。用它来平滑主存储器取指令和指令分析器使用指令之间的速度差异。RR型指令，不必处理，直接送先行缓冲栈。RS型指令，主存有效地址送先行读数栈，用该先行读数栈的寄存器编号替换指令中的主存地址码部分，形成RR*指令送先行缓冲栈。20RI型指令，

指令中的立即数送先行读数栈，用该先行读数栈的寄存器编号替换指令中的立即数部分，形成RR*指令送先行缓冲栈。转移指令，一般在指令分析器中直接执行。2.先行操作栈处于指令分析器和运算控制器之间。使指令分析器和运算器能够各自独立工作。采用先进先出方式工作，由指令寄存器堆和控制逻

辑组成。先行缓冲栈（续）213.先行读数栈处于主存储器与运算器之间。平滑运算器与主存储器的工作。每个缓冲寄存器由地址寄存器、操作数寄存器和标志三部分组成。也可以把地址寄存器和操作数寄存器合为一个。当收到从指令分析器中送来的有效地址时，就向主存申请读操作数。读出的操作数存放在操作数寄存

器中或覆盖掉地址寄存器中的地址。先行缓冲栈（续）224.后行写数栈每个后行缓冲寄存器由地址寄存器、数据寄存器和标志三部分组成。指令分析器遇到向主存写结果的指令时，把形成的有效地址送入后行写数栈的地址寄存器中，并用该地址寄存器的编号替换指令的目的地

址部分，形成RR*指令送入先行操作栈。当运算器执行这条RR*型写数指令时，只要把写到主存的数据送到后行写数栈的数据寄存器中即可。先行缓冲栈（续）23先行缓冲栈（续）5.采用先行控制方式时一个程序的执行情况：

指令地址指令执行情况„„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„„还没有进入处理机的指令24缓冲深度的设计方法以静态分析为主，通过模拟来确定缓冲深度。1.先行指令缓冲栈的设计考虑两种极端情况：假设缓冲深度为DI(1)先行指令缓冲栈已经充满指令流出

的速度最快，例如连续分析RR型指令，设这种指令序列的最大长度为L1，平均分析一条这种指令的时间为t1。指令流入的速度最慢，设平均取一条指令的时间为t2。从主存储器中取到先行指令缓冲栈中的指令条数是L1－DI条。25应该满足如下

关系：L1t1＝(LI－DI)t2计算出缓冲深度为：如果这种指令流的连续长度超过L1，则先行指令缓冲栈被取空，指令分析器没有指令可分析，被迫处于等待状态。缓冲栈失去作用。(2)先行指令缓冲栈原来为空输入

端指令流入的速度最快，每次取指令的时间最短；设这种指令序列的最大长度为L2，平均取一条这种指令的时间为t2’；DLtttI1212()缓冲深度的设计方法（续）26输出端指令流出的速度最慢，指令分析器连续分析最难分析的指令；设平均分析一条指令的时间为t1’。分析的指令条

数是L2－DI条。应该满足如下关系：(L2－DI)t1’＝LIt2’计算出缓冲深度为：如果这种指令流的连续长度超过L2，先行指令缓冲栈被完全充满，失去缓冲作用。DLtttI2121('')'缓冲深度的设计方法（续）272

.设计举例在一般处理机中连续执行短指令的概率大。例：一个采用先行控制方式的处理机，指令分析器分析一条指令用一个周期，到主存储器中取一条指令装入先行指令缓冲栈平均用4个周期，如果这种指令的平均长度为9，即90％的指令是执行时间短的指令。解：计算先行指令缓冲

栈的缓冲深度为：DLtttI121294147()()缓冲深度的设计方法（续）283.先行指令缓冲栈的工作时间关系第1个周期，取走指令k+1，请求取指令。第4个周期末尾，指令k+8取到先行指

令缓冲栈。第8个周期末尾，指令k+9取到先行指令缓冲栈。第9个周期，分析指令k+9，先行指令缓冲栈空。第10个周期，指令分析器等待。工作周期12345678910指令分析器的指令序列k+1k+2k+3K+4K+5K+6K+7K+8k+9空向主存请求取指令指令

取到先行缓冲栈中缓冲栈中剩余指令条数65433*211*00缓冲深度的设计方法（续）294.其余缓冲栈的设计原则一般有关系：DI≥DC≥DR≥DW其中：DI是先行指令缓冲栈的缓冲深度，DC是先行操作栈的缓冲深度，DR是先行读数栈的缓冲深度，D

W是后行写数栈的缓冲深度。例如：IBM370/165机：DI＝4，DC＝3，DR＝2，DW＝1。我国研制的两台大型计算机：DI＝8，DC＝DR＝4，DW＝2。DI＝12，DC＝DR＝6，DW＝2。缓冲深度的设计方法（续）30数据相关

数据相关：在执行本条指令的过程中，如果用到的指令、操作数、变址量等是前面指令的执行结果，这种相关称为数据相关。控制相关：由条件分支指令、转子程序指令、中断等引起的相关。解决数据相关的方法有两种：推后分析法，遇到相关数据，推后本条指令的分析，直至所需要的数据写入到相关的存储单元。设置专用路

径。不必等到所需要的数据写入到相关存储单元，而是经专门设置的数据通路读取所需要的数据。311.指令相关发生指令相关的情况：n：STORER1,n+1n+1：……满足关系：结果地址(n)＝指令地址(n+1)当第n条指

令还没有把执行结果写到主存之前，取出的第n+1条指令显然是错误的。在k个流水段的流水线处理机中，第n条指令要修改从第n+1到第n+k指令中的任意一条指令，都可能造成程序执行结果发生错误。数据相关（续）32在采用先行控制方式的处理机中，

如果执行部件正在执行第n条指令，与下述情况之一发生相关，都可能造成程序执行结果发生错误。存放在先行操作栈中的指令正在指令分析器中分析的指令已经预取到先行指令缓冲栈中的指令指令执行结果还在后行缓冲栈中的指令更严重

的是：有些分支指令，可能已经在指令分析器中执行完成。数据相关（续）33解决指令相关的根本办法是：在程序执行过程中不允许修改指令。现代程序设计方法要求程序具有再入性，可以被递归调用等，也要求不修改指令。在IBM370系列机

中，用“执行指令”来解决：在程序执行过程中既能够修改指令，程序又具有再入性。“执行指令”执行由第二地址((X2)+(B2)+D2)决定的主存数据区中的指令。07811121516192031EX（执行）R1X2B2D

2数据相关（续）342.主存操作数相关发生主存操作数相关的指令序列：n：OPA1，A2，A3；A1＝(A2)OP(A3)n+1：OPA4，A1，A5；A4＝(A1)OP(A5)出现下列情况之一，A1、A2、A3是主存地址，就发生主存操作数相关：A1（n）＝A2（n＋1）A1（n）＝A3（n＋1）解

决办法：运算结果写到通用寄存器，而不写到主存对于访问主存储器的请求，写结果的优先级高于读操作数。数据相关（续）35分析k执行k分析k+1分析k+1(推后)执行k+1时间t读主存A1单元请求存储控制器的排队器先响应写主存

请求结果写主存A1单元的请求有先行操作栈处理机中，分析指令、已经执行指令需要进入后行写数操作栈向主存写回运算结果的指令之间可能相隔很多条指令。已经进入先行操作栈的任何一条指令在向主存申请读数时都可能与正在执行部件中执行的指

令、正在后行写数栈中等待写结果到主存的指令，甚至还在先行操作栈中的指令发生主存操作数相关。解决办法：对于刚进入先行操作栈中的指令在向主存读数之前，首先把访问主存的地址与后行写数栈中的所有主存地址比较，如果发现有相等的，则先行栈

的读数操作缓行，等到相关写操作数指令完成，并把结果写到主存之后再读数。数据相关（续）36数据相关（续）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数据相关。37解决通用寄存器数据相关的方法：方法一：把读操作数、写运算结果与指令执行合在一个节拍。从数

据从通用寄存器读出，在运算器中完成运算，结果写回通用寄存器的整个回路中，只有通用寄存器是时序逻辑。当发生下述情况时，不能采用这种方法：当寄存器个数多时，读写寄存器的时间长。当功能部件数量多时，寄存器的读写端口多。当功能部件的执行时间比较长，或要求指令的

执行时间短时。数据相关（续）38方法二：建立相关专用通路(ByPass)由于发生寄存器数据相关的情况很普遍，一般计算机系统都采用专用数据通路。把读通用寄存器、执行操作和写结果分为3个周期，或2个周期。采用专用数据通路能够缩短1至2个周期。D触发器构成通用寄存器堆多路选择器多路选

择器运算器一种典型的运算器结构通用寄存器堆相关专用通路锁存器锁存器运算器设置专用数据通路解决通用寄存器数据相关数据相关（续）39变址相关：在采用变址寻址方式的处理机中，由于变址量放在寄存器中，因此，可能发生与通用寄存器数据相关类似变址相关.4.LOA

D相关LOAD操作的执行时间可能比较长n：LOADR1，A；R1＝(A)n+1：ADDR1，R2；R1＝(R1)OP(R2)如果R1(n)＝R2(n＋1)，或R1(n)＝R1(n＋1)，则发生LOAD数据相关。数据相关（续）40解决方法：方法一：由编译器

在LOAD之后插入不发生数据相关的指令，由于LOAD的执行时间不确定，不能根本解决问题。方法二：由硬件自动插入空操作，直到LOAD操作完成。在单条流水线处理机中，也可以停止节拍发生器，直到数据从存储器中读

出为止。K：IFIDEXWRK+1：IFIDEXWRIF：取指令，ID指令译码，EX：执行，WR：写回结果LOAD写R1完成ADD读R1开始数据相关（续）41控制相关因程序的执行方向可能被改变而引起的相关，也称为全局相关。主要包括：无

条件转移、一般条件转移、复合条件转移、中断等。1.无条件转移在流水线处理机中，无条件转移指令不进入执行流水段，一般在指令译码阶段就实际执行完成。如果在处理机中设置有指令先行缓冲栈，则要全部或部分作废先行指令缓冲栈中的指令。42如果转移目标

指令L不在先行指令缓冲栈中，则要将先行指令缓冲栈中的所有指令全部作废，并等待取出转移目标指令L。如果转移目标指令L在先行指令缓冲栈中，只要作废先行指令缓冲栈中的部分指令。无条件转移指令一般对指令执行部件的工作不会造成影响。为进一步减少无条件转移指令造成的影响，在先行指令

缓冲栈的入口处增设一个专门处理无条件转移指令的指令分析器控制相关(续)43分析k执行k分析k+1指令L不在先行指令缓冲栈中：取指令L分析L执行L指令L在先行指令缓冲栈中：分析L执行L分析L+1执行L+1无条件转移指令的执行时序2.一般条件转移k：……;置条件码CCk+1：JMP(CC)L;

如果CC为真转向L……L：……•当条件码是上一条指令产生时，相关最严重控制相关(续)44分析k执行k转移不成功分析k+1分析k+2执行K+2成功,L在缓冲栈分析k+1分析L执行L成功,L不在缓冲栈分析k+1取指令L分析L执行L产生转移条件CC根据转移

条件CC判断转移是否成功无论转移是否成功，条转移指令都在指令分析阶段就已经执行完成。无论转移不成功或不成功，指令分析器要停顿一段时间，等待条件码产生。控制相关(续)45如果转移成功：指令L已经在先行指令缓冲栈，指令分析器接着“分析L”，如果指令L不在先行指令缓冲栈，指令分析器要等

待一个周期。转移不成功，对程序执行影响不大，当转移成功时，不仅指令执行过程变成完全串行，而且要作废先行指令缓冲栈中的大量指令。在采用流水线方式的处理机中，要通过软件与硬件的多种手段来近可能地降低转移成功的概率，减少转移成功造成的影响。控制相关(续)463.复合条件转移k：

OPL;产生条件码，并决定是否转向L……L：……如果转移不成功：不造成任何影响，就象普通的运算型指令一样如果转移成功：造成的影响比一般条件转移指令还要大得多。全部或部分作废先行指令缓冲栈、先行操作栈、先行读数栈和指令分析器中的指令。必须采取策略，减小转移成功造成的影响。控制相关(续)47分析k

执行k转移不成功分析k+1执行k+1分析k执行k成功，L在先行指令缓冲栈中分析L执行L分析k执行k成功，L不在先行指令缓冲栈中取指令L分析L执行L控制相关(续)48转移预测技术转移预测技术包括：静态分支预

测：在程序执行过程中转移预测方向不能改变动态分支预测：在程序执行过程中能够改变转移预测方向49静态分支预测技术1.软件“猜测法”目标：通过编译器尽量降低转移成功的概率。例如：对于循环程序，普通编译器生成的目标代码，转移成功的概率很高，不成功的只有一次。这种编译结果对流水

线极为不利。优点：不需要改变先行控制器的硬件结构，只需适当修改编译器就能够大幅度降低条件转移指令对先行控制器产生的影响。其最终目标是提高处理机执行程序的速度。50静态分支预测技术（续）软件“猜测法”：通过编译器降低转移成功的概率i←ni←ni←n循环体i＝0Yi←i－1Ni←i－1循环体i＜0YN

Yi＞0i←i－1循环体N(a)原来程序(b)一般条件转移(c)复合型条件转移512.硬件“猜测法”方法：通过改变硬件结构来降低转移指令对流水线的影响在先行指令缓冲栈的入口处设置一个简单的指令分析器，

当检测到转移指令时，就把转移目标地址L送入先行程序计数器PC1中，同时保留当前PC1中的内容到另一寄存器中。转移成功，猜测正确。对转移指令对流水线不造成影响。转移不成功，用保存下来的地址恢复PC1和PC。软硬件共同配合，都往同一个方向去猜测。静态分支预测技术（续）523.两个

先行指令缓冲栈向前条件转移，转移成功与不成功各50%在先行指令缓冲栈中增加一个先行目标缓冲栈按照转移成功的方向预取指令到先行目标缓冲栈中。先行指令缓冲栈仍然按照转移不成功的方向继续预取指令。如果转移不成功，则继续分析原来先行指令缓冲栈中指令。如果转

移成功，则分析新增设的先行目标缓冲栈中的指令。静态分支预测技术（续）53K：BC按TR1PC执行转移PCTR1原TR2PC1PC1TR2执L:„„LPC1、PC行k:„L+1:„„顺k+1:·从L开始取指令序·装入AIB，执···等待条件码CC行·AI

B成功判CC不成功IB两个先行指令缓冲栈的条件转移指令执行流程静态分支预测技术（续）•AIB，新增先行指令缓冲栈，IB原先行指令缓冲栈。•TR1，TR2，保存PC1和PC中的内容，转移不成功，恢复PC1和PC。54短循环程序的处理在循环程序中存在大量的短循环程序，对于短循环程序，一般

先行指令缓冲栈的效率很低，一种极端的情况是：当循环体只有一条指令，先行缓冲栈失效。指令分析器分析完该指令后就清除指令缓冲栈，重新到主存取指令。短循环程序的特点：1.循环体的长度小于等于先行指令缓冲栈的深度。使得在循环程序执行过程中，整个循环体能够始终

存放在先行指令缓冲栈不被清除。循环程序可以多次重复使用减少访问主存的次数。2.循环次数的控制采用计数转移指令实现。因为计数转移指令可以在指令分析器中直接执行，指令分析器分析到这种特殊条件转移指令时不必等到指令执行部件形成条件码，而在指令分析器中就可以判断循环出口条件是

否满足。3.控制循环的条件转移指令一般是向后转移的指令。55短循环程序的处理（续）要在先行控制器中对短循环程序作特殊处理，必须解决好三个问题：①指令分析器如何发现短循环程序。②如何控制短循环程序在先行缓冲栈不被清除。

③如何控制循环体的执行次数，即处理好循环体的出口。56短循环程序的处理（续）方法一：在指令系统中专门设置短循环程序的开门指令和关门指令，由编译器在对源程序进行编译时发现短循环程序，并在其开头加上短循环开门指令，在末尾加上关门指令。在指令分析器中增加专门的硬件来处理短循环开关门指令。设置专门的

短循环标志触发器TL。当TL=1时表示先行指令缓冲栈内是短循行程序而不被清除57短循环程序的处理（续）执行过程：指令分析器分析到开门指令表示循环开始，开门指令主要为循环做预处理：将短循环程序的循环次数送入指令分析器的循环次数计数器。设置短循环程序在先行指令缓冲栈的起

始地址，即入口。置位短循环标志触发器TL，表示短循环程序的开始。先从指令缓冲栈中取出一条指令进行分析，如果TL=1，每从指令缓冲栈取一条指令，都不清除该指令。执行到关门指令，循环体结束，指令缓冲栈放置了全部该段循环体的

指令。每次循环都执行关门指令，关门指令控制循环体的次数。58短循环程序的处理（续）关门指令的工作：把循环计数器减1。若循环计数器值大于等于1，现行程序计数器指向短循环程序的入口，准备下一次循环。若等于1，还要把Tl清零。当Tl=0时，每分析一条指令就清除该指令，先行缓冲栈恢复正常功能。若循环

计数器值为0，循环结束，顺序执行后续指令。59短循环程序的处理（续）优缺点：优点是硬件简单，开关门指令确定循环体，指令操作马即可识别此两条指令，不需专门的硬件。缺点是增加了程序员的负担。方法二：在有的机器中为使短循环程序处理对程序员透明，

不采用专门的开关门指令。而是采用专门的硬件来识别短循环程序。IBM360/370在指令分析器中有一个向后检测8条指令的功能，如果条件转移指令的转移目标地址和转移指令本身地址相差小于0，大于-8，即认为遇到短循环程序。处理方法和开关方法相同。许多高性能处

理机采用专门的一级指令Cache，把指令Cache和数据Cache分开，其中指令可以较长时间保存，有效提高循环程序的执行速度。605.2流水线处理机技术空间并行性：设置多个独立的操作部件时间并行性：分时使用同一个部件的不同部分5.2.1流水线工作原理5

.2.2流水线的分类5.2.3线性流水线的性能分析5.2.4非线性流水线的调度61流水线工作原理1.流水寄存器流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。在

每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等。加入流水寄存器，会增加指令的执行时间。在一般流水线时空图中不画出流水寄存器。622.一种指令流水线一般4至12个流水段，≥8个流水段的称为超流水线处理机3.流水线时空图空

间执行部件执行k执行k+1执行k+2执行k+3分析部件分析k分析k+1分析k+2分析k+3取指令部件取指令k取指令k+1取指令k+2取指令k+30t1t2t3t4t5时间输入输出取指令i分析i执行i流水线

寄存器流水线寄存器△t流水线工作原理（续）63流水线工作原理（续）一个浮点加法器流水线的时空图空间规格化规格化1规格化2规格化3规格化4规格化5尾数加尾数加1尾数加2尾数加3尾数加4尾数加5对阶对阶1对阶2对阶3对阶4对阶5求阶差求阶差1求阶差2求阶差3求阶差4求阶差50t1t2t3t4t

5t6t7t8时间644.流水线的主要特点只有连续提供同类任务才能发挥流水线效率尽量减少因条件分支造成的“断流”通过编译技术提供连续的相同类型操作每个流水线段都要设置一个流水寄存器时间开销：流水线的执行时间加长是流水线中需要增加的主要硬件各流水段的时

间应尽量相等流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。流水线需要有“装入时间”和“排空时间”流水线工作原理（续）65流水线的分类1.线性流水线与非线性流水线流水线的各个流水段之间是否有反馈信号线性流水线（Li

nearPipelining）：每一个流水段都流过一次，而且仅流过一次非线性流水线（NonlinearPipelining）：某些流水段之间有反馈回路或前馈回路。线性流水线能够用流水线连接图唯一表示。非线性流水线必须用流水线连接图和流水线预约表共

同表示。66流水线的分类（续）2.按照流水线的级别来分处理机级流水线，又称为指令流水线。例如：在采用先行控制器的处理机中，各功能部件之间的流水线输入先行指令缓冲栈先行指令分析器先行读数栈先行操作栈指令执行部件后行写数栈输出功能:取指令指令

译码,形成操作数地址取操作数形成RR*指令执行算术逻辑运算向存储器写结果先行控制方式中的指令流水线前馈回路输入S1S2S3输出反馈回路一种简单的非线性流水线67流水线的分类（续）部件级流水线(操作流水线)如浮点加法器流水线宏流

水线(MacroPipelining)处理机之间的流水线称，每个处理机对同一个数据流的不同部分分别进行处理。输入求阶差对阶尾数加规格化输出△t1△t2△t3△t4输入处理机1处理机2„处理机n输出功能:任务1任务2任务n存储器存储器存储器68流水线的分类（续）3.单功能流水线与多功能流水线单功

能流水线：只能完成一种固定功能的流水线。Cray-1计算机种有12条，YH-1计算机有18条Pentium有一条5段定点和一条8段浮点流水线。PentiumⅢ有两条定点和一条浮点指令流水线。多功能流水线：流水线

的各段通过不同连接实现不同功能Texas公司的ASC机，8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。69流水线的分类（续）ABABABAB输入输入输入输入求阶差求阶差求阶差求阶差对阶对阶对阶对阶尾数加尾数加尾数加尾数加规

格化规格化规格化规格化尾数乘尾数乘尾数乘尾数乘累加累加累加累加输出输出输出输出g=f(A,B)定点乘浮点加浮点点积(a)功能段间的互连(b)定点乘法(c)浮点加法(d)浮点点积704.静态流水线与动态流水线静态流水线：同一

段时间内，多功能流水线各个功能段只能按照一种方式连接，实现一种固定的功能。空间浮点加法定点乘法输出123„„n-1n1„累加12„尾数乘123„规格化123„„n-1n尾数加123„„n-1n对阶123„„n-1

n求阶差123„„n-1n输入123„„n-1n1234„时间静态流水线时空图流水线的分类（续）71动态流水线：在同一段时间内，多功能流水线各段可以按照不同的方式连接，同时执行多种功能。空间浮点加法定点乘法输入123„„n-1n123„求阶差1234„对阶12345„尾数加123„„n

-1n规格化123„„n-1n尾数乘123„„n-1n累加123„„n-1n输入123„„n-1n123456„时间动态流水线时空图流水线的分类（续）条件：流水线中各个功能部件之间不能发生冲突。725.流水线的其他分类

方法按照数据表示方式：标量流水线和向量流水线按照控制方式：同步流水线和异步流水线顺序流水线与乱序流水线，按照流水线输出端流出的任务和流水线输入端流入的任务顺序是否相同划分。乱序流水线又称为无序流水线、错序流水线或异步流水线等。输入就绪回答S1就绪

回答S2就绪回答Sn输出就绪回答一种异步流水线流水线的分类（续）73线性流水线的性能分析主要指标：吞吐率、加速比和效率1.吞吐率（ThoughPut），单位时间内流水线所完成的任务数量或输出结果数量。流水线吞吐率的最基本公式：其中：n为任务数，Ｔk为完成n个任务所

用的时间。各段执行时间相等，输入连续任务情况下，完成n个任务需要的总时间为：Tk＝(k＋n－1)t其中：k为流水线的段数，t为时钟周期。kTnTP74线性流水线的性能分析（续）依据：从输出端：用k个时钟周期输出第一个任务，其余n-1个

周期，每个周期输出一个任务，共n-1个任务。从输入端：用n个周期输入n个任务。另外还有k-1个周期等待流水线排空。75线性流水线的性能分析（续）Tk=k·Δt+(n-1)Δt=(k+n-1)t吞吐率为：最大吞吐率为：空间S4123„„n-1nS3123„„n-1nS

2123„„n-1nS1123„„n-1n时间k·t(n－1)tn·t(k－1)tTTPnknt()1nTPLimnknttmax()1176线性流水线的性能分析（续）最大吞吐率和实际吞吐率的关系：流水线的实际吞吐率要小于最大吞吐

率。实际吞吐率和Δt，流水线短数k，输入到流水线的任务数n相关。只有n﹥﹥k时，才有TP≈TPmax。max1TPnknTP77线性流水线的性能分析（续）各段时间不等，完成n个连续任务：吞吐率：最大吞吐率：流水线各段执行时间不相等的解决办

法TPntntttiikk1121()max(,,,)),,,max(121ktttTP输入S1S2S3S4输出t1＝tt2＝3tt3＝tt4＝t78线性流水线的

性能分析（续）(1)将“瓶颈”部分再细分（如果可分的话）空间S4123„nS3123„nS2123„nS1123„n时间kiit1（n－1）t2Tk各段执行时间不相等的流水线及其时空图输入S1S2-1S2-2S2-3S3S4输出tttttt“瓶颈”流水段

再次细分S2(3t)79线性流水线的性能分析（续）(2)“瓶颈“流水段重复设置：增加分配器和收集器S2-3输入S1S2-2S3S4输出t1＝tt3＝tt4＝tS2-1t2＝3t空间S4123456„n-2n-1nS3123456„n-

2n-1nS2-336„nS2-225„n-1S2-114„n-2S1123456„n-2n-1n时间流水段重复设置的流水线80线性流水线的性能分析（续）2.加速比（Speedup）计算加速比的基本公式：各段执行时间相等，输

入连续任务情况下,加速比：最大加速比：各段时间不等，输入连续任务情况下,实际加速比为：STTk顺序执行时间流水线执行时间0Skntkntknkn()11SLimknknknmax1Snttntttiikiikk

11121()max(,,,）81线性流水线的性能分析（续）是否流水线的段数越多越好？当流水线段数增加时，需要连续输入的任务数也必须增加。由于程序中存在数据相关、转移、中断等情况。任务数n受到很大限制。控制的复杂性，电路的实现及组装

技术，实现的成本等的限制，流水线不可能很多。加速比S10加k=10段8速6比k=6段4211248163264128n任务个数823.效率（Efficiency）——流水线的设备利用率。计算流水线效率的一般公式：各流水段时间相等，输入n个连续任务，流水线的效率为：最高效率为：各流水段时间不等，输

入n个连续任务，流水线效率为：EnkTkTk个任务占用的时空区个流水段的总的时空区0Ekntkkntnkn()11ELimnknnmax11Entktntttiikiikk11121[)max(,,,)]（

线性流水线的性能分析（续）83各段设备量或价格不等时，流水线的效率为：即：其中，ai＜k，且＝k。流水线的吞吐率、加速比与效率的关系：因为：因此：E＝TP·t，S＝k·E空区个流水段的总的加权时区个任务占用的加权时空knEEnataatnttti

iikiIikiiikn111121[)max(,,,)]（TPnknt()1Sknkn1Enkn1线性流水线的性能分析（续）844.流水线最佳段数的选择采用顺序执行方式完成一个任务的时

间为t在同等速度的k段流水线上执行一个任务的时间为：t／k＋d(d为流水锁存器的延迟时间)流水线的最大吞吐率为：P=1／(t／k＋d)流水线的总价格估计为：C＝a＋bk，其中：a为功能段身的总价格，b为每个锁存器的价格A.G.Larson把流水线的性能价格比PCR定义为：PCRPCtkd

abk11/线性流水线的性能分析（续）85线性流水线的性能分析（续）求PCR的最大值为：bdatk000)()())((0)')(1)((0)'1/1(2bdkatdktbkbkadkbkadktbkadktkbkadkt性能价

格比PCR峰值最佳值(k0)流水线段数k865.流水线性能分析举例对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。对于输入不连续任务，或多功能流水线，通

常采用基本公式计算。例：用一条4段浮点加法器流水线求8个浮点数的和：Z＝A＋B＋C＋D＋E＋F＋G＋H线性流水线的性能分析（续）87解：Z＝[(A＋B)＋(C＋D)]＋[(E＋F)＋(G＋H)]空间周期12345678910

1112131415规格化1234567尾数加1234567对阶1234567求阶差1234567时间加数ACEGA+BE+FA+B+C+D加数BDFHC+DG+HE+F+G+H结果A+BC+DE+Fg+HA+B+C+DZE+F+G+H用一条4段浮点加法器流水线求8个数之和的流水线

时空图线性流水线的性能分析（续）88解：7个浮点加法共用了15个时钟周期。流水线的吞吐率为：TPnTttk7150471流水线的加速比为：87115740ttTTSk流水线的效率为

：470154740ttTkTEk线性流水线的性能分析（续）89线性流水线的性能分析（续）例，多功能、线形流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。利用Ti-ASC多功能静态流水线计算两个向量的点积：Z=AB+CD+EF+GH

。解，为减少数据相关性充分发挥流水线的作用，因该先做4个乘法，AB，CD，EF，GH。然后坐两个加法AB+CD和EF+GH。最后求总的结果Z。90线性流水线的性能分析（续）流水线的时空图：76543217657657657654321432

17654321AB+CDEF+GHABEFCDGHABCDEFGH数据1数据2输入求阶差对阶尾数加规格化尾数乘累加输出ABCDEFGHAB+CDEF+GH时间空间91线性流水线的性能分析（续）20个周期完成7个运算。每个功能能段的延迟

时间都为△t，则Tk=20△t，n=7。则有流水线吞吐率TP为：如果采用顺序执行方式，完成一次乘法要用4个△t，完成一次加法要用6个△t，完成全部运算要用：Ｔ０＝４×４△t＋３×６△t＝３４△t。流水线的加速比Ｓ为：整个流水线共有８段，流水线的效率Ｅ为：ttTnTPk

135.020770.120340ttTTSk21.0208340ttkTTEk92线性流水线的性能分析（续）整个流水线效率很低：多功能流水线在做某一运算时，总有一些功能段是闲置的。静态流水线必须等前一种运算运算全部排除流水线之后才能重新进行连接。计算本身存在数据相

关，发生数据相关时必须等待前一个运算结果产生之后，下一个运算才能开始。流水线有装入和排空部分，当输入到流水线中的任务不多时，装入与排空部分所占的比例比较大。93非线性流水线的调度非线性流水线中存在反馈回路，当一个任务在流水线中流过时

，在同一功能段中可能要多次经过。不能在一个时钟周期内向流水线输入一个任务，否则会发生在同一个时刻有几个任务争用同一个功能段的情况。称为功能部件冲突或者流水线冲突。为避免冲突，采用延迟输入新任务的方法。间隔几个周期再输入新任务。间隔的周期数不

是一个常数。而是一串周期变化的数字。94非线性流水线的调度（续）非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。1.非线性流水线的表示线性流水线能够用流水线连接图唯一

表示对于非线形流水线，连接图不能唯一表示工作流程，因此，引入流水线预约表95非线性流水线的调度（续）例如：非线形流水线的连接图和预约表输出输入S1S2S3S4前馈线反馈线时间功能段1234567S1×××S2

××S3××S4×96非线性流水线的调度（续）四个功能段组成非线性流水线。与线性流水线相同地方：从第一个功能段S1到最后一个功能段S4的单方向传输线。不同的地方：有两条反馈线和一条前馈线。输出端经常不在最

后一个功能段，可能从中间的任意一个功能段输出。97非线性流水线的调度（续）预约表：预约表的横坐标表示流水线工作的时钟周期，纵坐标表示流水线的功能段。中间的X表示该功能段在该时钟周期处于工作状态。即有任务在该时钟段通过该功能段。

空白表示该时钟周期该功能段不工作。一行可以有多个X，表示一个任务在不同时钟周期重复使用同一个功能段。一列可以有多个X，指同一个时钟周期多个功能段被使用。预约表的行数是非线性流水线的段数。列数是指一个任务从进入流水线到从流水线输出经过的时钟周

期数。又称为功能求值时间或装入时间。98非线性流水线的调度（续）一张预约表可能与多个流水线连接图相对应时间功能段1234567S1×××S2××S3××S4×输出S4输入S1S2S3前馈线反馈线输出输入S1S2S3S4前馈线反馈线原因：在预约表的同一列中可能有多个X

，即该时钟周期有多个功能段输出，下一功能段的输入有多个来源，从而应对有多个连接图。99非线性流水线的调度（续）一个流水线连接图对应与多张预约表时间功能段1234567S1×××S2××S3××S4×输出输入S1S2S3S4前馈线反馈线时间功能段12

34567S1×××S2×S3××S4×原因：非线性流水线的有些功能段可能有多个输出端，也有些功能段有多个输入端，输出端和输入端之间连接的先后次序形成多张预约表。100非线性流水线的调度（续）2.非线性流水线的冲突启动距离：连续输入两个任务之间的时间间隔，又称等待时间。流水线冲突：以某启动距离连续

向一条非线性流水线输入任务，可能会存在几个任务争用同一个流水段。启动距离为3的流水线冲突情况时间功能段1234567891011„S1X1X1X2X1X2X3X2X3X4„S2X1X1X2X2X3X3X4„S3X1X2X1X3X2X4„S4

X1X2X3„启动距离为2的流水线冲突情况时间功能段1234567891011„S1X1X2X1X3X2X1X4X3X2X5X4X3X6„S2X1X2X1X3X2X4X3X5X4„S3X1X2X1X3X2X4X3X5„S4X1X2X3X4X5„101启动距离为5时的流水线不冲突时间功能段1234

567891011„S1X1X1X2X1X2X3„S2X1X1X2X2„S3X1X1X2X2„S4X1X2„启动周期重复启动周期启动距离为(1,7)循环时的流水线预约表时间功能段123456789101

11213141516„S1X1X2X1X2X1X2X3X4X3X4X3X4„S2X1X2X1X2X3X4X3X4„S3X1X2X1X2X3X4X3X4„S4X1X2X3X4„启动周期重复启动周期非线性流水线的调度（续）102非

线性流水线的调度（续）引起非线性流水线功能段冲突的启动距离称为禁止启动距离。有些启动距离在非线性流水线的所有功能段，在任何时间都不会发生冲突，如前表的（5），（1，7）。不发生冲突的启动距离不一定仅仅是一个常数，在一般情况下是一个循环数列。称为非线性流水线的启动循环。只有一个启动距

离的启动循环又称为恒定循环。103非线性流水线的调度（续）要正确的调度一条非线性流水线，首先需要找到流水线的所有禁止启动距离。把所有禁止启动距离组合在一起形成数列，称为非线性流水线的禁止向量。计算禁止向量：把预约表中每一行中任意两个X之间的距离算出来，去掉重复的，这些数组成数列就是该非线性流水

线的禁止向量。把一个启动循环内的所有启动距离相加再除以这个启动循环内的启动距离个数就得到该启动循环的平均启动距离。1043.无冲突调度方法主要目标：找出最小平均启动距离的启动循环。由E.S.Davidson及其学生于1971年提出禁止向量：预约表中每一行任意两个“×”之间距离的集合。上例中为（3，

4，6）冲突向量：用C＝（CmCm-1…C2C1）表示，m位的二进制数。其中：m是禁止向量中的最大值。如果i在禁止向量中，则Ci＝1，否则Ci＝0。上例中C＝(101100)时间功能段1234567S1×××S2××

S3××S4×非线性流水线的调度（续）105非线性流水线的调度（续）由冲突向量可以构造状态图。①将冲突向量C作为初始冲突向量送入m位的右移逻辑移位器。移出为0，移位器内的值和初始冲突向量做按位或运算。得到一个新的冲突向量。②移出为1，不做任何处理。移位器继续右移。③中间形成的新的冲突向量，

也按上述方法处理。④在初始向量和新的冲突向量之间用箭头连接，并标注右移次数。表示各种状态之间的转换关系，向量重复时合并到一起。106非线性流水线的调度（续）当初始冲突向量确定后，状态图就是唯一的。不同的预约表可能产生相同的初始冲突向量，因而不同的预约表也可能有相同的状态图。从预约表可以

画出状态图，冲状态图不能获得预约表。当启动距离大于或等于m+1时，流水线的任何一个功能段在任何时钟周期都不会发生冲突，但流水线的吞吐率、加速比、效率都很差。107例：一条4功能段的非线性流水线，每个功能段的延迟时间都相等，它的预约表如下：(1)写出流水线的禁止向量和

初始冲突向量。(2)画出调度流水线的状态图。(3)求最小启动循环和最小平均启动距离。(4)求平均启动距离最小的恒定循环。时间功能段1234567S1XXS2XXS3XXS4X非线性流水线的调度（续）108解：(1)禁止向量为：(2，4，6)初始冲突

向量：S=101010(2)构造状态图S逻辑右移2、4、6位时，不作任何处理，逻辑右移1、3、5和大于等于7时：S右移1位之后：010101∨101010＝111111，S右移3位之后：000101∨101010＝101111，S右移5位之后：000001∨101010＝101011，S

右移7位或大于7位后：按位或就还原到它本身。非线性流水线的调度（续）109非线性流水线的调度（续）新冲突向量再处理：101111右移5位之后：000001∨101010＝101011，101011右移3位之后：000101∨101010＝101111，101011右移5位之后：0

00001∨101010＝101011。7*１０１0１０7*1537*7*１１１１１1１０１１１１53１０１0１１5非线性流水线的状态图110简单循环：状态图中各种冲突向量只经过一次的启动循环。在一个状态图中，简单

循环的个数是有限的。(3)最小的启动循环为（1，7）和（3，5）,平均启动距离为4。(4)启动距离最小的恒定循环为（5）简单循环平均启动距离（1，7）4（3，7）5（5，7）6（3，5，7）5（5，3，7）5（3，5）4（5）5（7）7非线性流

水线的调度（续）111非线性流水线的调度（续）最小启动循环(1,7)的流水线工作状态时间功能段123456789101112131415„S1X1X2X1X2X3X4X3„S2X1X2X1X2X3X4X3X4„S

3X1X2X1X2X3X4X3X4„S4X1X2X3X4„启动周期重复启动周期最小启动循环(3,5)的流水线工作状态时间功能段123456789101112131415„S1X1X2X1X3X2X4X3„S2X1X2X1X2X3X4X3„S3X1X1X2X2X3

X3X4„S4X1X2X3X4„启动周期重复启动周期112恒定启动循环(5)的流水线工作状态时间功能段123456789101112131415„S1X1X2X1X3X2„S2X1X1X2X2X3„S3X1X1X2X2X3X3„

S4X1X2X3„启动周期重复启动周期非线性流水线的调度（续）1134.优化调度方法采用最小启动循环启动非线性流水线时，许多功能段还有空闲，即预约表中还有空白格子。最小启动循环实际上不能使非线性流水线充分发挥效率。L.

E.Shar于1972年提出流水线最小平均启动距离的限制范围：①最小平均启动距离的下限是预约表中任意一行里“×”的最多个数。即同一任务通过流水线中任意一个功能段的次数。②最小平均启动距离小于等于状态图中任意一个简单循

环的平均启动距离。③最小平均启动距离的上限是冲突向量中1的个数再加上1。1992年，L.E.Shar又证明了上述限制范围。最有用的是第1条。预约表中“×”最多的行一定是瓶颈流水段。要使整个流水线最大发挥作

用，必须使瓶颈功能段不间断工作。不得空闲。非线性流水线的调度（续）114非线性流水线的调度（续）采用预留算法来调度非线性流水线，可以达到最优调度。确定流水线的最小平均距离，最小平均距离等于预约表中任意一行中X的最大个数。或者同一

个任务流过任意功能段的最多次数。确定最小启动循环，相对于同一个最小平均启动距离可能有多个最小启动循环。其中有一个且只有一个启动距离都相等的恒定循环。选用该恒定循环为最小启动循环。结合流水线预约表和连接图，采用预留算法，通过插入非

计算延迟功能段实现最小启动循环。115对于前例的预约表，在同一行中“×”最多的为2个，因此，最小平均距离可以达到2。最小启动循环可以是(2)、(1,3)、(1,1,4)、(1,2,3)、……。现取恒定循环(2)。每一行中与第1个“×”的距离为2的倍数的位置都要预留出来。S3行的第2个“×”从周期5

延迟到周期6。为此，S2行的第2个“×”从周期6延迟到周期7；S1行的第2个“×”从周期7延迟到周期8。实际上，只要在流水段S4的输出端到流水段S3的输入端中间插入一个非计算延迟D1。非线性流水线的调度（续）116非线性流水线的调度（续）

采用预留调度算法的预约表时间12345678S1××S2××S3××功能段S4×延迟D1×注：表示由D1延迟一个时钟周期117非线性流水线的调度（续）增加了一个非计算延迟流水段D1的流水线连接图输出输入S1S2S3S4D1有非计算延迟的流水线状态图8*１０１0１０08*8*1246

8*１１１１１１0１０１0１0１1246１１１１１１１118按照最小启动循环（2）工作的流水线预约表时间123456789101112„功S1X1X2X3X4X1X5X2X6X3„能S2X1X2X3X1X4X2X5X3X6„段S3X1X2X1X3X2X4X3X

5X4„S4X1X2X3X4X5„延D1X1X2X3X4„在非线性流水线中，“×”最多的流水段一定是“瓶颈“流水段。实现最优调度的目标是使“瓶颈”流水段处于忙碌状态，没有空闲周期。最优调度方法能够使非线性流水线

的吞吐率、加速比和效率达到最优。非线性流水线的调度（续）119局部相关在流水线处理机中由于处理的指令条数很多，发生相关的可能性及其造成的影响将更严重。按照对程序执行过程可能造成的影响划分：可以把相关分为局部

相关和全局相关两类。如图，程序中一条分支指令把程序划分为三个部分，每部分内部不再有分支操作，这种部分称为基本块。B0B1B2120局部相关（续）同一个基本块内部的相关称为局部相关（lacalcorrelation）在基本块之间的相关成为全局相关（）。引起全局相关的除了分支操作还有中断。局部相关对

程序执行影响较小，仅限于相关指令临近的几条指令。全局相关影响很大，影响到整个程序的执行方向。121局部相关（续）促使流水线充分发挥作用，需要软硬件结合。软件编译的目标代码要适合流水线结构，尽量把相关数据和相关控制的指令安排

得远一些。把相同操作尽量安排在一起。在硬件方面解决好存储系统的频带问题，能够为流水线提高足够的指令和数据。解决好流水线的局部相关和全局相关。局部相关包括：先写后读数据相关，先读后写数据相关，写写相关三种。122顺序流动与乱序流动1.顺序流动方式：任务按顺序流入流水线,也

按顺序流出流水线把如下一段程序输入到这条流水线中：k：R0←（R1）k+1：……k+2：R2←（R0）＋（R3）k+3：……k+4：……k+5：……123读专用数据通路写输入S1S2S3S4S5S6输出寄存器R0指

令k+2无法继续执行，要在功能段S2中等待。后续的指令k+4、k+5、……等也不能进入流水线。功能段S3、S4、S5将逐渐空闲。缺点：吞吐率和效率降低优点：流水线的控制逻辑比较简单顺序流动与乱序流动（续）124顺序流动与乱序流动（续）流水线“断流”，有些功能段“空闲”

时钟周期ti+4k+4k+3k+2空闲空闲空闲ti+3k+3k+2空闲空闲空闲k+1ti+2k+3k+2空闲空闲k+1kti+1k+3k+2空闲k+1Kk-1tik+3k+2k+1kk-1k-2正常流动k+5k+4k+3k+2k+1

k功能段功能段S1S2S3S4S5S6顺序流动方式1252.乱序(Outoforder)流动方式：指令流出流水线的顺序与流入流水线的顺序不同。又称为错序流动方式、无序流动方式、异步流动方式等。时钟周期ti+5k+8(k+7)k+6k+2K+5k+4k+3ti+4k+7(k

+6)k+2k+5K+4k+3k+1ti+3k+6k+5(k+2)k+4k+3k+1kti+2k+5k+4(k+2)k+3k+1kk-1Ti-+1k+4k+3(k+2)k+1kK-1k-2tik+3(k+2)k+1kk-1k-1k-3正常流动k+5k

+4k+3k+2k+1k功能段功能段S1S2S3S4S5S6乱序流动方式顺序流动与乱序流动（续）126乱序流动中的数据相关在乱序流动方式中，可能发生三种数据相关写写相关k：LOADF1,A;F1（A）写读相关k+1：FADDF2,F1;F2（F2）+（F1）k+2：FMULF

1,F3;F1（F1）（F3）k+3：STOREF1,B;B（F1）读写相关(1)写读相关：指令k与指令k+1之间关于F1的相关，又称为数据相关、先写后读相关、流相关、WR相关、RAW相关等。127(2)读写相关：指令k+1与指令k+2之间关于F1的相关，变量名相关、先读后

写相关、反相关、RW相关、WAR相关等。(3)写写相关：指令k与指令k+2左边的F1之间的相关关系称为：输出相关、写写相关、WW相关、WAW相关或写后再写相关等。有时把相关称为“冒险”(hazard)、“竟争”(co

mpetition)等。在程序执行过程中，只有避免相关，执行结果才是正确的。乱序流动中的数据相关（续）128乱序流动中的数据相关（续）测试先写后读数据相关的方法：在流水线的读书操作功能段设置一个相联比较器，在指令读操作数之前，把源操作数地址和已经在流水线中的

从读数功能段到写结果功能段之间的所有指令的目标地址进行比较，发现地址相等，则表明发生了先写后读相关。测试先读后写，写写相关的方法：在流水线的写功能段设置相联比较器，把自己的目标操作数地址分别与已经进入流水线的指令序号比自己小的源操作数地址和目标操作

数地址进行比较。发现源操作数地址相等，发生先读后写相关，发现目标操作数地址相等，发生了写写相关。129乱序流动中的数据相关（续）三种数据相关可以用下列关系式来表示：对于写读相关D(i)∩S(j)≠对

于读写相关S(i)∩D(j)≠对于写写相关D(i)∩D(j)≠(写)(写)(读)(写)(a)写读相关(b)写写相关(读)(写)i先于j。(c)读写相关S(i)S(i)S(i)D(i)D(i)D(i)S

(j)S(j)S(j)D(j)D(j)D(j)130乱序流动中的数据相关（续）在流水线中避免数据相关的方法分为两类：延迟执行。优点是流水线的控制简单，缺点是流水线的吞吐率和效率很低。建立专用路径。分散控制的公共数据总线法。集中控制的CDC记

分牌法。流水线的吞吐率和效率有比较大的提高。在流水线中建立专用数据路径是高性能处理机的通用方式。131数据重定向方法1.三种数据相关的重定向重定向之前，j只能在i之后执行。重定向之后，可以做到：(1)写读相关，j与i可以同时执行。即专用数据通路。(2)写写相关，先后顺序无关。(3)读写相关

，先后顺序无关。后两种情况又称为“变量换名技术”132数据重定向方法（续）BBijiACAjC(a)写读相关的数据重定向BBB’ijijACAC(b)写写相关的数据重定向BBijjACAjCiB’(c)读写相关的数据重

定向1332.变量换名技术用来自动消除读写数据相关和写写数据相关。规则：一个变量只允许定值一次。在三种数据相关中，实际上只有写读数据相关必须依靠硬件、或采用软硬件结合的方法来解决。解决方法：推后处理或专用数

据通路。在上面的数据重定向图中，把B换成了B’，并在以后的都引用B’读写数据相关和写写数据相关就不存在了。数据重定向方法（续）134数据重定向方法（续）一个实际例子：Loop:LDF0,0(R1)ADDF0,F2SD0(R1),F0LDF0,-8(R1)ADDF0,F2

SD-8(R1),F0LDF0,-16(R1)ADDF0,F2SD-16(R1),F0LDF0,-24(R1)ADDF0,F2SD-24(R1),F0SUBIR1,R1,#32BNEZR1,LoopLoop:LDF0,0(R

1)LDF4,-8(R1)LDF6,-16(R1)LDF8,-24(R1)ADDF0，F2ADDF4，F2ADDF6，F2ADDF8，F2SD0(R1),F0SD-8(R1),F4SUBIR1,R1,#32SD-16(R1),F6BNEZR1,Lo

opSD-24(R1),F8135数据重定向方法（续）3.一个简单的程序：k：LOADF1,Ak+1：FADDF1,F2k+2：FMULF1,F3k+3：STOREF1,BAk+1FADDk+1F2kk+1F1k+3k+2Bk+2FMULk

+2F3136AK，k+1FADDk+1F2F1k+1k+2k+2Bk+2,k+3FMULk+2F3专门设置：A→FADD、FMUL→B、FADD→FMUL三条专用路径。撤消：F1→FADD、F1→FMUL、FADD→F1、A→F1的路径。数据重定向方法（续）1

37Tomasulo动态调度算法实用的动态调度算法主要有两种:(1)集中控制：CDC计分牌(scorebord)算法.最先在CDC6600大型机中采用。(2)分散控制：Tomasulo算法,公共数据总线法，令牌法等。最早

在大型机IBM360/91的浮点处理部件中被采用。以上面的一段程序为例说明Tomasulo算法k：LOADF1,Ak+1：FADDF1,F2k+2：FMULF1,F3k+3：STOREF1,B138Tomasulo动态调度算法（续）存储器总线指令分析部件CDB6先行读数站控制先行操

作站F7忙位站号通用寄存器5(FLB)(FLOS)F6(FLR)4F53F42F3FLB1F2F1110/8控制站号后行写数站F0译码器A312站号源1站号源2控制M29站号源1站号源2控制A211M1810(F3)A110(F

LB1)(F2)乘/除法器加法器（6级流水线）(2级流水线)CDBIBM360/91处理机的浮点执行部件控制总线FLB总线FLR总线CDB139全局相关由条件转移或程序中断引起的相关称为全局相关，在流水线中全局相关对流水线的吞

吐率和效率的影响相对于局部相关要大得多。条件转移指令和中断指令与后续指令存在一种相关。使他们不能同时进入流水线中执行。140全局相关（续）处理好条件转移和中断的关键问题有两个：要确保流水线能够正常工作减少因“断流”引起的吞吐率和效率的下降1.条件分支的处理方法条件转移指令对流水线的影响很大，必

须采取措施来减少这种影响。可能的措施有：(1)延迟转移技术和指令取消技术只能用于单流水线处理机中，且流水线的级数不能太多；141据统计，编译器调度一条指令成功的概率在90％以上，而调度两条指令成功的概率只有40％左右。当没有合适的指令可调度时，编

译器只能插入空操作。(2)动态分支预测技术根据近期转移是否成功的记录来预测下一次转移的方向。所有的动态转移预测方法都能够随程序的执行过程动态地改变转移的预测方向。全局相关（续）142(3)静态分支预测技术转移预测的方向是确定的，或者预测转移不成

功，或者预测转移成功，在程序实际执行过程中，转移预测的方向不能改变。静态转移预测可以只用软件实现，也可用硬件来实现，还可以在转移的两个方向上都预取指令。TI公司的SuperSPARC处理机采用了静态转移预测技术，而且设置有转移目标缓冲栈，在两个方向上

都预取指令。（4）提前形成条件码全局相关（续）1432.条件分支在流水线中的执行过程因为第i条指令所需要的条件码由第i-1条指令给出；在一条由k个功能段的流水线中，第i-1条指令要等到第i+k-2条指令进入流水线时才能形成条件码。转移不成功，猜测正确，流水线的

吞吐率和效率没有降低，转移成功，猜测错误，要先作废流水线中已经执行的i+1、i+2、……、i+k-2指令；然后再从分支点开始执行第P、p+1、……指令。一条k段流水线有k-2个功能段是浪费的。全局相关（续）144全局相关（续）条件分支指令在流水线中的执行过程时间ti+1i+2„i+k-3

i+k-2输出输入i-1ipp+1„p+k-4p+k-3输出形成条件码的指令条件转移指令形成转移条件转移不成功转移成功145当分支的执行方向猜测错误时，可能造成程序执行结果发生错误。例如，若第i+1条指令是：(R1＋(R2)→R1，寄存器R1中内容就被破坏，整个程序执行的结果是错误的。目前的处理

机有两种做法：一种方法是只进行指令译码和准备好运算所需要的操作数，在转移条件没有形成之前不执行运算。另一种方法是一直执行到运算完成，但不送回运算结果。全局相关（续）1463.条件分支对流水线性能的影响假设条件转移指令在一般程序中所占的比例为p，转移成功的概率为q。n条指令的总的执行时间

是：TK-IF＝(n+k-1)t+npq(k-1)t有条件转移影响的流水线吞吐率为：有条件转移影响的流水线最大吞吐率为：TPnnktnpqktIF（11)()tkpq))1(11TPIFMAX（

条件分支对流水线的影响（续）147流水线吞吐率下降的百分比为：在典型程序中，转移指令占的比例为p＝20％，转移成功的概率为ｑ＝60％。对于一条8功能段的指令流水线，由于条件转移指令的影响，流水线的最大吞吐率要下降：如果指令流水线的功能段数为10，

由于条件转移指令的影响，流水线的最大吞吐率将下降一半以下：)1(1)1(kpqkpqTPTPTPDMAXIFMAXMAX%46)18(60.020.01)18(60.020.08D%53)110(60.020.01)110(60.020.0D10

条件分支对流水线的影响（续）148动态分支预测技术动态转移预测技术的两个关键问题：如何记录转移历史信息如何根据记录的转移历史信息预测转移方向记录转移历史信息的方法有三种：①最近一次或几次转移是否成功的信息记录在转移指令中②用一个高速缓冲栈保存条件转移指

令的转移目标地址③用Cache保存转移目标地址之后的n条指令1491.在指令Cache中记录转移历史信息在指令Cache中专门设置一个字段，称为“转移历史表”。在执行转移指令时，把转移成功或不成功的信息记录在这个表中。

当下次再执行到这条指令时，转移预测逻辑根据“转移历史表”中记录的信息预测转移成功或不成功。动态分支预测技术(续)1501.只记录最近一次转移是否成功的历史信息2.如果“转移历史表”中记录的内容是“T”，则预测转移成功，如果记录的

是“N”，则按照转移不成功的方向继续取指令。3.并用实际转移是否成功的信息来修改“转移历史表”。TTT：转移成功，N：转移不成功NNTN动态分支预测技术(续)151记录最近两次转移是否成功的历史信息图

中采用偏向成功的预测策略：只有历史上最近两次执行这条转移指令时转移都没有成功，本次才预测转移不成功。也可以采用其他预测策略TT：最近两次转移都成功NT：最近一次转移成功，前一次转移不成功TN：最近一次转移不成功，前一次转移成功NN：最近两次转移都不成功t：本次预测转移成功n：本次预测转移不成功

T：本次实际转移成功N：本次实际转移不成功TTtTNtNTtNNnTNNTTTNN动态分支预测技术(续)152“转移历史表”的修改规则和转移预测规则可以有多种多样，记录转移预测是否成功的信息。用最近预测是否成功的信息作

为是否转移的依据当“转移历史表”是空白时，可以有两种做法：在“转移历史表”中预置转移历史信息。根据指令本身的偏移字段的符号来预测转移的方向如果偏移字段为负，则预测转移成功，否则预测转移不成功动态分支预测技术(续)153主要优点：不必专门设置转移缓冲栈，所记录的转移历史信息比较少。例

如：DEC公司的Alpha21064处理机就采用了这种转移预测方法，在它的一级指令Cache中有一个专门的“转移历史表”字段。动态分支预测技术(续)154动态分支预测技术(续)Alpha21064的结构

框图：指令Cache（8KB）转移历史表区号指令地址总线EBOXIBOXFBOX34位乘法器预取器乘法器/加法器资源冲突检测加法器移位器PC计算数据总线逻辑单元指令快表除法器128位流水线控制定点寄存器堆（32×64）浮点寄存器堆（32×64）ABOX总线接口部外部Cache写数

缓冲器地址发生器数据快表读数缓冲器控制件数据Cache（8KB）区号数据Alpha21064处理机结构除法器1552.设置转移目标地址缓冲栈用高速缓冲栈保存最近k条转移指令的“转移历史表”和转移目标地址当前指令地址与转移目标缓冲栈中的所有转移指令地址进行比较；如果发现有相等

的，则根据所记录的历史信息预测本次转移方向。根据某种规则修改“转移历史表”。I0T0P0I1T1P1:::::::::Ik-1Tk-1Pk-1转移指令地址转移历史表转移目标地址动态分支预测技术(续)156A0T0I0,0I0,1„„I0,n-1A1T1I1,0I1,1„„I1,n-1

A2T2I2,0I2,1„„I2,n-1:::::::::Ak-1Tk-1Ik-1,0Ik-1,1„„Ik-1,n-1转移指令地址转移历史表转移目标地址之后的n条指令3.设置转移目标指令缓冲栈把上面方法中的“转移目标地址”字段改为存放转移目标地址之后的

n条指令。预测转移方向的规则和修改“转移历史表”的规则与上面的方法相同。动态分支预测技术(续)157提前形成条件码必要性：对提高流水线的性能非常有效。可能性：可在运算开始或中间产生条件码。1.对于乘除法，两个源操作数的符号相同结果为正，符号相反结果为负。2

.对于乘法，有一个操作数为0，则乘积为0。3.被除数为0，商为0；除数为0，除法结果溢出。4.同号加或异号减，结果符号与第一操作数相同。5.异号加或同号减，结果的符号与绝对值大的操作数相同。6.溢出及是否为0可以通过一个比较器提前产生。158只要在一个时钟周期之内产生条件码，

流水线就不会“断流”。如Amdahl470V/6在运算部件的入口处设置药有一个LOCK部件，提前形成条件码。把产生条件码与使用条件码的指令分开LOADR1,NUM;循环次数初值装入R1LOOP：……;循体开

始……DECR1;循环次数减“1”BNELOOP;测试循环是否则结束HALT;程序结束NUM:n提前形成条件码（续）159可以编译成如下程序：LOADR1,NUM;循环次数装入R1中LOOP：LDECR1;一条专用的;循环次数减1指令……;循体开始……LBNELOOP;一条专用的测试循环;是

否结束的指令HALT;程序结束NUM:n;循环次数指令LDEC和LBNE使用专用的条件码寄存器CCL。CCL由LDEC设置，由LBNE使用，循环体中间的其他指令不破坏CCL。提前形成条件码（续）160精确断点与不精确断

点对于输入输出设备的中断服务，实际上不需要有精确断点。比较简单的处理方法是：让已经进入流水线的所有指令都执行完成，断点就是最后进入流水线的那条指令的地址。对于程序性错误和机器故障等引起的中断，它们出现的概率很低，处理原则：不在于缩短时间，关键是要正确保存现场和正确恢复断点。161不精确断点

(Imprecise)，流水线可以不断流需要的硬件比较少，控制逻辑比较简单。中断响应时间加长。采用不精确断点法可能会发生如下两个问题：(1)程序的调试困难早期的流水线处理机，多采用不精确断点法。近期的流水线处理机一

般都采用精确断点法。申请中断输入S1S2S3S4S5S6S7S8输出PC：i+5i+4i+3i+2i+1ii-1i-2不精确断点精确断点精确断点与不精确断点（续）162(2)程序执行的结果可能出错，例如：i：FADDR1,R2；(R1)＋(R

2)→R1i+1：FMULR3,R1；(R3)×(R1)→R3当第i条指令执行到S6段时发现浮点加法结果溢出，于是发出中断服务申请。由于采用不精确断点法，已经进入流水线的第i+1条指令将执行完成；因为第i+1条

指令使用了不正确的R1，所以浮点乘法的执行结果是不正确的。采用精确断(Precise)点法，要设置一定数量的后援寄存器，把整个流水线中所有指令的执行结果和现场都保存下来。精确断点与不精确断点（续）1635.3超标量处理机5.3.1基本结构5.3.2单发射与多发射5.3.3多流

水线调度5.3.4资源冲突5.3.5超标量处理机性能164三种主流处理机：超标量处理机超流水线处理机超标量超流水线处理机以一台k段流水线的普通标量处理机为基准超标量处理机、超流水线处理机和超标量超流水线处理机的主要性能：机器类型k

段流水线标量处理机m度超标量处理机n度超流水线处理机(m,n)度超标量超流水线处理机机器流水线周期1个时钟周期11／n1／n同时发射指令条数1条m1m指令发射等待时间1个时钟周期11／n1／n指令级并行度ILP1mnm×n超

标量处理机（续）165基本结构普通标量流水线处理机：一条指令流水线，一个多功能操作部件，每个时钟周期平均执行指令的条数小于1。多操作部件标量处理机：一条指令流水线，多个独立的操作部件，指令级并行度小于1。超标量处理机典型结构：多条并行工作的指令流水线，多个独立

的操作部件，指令级并行度（ILP）大于1。166基本结构（续）整数部件整数部件位操作部件浮点加部件乘法部件除法部件图形部件图形部件内部总线读数／存数部件通用寄存器堆扩展寄存器堆目标指令Cache指令分配／转移部件数据Cache（8KB）

指令Cache（8KB）32位地址总线64位数据总线系统总线超标量处理机MC88110的结构167Motorola公司的MC88110有10个操作部件。两个寄存器堆：整数部件通用寄存器堆，32个32位寄存器。浮点部件扩展寄存器堆，32个80位寄存器。缓冲

深度为4的先行读数栈。缓冲深度为3的后行写数栈。两个独立的高速Cache中，各为8KB，采用两路组相联方式。转移目标指令Cache，用于存放另一条分支上的指令。基本结构（续）168单发射与多发射1.单发射处理机：每个周期只

取一条指令、只译码一条指令，只执行一条指令，只写回一个运算结果。取指令部件和指令译码部件各设置一套；只设置一个多功能操作部件或设置多个独立的操作部件；操作部件中可以采用流水线结构，也可以不采用流水线结构。目标是每个时钟周期平均执行一条指令，ILP的期望值为1。16

92.多发射处理机：每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时写回多个运算结果。多个取指令部件，多个指令译码部件和多个写结果部件。设置多个指令执行部件，有些指令执行部件采用流水线结构。目标是每

个时钟周期平均执行多条指令，ILP的期望值大于1。单发射与多发射（续）170单发射与多发射（续）单发射处理机的指令流水线时空图123456I1IFIDEXWR时钟周期I2IFIDEXWRI3IFIDEXWR指令多发射处理机的指令流水线时空图1234

56I1IFIDEXWR时钟周期I2IFIDEXWRI3IFIDEXWRI4IFIDEXWRI5IFIDEXWRI6IFIDEXWRI7IFIDEXWRI8IFIDEXWRI9IFIDEXWR指令171单发射处理机的指令流水线取指令指令译码执行指令EX写回结果FA

1FA2FA3浮点加法部件来自指令CacheIFIDMD1MD2MD3WR通用寄存器后行写数栈乘除法部件AL定点算术逻辑部件LS取数存数部件单发射与多发射（续）172同时发射两条指令的多发射处理机的指令流水线取指令指令译码执行指令写回结果FA1FA2FA3浮

点加法部件来自指令CacheIF1ID1MD1MD2MD3WR1通用寄存器后行写数栈乘除法部件来自指令CacheIF2ID2ALWR2通用寄存器后行写数栈定点算术逻辑部件LS取数存数部件单发射与多发射（

续）1733.超标量处理机：有两条或两条以上能同时工作的指令流水线先行指令窗口：能够从指令Cache中预取多条指令，能够对窗口内的指令进行数据相关性分析和功能部件冲突检测。例如：Intel公司的i860、i960、Pentium，Motolora公司的MC88110，IBM公司的Power6

000,TI公司生产SuperSPARC等操作部件的个数一般多于每个周期发射的指令条数。通常为4个至16个操作部件。超标量处理机的指令级并行度：1＜ILP＜m单发射与多发射（续）174单发射与多发射（续）先行指令窗口类似先行指令控制技术中的先行指令缓冲栈。可以读

更多的指令，通过硬件判断哪些指令可以先发射到操作部件中去执行。没有功能部件冲突、没有数据相关、控制相关的指令可以超越前边指令先行执行。结合编译器的支持，可以把多条不相关指令调度到先行窗口。先行窗口太小，调度效果不好。先行窗口太大，硬件又太复杂。一般为2-8条指令。175有

先行指令窗口的超标量处理机的流水线结构取指令指令译码执行指令写回结果FA1FA2FA3浮点加法部件指令CacheIF1ID1MD1MD2MD3WR1通用寄存器后行写数栈乘除法部件指令CacheIF2ID2ALWR2通用寄存器后行写数栈定点算术逻辑部件IF3ID3LS先行指令窗口取数存数部件

FA：浮点加减法运算，MD：乘除法运算，AL：定点算术逻辑运算，LS取数存数单发射与多发射（续）176多流水线调度顺序发射(in-orderissue)与乱序发射(out-orderissue)：指令发射顺序是按照程序中指令排列顺序进行的称为顺序发射顺序完

成(in-ordercompletion)与乱序完成(out-ordercompletion)：指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成多流水线的调度主要有三种方法：顺序发射顺序完成。顺序发射乱序完成。乱序发射乱序完成。177以如下6条指令组成的程序为例，说明这三种调

度方法I1：LOADR1,A；R1←(A)I2：FADDR2,R1；R2←(R2)＋(R1)I3：FMULR3,R4；R3←(R3)×(R4)I4：FADDR4,R5；R4←(R4)＋(R5)I5：DECR6；R6←(R6)－1I6：FMULR6,R7；R6←(R6

)＋(R7)6条指令中有4个数据相关，包括2个写读相关，1个读写相关和1个写写相关。多流水线调度（续）178多流水线调度（续）1.顺序发射顺序完成共用10个时钟周期完成还有8个空闲的时钟周期，其中5个周期纯粹为维持顺序

才插入。顺序发射顺序完成的指令流水线时空图12345678910I1IF1ID1LSWR1时钟周期I2IF2ID2FA1FA2FA2WR2I3IF1ID1MD1MD2MD3WR1I4IF2ID2FA1FA2FA3WR2I5IF1ID1ALWR1I6IF2ID2MD1MD2MD3W

R2指令IF：取指令，ID：指令译码，LS取数存数，FA：浮点加减法运算，MD：乘除法运算，AL：定点算术逻辑运算WR：写回运算结果179多流水线调度（续）2.顺序发射乱序完成总的执行时间为9个时钟周期，节省了一个时钟周期。少了5个空闲时钟周期。顺序发射乱序完成的流水

线时空图123456789I1IF1ID1LSWR1时钟周期I2IF2ID2FA1FA2FA2WR2I3IF1ID1MD1MD2MD3WR1I4IF2ID2FA1FA2FA3WR2I5IF1ID1ALWR1I6IF2ID2MD1MD2MD3WR2指令顺序发射乱序完成的指令完成次序时钟周期

456789流水线1I1I5I3流水线2I2I4I6180多流水线调度（续）3.乱序发射乱序完成（采用先行指令窗口）没有空闲周期，功能部件得到充分利用。总的执行时间为8个周期，节省2个周期。乱序发射乱序完成调度方法的流水线时空图12345678流水线1I1IF1ID1LSW

R1时钟周期流水线2I3IF2ID2MD1MD2MD3WR2先行窗口I4IF3ID3FA1FA2FA3WR1I2IF1ID1FA1FA2FA3WR1I5IF2ID2ALWR2I6IF1ID1MD1MD2MD3WR1指令指令在流水线中的发射次序指令在流水线中的完成次序时钟周期123时钟周期45

678流水线1I1I2I6流水线1I1I4I2I6流水线2I3I5流水线2I5I3先行窗口I4181资源冲突如果操作部件采用流水线结构，发生资源冲突的可能性很小。如果不采用流水线结构，发生资源冲突的可能性就

比较大。下面是一个由4条指令的程序例子：I1：FADDR0,R1；R0←(R0)＋(R1)I2：FMULR2,R3；R2←(R2)×(R3)I3：FADDR4,R5；R4←(R4)＋(R5)I4：FMULR6,R7；R6←(R6)＋(R7)182资源冲突（续）操作部件不采用流

水线：做完4条指令总共用了11个周期，有5个空闲周期。双流水线超标量处理机，操作部件不采用流水线的时空图1234567891011流水线1I1IF1ID1FADDWR1时钟周期流水线2I2IF2ID2FMULWR2流水线1I3IF1ID1FADDWR1流水线2I4IF2ID2

FMULWR2指令IF：取指令，ID：指令译码，FADD：浮点加法，FMUL：浮点乘法，WR：写回结果183操作部件采用流水线：做完4条指令共用8个周期，少用3个周期。浮点乘双流水线超标量处理机，操作部件采用流水线的时空图12345678

流水线1I1IF1ID1FADD1FADD2FADD3WR1时钟周期流水线2I2IF2ID2FMUL1FMUL2FMUL3FMUL4WR2流水线1I3IF1ID1FADD1FADD2FADD3WR1流水线2I4IF2ID2FMUL1FMUL2FMUL3FMUL4WR2指

令IF：取指令，ID：指令译码，FADD：浮点加法，FMUL：法，WR：写回结果资源冲突（续）184操作部件采用流水线结构的原因分析假每个周期发射m条指令，操作部件的延迟时间为k个周期，如果操作部件不采用流水线结构，则使用同一个操作部件的

两条指令应该至少相差m×k如果操作部件采用k段流水线结构，则使用同一个操作部件的两条指令只需相差m或m以上指令流水线的段数k一般在4至10之间，每个时钟周期发射的指令条数m在2至4之间。取中间值，k＝7，m＝3。资源冲突（续）185为了不发生资源冲突，如果操作部件不采

用流水线结构，两条使用同一个功能部件的指令序号必须相差21或21以上。如果操作部件采用流水线结构，两条使用同一个功能部件的指令序号只需要相差3或3以上。因此，在超标量处理机中，操作部件一般要采用流水线结构。如果由于某种原因，操作部件不能采用流水线结构，则必须设置多个相同种类

的操作部件资源冲突（续）186普通标量处理机，希望相同操作连续出现。只有连续出现相同操作的指令序列时，流水线的效率才能得到充分发挥。超标量处理机则正好相反，希望相同操作不要连续出现。相同操作的指令序列连续出现时，会发生资源冲突；要求相同操作的指令能

够相对均匀地分布在程序中。超标量处理机的这种要求正好符合一般标量程序的特点。资源冲突（续）187超标量处理机性能单流水线普通标量处理机的指令级并行度记作(1,1)，超标量处理机的指令级并行度记作(m,1)，超流水线处理机的指令级并行度记作(1,n)，而超标量超流水线处理

机的指令级并行度记作(m,n)。在理想情况下，N条指令在单流水线标量处理机上的执行时间为：T(1,1)＝(k＋N－1)t188在每个周期发射m条指令的超标量处理机上执行的时间为：第一项为第一批m条指令同时通过

m条指令流水线所需要的时间，第二项是剩余N-m条指令所需要的时间。超标量处理机相对于单流水线标量处理机的加速比为：超标量处理机的加速比的最大值为：S(m,1)MAX＝mtmmNkmT)()1,()1()1()1,()1,1()1,(

kmNNkmmTTmS超标量处理机性能（续）189超流水线处理机1指令执行时序2典型处理机结构3超流水线处理机性能190超流水线处理机的两种定义：在一个周期内分时发射多条指令的处理机。指令流水线的段

数大于等于8的流水线处理机。提高处理机性能的两种方法：通过增加硬件资源来提高处理机性能——超标量处理机。通过各部分硬件的重叠工作来提高处理机性能——超流水线处理机。两种不同并行性：超标量处理机采用的是空间并行性。超流水线处理机采用的是时间并行性。超流水线处

理机（续）191指令执行时序每隔1/n个时钟周期发射一条指令，即处理机的流水线周期为1/n个时钟周期。每个时钟周期分时发射3条指令的超流水线处理机的指令执行时空图123456I1IFIDEXWR时钟周期I2IFIDEXWR

I3IFIDEXWRI4IFIDEXWRI5IFIDEXWRI6IFIDEXWRI7IFIDEXWRI8IFIDEXWR指令I9IFIDEXWR192典型处理机结构MIPSR4000处理机：每个时钟周期包含两个流水段是一种很标准的超流水线处理机结构。指令流

水线有8个流水段。指令Cache和数据Cache的容量各8KB，每个时钟周期可以访问Cache两次，在一个时钟周期内可以从指令Cache中读出两条指令，从数据Cache中读出或写入两个数据。主要运算部件有整数部件和浮点部件。1

93典型处理机结构（续）译码数据Cache标志标志指令Cache译码存入缓冲／对准器IBUS写入缓冲器数据标志地址DBUS系统控制浮点存储管理部件寄存器堆指令快表浮点流水线专用通路指令Cache控制快表TLB浮点控制寄存器DVAIVA浮点乘法部件地址部件浮点除法部件数据Cache控制程序计数器

浮点加法部件流水线通用寄存器堆转换部件控制算术逻辑部件ALU求平方根部件装入对准器/存入驱动器整数乘法／除法部件MIPSR4000超流水线处理机结构194MIPSR4000处理机的流水线操作IFISRFEXDFDSTCWB指令指令译码Cache数据寄存读寄存器堆ALUCache标志检

验器堆IF：取第一条指令；IS：取第二条指令；RF：读寄存器堆，指令译码；EX：执行指令；DF：取第一个数据；DS：取第二个数据；TC：数据标志检验；WB：写回结果典型处理机结构（续）195典型处理机结构（续）MIPSR4000正常指令流水线工作时序主时钟周期当

前CPU周期IFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRF

EXDFDSTCWBIFISRFEXDFDSTCWBIF：取第一条指令；IS：取第二条指令；RF：读寄存器堆，指令译码；EX：执行指令；DF：取第一个数据；DS：取第二个数据；TC：数据标志检验；WB：写回结果流水线周期196如果在LOAD指令之后的两条指令中，任何一

条指令要在它的EX流水级使用这个数据，则指令流水线要暂停一个时钟周期。指令运行暂停暂停运行运行运行运行运行运行运行运行I1DFDSTCWBLOAD指令I2EXDFDSTCWB使用LOAD数据I3RFEXDFDSTCWBI4ISRFEXDFDSTCWBI5IFISRFEXDFDSTCWBI6

IFISRFEXDFDSTCWB典型处理机结构（续）197超流水线处理机性能指令级并行度为(1,n)的超流水线处理机，执行N条指令所的时间为：超流水线处理机相对于单流水线普通标量处理机的加速比为：加速比的最大值为：S(1,n)MAX＝n

TnkntN(,)()111)1()1()1(),1()1,1(),1(NnkNkntnNktNknTTnSＫ是指令流水线的功能段数或时钟周期数。198超标量超流水线处理机超标量处理机设置

多套指令执行部件，同时发射多条指令。超流水线处理机把一个时钟周期细分为多个流水线周期，每个流水线周期发送一条指令，一个周期发生多条指令。超标量处理机需要更多数量的硬件晶体管，超流水线处理机需要更快速度的晶体管和更精确的电路设计。结合起来就是超标量超流水线处理机，一个时钟周期发射m次，每次发射

n条指令。①指令执行时序。②典型处理机结构。③超标量超流水线处理机性能。④三种处理机的性能比较。199每个时钟周期发射3次，每次同时发射3条指令的超标量超流水线处理机的指令执行时空图123456I1IFIDEXWR时钟周

期I2IFIDEXWRI3IFIDEXWRI4IFIDEXWRI5IFIDEXWRI6IFIDEXWRI7IFIDEXWRI8IFIDEXWRI9IFIDEXWRI10IFIDEXWRI11IFIDEXWRI12IFIDEXWR指令IF：取指令，ID：指令译码，EX：执

行指令，WR：写回结果指令执行时序200典型处理机结构DEC公司的Alpha处理机为典型的超标量超流水线结构。主要由四个功能部件和两个Cache组成：整数部件EBOX浮点部件FBOX地址部件ABOX中央控制部件IBOX指令Cache和数据Cache在EBOX内还有多

条专用数据通路，可以把运算结果直接送到执行部件。201中央控制部件IBOX能够同时完成：同时读出两条指令；同时对两条指令进行译码，并作相关性检测；如果资源和相关性允许，IBOX就把两条指令同时发射给EBO

X、ABOX和FBOX三个执行部件中的两个。指令流水线的控制方式：采用顺序发射乱序完成。在指令Cache中有一个转移历史表，实现条件转移的动态预测。典型处理机结构（续）202指令Cache（8KB）转移历史表区号指令地址总线EB

OXIBOXFBOX34位乘法器预取器乘法器/加法器资源冲突检测加法器移位器PC计算数据总线逻辑单元指令快表除法器128位流水线控制定点寄存器堆（32×64）浮点寄存器堆（32×64）ABOX总线接口部外部Cache写数缓冲器

地址发生器数据快表读数缓冲器控制件数据Cache（8KB）区号数据Alpha21064处理机结构除法器典型处理机结构（续）203Alpha21064处理机共有三条指令流水线：(1)整数操作流水线为7个流水段，其中，取指令2个流水段、分析指令2个流水段、运算2个流水

段、写结果1个流水段。(2)访问存储器流水线为7个流水段。(3)浮点操作流水线分为10个流水段，其中，浮点执行部件FBOX的延迟时间为6个流水段。三条指令流水线的平均段数为(7+7+10)/3=8，且每个时钟周期发射两

条指令。因此，Alpha21064处理机为超标量超流水线处理机。典型处理机结构（续）2047个流水段的整数操作流水线(0)(1)(2)(3)(4)(5)(6)IFSWAPI0I1A1A2WRIF：取指令；SWAP：交换双发射指令，转移预测；I0：指令

译码；I1访问通用寄存器堆，发射校验；A1：计算周期1，IBOX计算新的PC值；A2：计算周期2，查指令快表；WR：写整数寄存器堆，指令Cache命中检测。7个流水段的访问存储器流水线(0)(1)(2)(3

)(4)(5)(6)IFSWAPI0I1ACTBHMAC：ABOX计算有效数据地址；TB：查数据快表；HM：写读数缓冲栈，数据Cache命中/不命中检测。10个流水段的浮点操作流水线(0)(1)(2)(3)(4)(5)(6)(7)(8)(

9)IFSWAPI0I1F1F2F3F4F5FWRF1－F5：浮点计算流水线；FWR：写回浮点寄存器堆。典型处理机结构（续）205超标量超流水线处理机的性能指令级并行度为(m,n)的超标量超流水线处理机，连续执

行N条指令所需要的时间为：超标量超流水线处理机相对于单流水线标量处理机的加速比为：在理想情况下，超标量超流水线处理机加速比的最大值为：S(m,n)MAX＝m×nTmnkNmmnt(,)()m

NmnkNkmntmnmNktNknmSSnmS)1()()1(),()1,1(),(206三种标量处理机的性能比较1.相2.5对性2.0能1.51.00.50.012345678指令级并行度超流水线处理机超标量处理机超标量超流水线处理

机２．相对单流水处理机的加速比３．实际能够达到的指令并行度207从三种标量处理机的性能曲线中，可以得出如下结论：1.三种处理机的性能关系超标量处理机的相对性能最高，其次是超标量超流水线处理机，超流水线处理机的相对性能最低，主要原因如下：(1)超标量处理机功能部件

的冲突比超流水线处理机小。在指令执行过程中的许多功能段，超标量处理机都重复设置有多个相同的指令执行部件，而超流水线处理机只是把同一个指令执行部件分解为多个流水级。三种标量处理机的性能比较（续）208(2)条件转移等操作造成的损失，超流水

线处理机要比超标量处理机大。由于超流水线处理机采用深度流水线结构，对条件转移等操作比超标量处理机敏感。(3)超流水线处理机的启动延迟通常要比超标量处理机大。超标量处理机在每个时钟周期的一开始就同时发射多条指令。

超流水线处理机把一个时钟周期平均分成多个流水线周期，每个流水线周期只发射一条指令。三种标量处理机的性能比较（续）209三种标量处理机的性能比较（续）2.实际指令级并行度与理论指令级并行度的关系当横坐标给出的理论指令级并行度比较低时，处理机的

实际指令级并行度的提高比较快。当理论指令级并行度进一步增加时，处理机实际指令级并行度提高的速度越来越慢。在实际设计超标量、超流水线、超标量超流水线处理机的指令级并行度时要适当，否则，有可能造成花费了大量的硬件，但实际上处理机所能达

到的指令级并行度并不高。目前，一般认为，m和n都不要超过4。210三种标量处理机的性能比较（续）3.一个特定程序由于受到本身数据相关和控制相关的限制，它的指令级并行度的最大值是确定的。这个最大值由程序自身的语义决定，与该程序在那种机器上执行无关

。对某一种程序，三条曲线收拢到一点，点的位置随程序变化而变化。能够达到的指令并行级还和所采用的调度算法相关。实现最优调度算法很困难。211P问题、NP问题与NPC问题1、P问题P是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出

。如果一个判定性问题的复杂度是该问题的一个实例规模n的多项式函数，这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。NP是一个判定问题类，这些问题可以

用一个确定算法在多项式时间内检查或验证出它们的解，P事实上很直观，我们通常在编程中求解的问题大多都是P类问题。比如说排序，找最短路径等。212P问题、NP问题与NPC问题2、NP问题然而有些问题很难找

到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是发现如果给了该问题的一个答案，就可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，很容易判断是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）

。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP？这个问题至今还未解决。NP这个类并不要求给出一个算法来求解问题本身，而只是要求给出

一个确定性算法在多项式时间内验证它的解。213P问题、NP问题与NPC问题3、NP完全问题NP问题不一定都是难解的问题。比如，简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信P<>NP

，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。NP完全问题是求NP中判定问题的一个子类。NPC问题存在着一个特殊性质，即如果一个NPC问题存在多项式时间的算法，

则所有的NP问题都可以在多项式时间内求解，即P=NP成立。这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久，cook在

1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法。类似哈米尔顿回路/路径问题，货郎担问题，集团问题，最小边覆盖问题等等很多问题都是NPC问题。21

4P问题、NP问题与NPC问题4、NP困难与NP完全问题证明多项式时间归约：设A和B是两个判定问题。如果存在一个确定性算法C，它的行为如下：当给C展示问题A的一个实例时，算法A可以把这个实例变换成问题

B的一个实例，使得A的实例跟B的实例有相同的YES/NO应答，并且这个变换在多项式时间内完成。那么说A多项式时间归约到B。事实上，可以将多项式时间归约看做是一个函数的映射，即F(A)=B。并且这个F是多项式时间内

可计算的。也就是说问题A实现上可以通过它自身满足的条件，通过一些形式上的改变而变换到问题B。215P问题、NP问题与NPC问题NP困难与NP完全：如果对于NP中的每个问题B，B多项式时间归约到A，判定问题A称为NP是困难的。如

果对于NP中的每个问题B，B多项式时间归约到A，并且A在NP类中，判定问题A称为是NP完全的。NP完全问题的证明：要证明一个判定问题是NP完全，只要在NP完全类中找到一个问题A，将这个问题归约到待证明问题即可。

要证明问题是NP完全很困难，因为很多问题之间的转化过程很难想得到。第一个被证明的NP完全问题是可满足性问题，它是判定一个合取范式的布尔公式F是否存在真值指派的问题。在很多NP完全问题的证明中，都可以用这个问题来归约。2161.线性流水线的性能分析及计算2

.非线性流水线的调度方法3.数据相关的种类，发生的情况及解决的办法4.分支预测技术5.乱序流动方式中的数据相关及解决办法6.单发射、多发射与先行指令窗口7.超标量、超流水线处理机的结构及性能分析本章重点：