第一章 基本概念第二章 指令系统第三章 存储系统第四章 输入输出系统第五章 标量处理机第六章 向量处理机第七章 互连网络第八章 并行处理机第九章 多处理机 标量处理机•具有标量数据表示和标量指令系统的处理机称为具有标量数据表示和标量指令系统的处理机称为标量处理机标量处理机•提高指令执行速度的主要途径提高指令执行速度的主要途径–提高处理机的工作主频提高处理机的工作主频–采用更好的算法和设计更好的功能部件采用更好的算法和设计更好的功能部件–采用指令级并行技术采用指令级并行技术 •三种指令级并行处理机三种指令级并行处理机–流水线（流水线（pipelining ）处理机超流水线（）处理机超流水线（Superpipelining ）处理机）处理机–超标量（超标量（Superscalar）处理机）处理机–超长指令字超长指令字(VLIW：：Very Long Instruction Word)处理机处理机• 四个基本技术四个基本技术–先行控制技术先行控制技术 –流水线技术流水线技术–相关性分析技术相关性分析技术 –动态调度技术动态调度技术 本章主要内容5.1 先行控制技术先行控制技术5.2 流水线技术流水线技术5.3超标量与超流水线处理机超标量与超流水线处理机5.3.1超标量处理机超标量处理机5.3.2 超流水线处理机超流水线处理机5.3.3 超标量超流水线处理机超标量超流水线处理机hlzghhlzgh整理发布整理发布 5.1先行控制技术•先行控制先行控制(Lookahead)技术技术最早在最早在IBM公司的公司的STRETCH机器中采用。
目前，许多处理机中都机器中采用目前，许多处理机中都已经采用了先行控制技术已经采用了先行控制技术•先行控制技术的关键是先行控制技术的关键是缓冲技术缓冲技术和和预处理技术预处理技术•本节主要内容本节主要内容–指令的重叠执行方式指令的重叠执行方式–先行控制方式的原理和结构先行控制方式的原理和结构•先行控制方式的处理机结构先行控制方式的处理机结构•先行控制方式的指令执行序列先行控制方式的指令执行序列•先行缓冲栈先行缓冲栈•缓冲深度的设计方法缓冲深度的设计方法–数据相关数据相关–控制相关控制相关 指令的重叠执行方式1、顺序执行方式顺序执行方式–执行执行n条指令所用的时间为：条指令所用的时间为：–如果每段时间都为如果每段时间都为t，则执行，则执行n条指令所用的时条指令所用的时间为：间为： T＝＝3 n t–主要优点主要优点：控制简单，节省设备控制简单，节省设备–主要缺点主要缺点：执行指令的速度慢，功能部件的利：执行指令的速度慢，功能部件的利用率很低用率很低 指令的重叠执行方式2、一次重叠执行方式、一次重叠执行方式–一种最简单的流水线方式一种最简单的流水线方式–如果两个过程的时间相等，则执行如果两个过程的时间相等，则执行n条指令的时间为：条指令的时间为： T＝（＝（1＋＋2n））t–主要优点：主要优点：•指令的执行时间缩短指令的执行时间缩短•功能部件的利用率明显提高功能部件的利用率明显提高–主要缺点：主要缺点：•需要增加一些硬件需要增加一些硬件•控制过程稍复杂控制过程稍复杂 指令的重叠执行方式•3、二次重叠执行方式、二次重叠执行方式–如果三过程的时间相等，执行如果三过程的时间相等，执行n条指令的时间为：条指令的时间为： T＝＝(2＋＋n））t–在理想情况下，处理机中同时有三条指令在执行在理想情况下，处理机中同时有三条指令在执行–处理机的结构要作比较大的改变，需要采用先行控制处理机的结构要作比较大的改变，需要采用先行控制技术来实现技术来实现 先行控制方式的原理1、采用二次重叠执行方式，必须解决两个问题：、采用二次重叠执行方式，必须解决两个问题：–有独立的取指令部件、指令分析部件和指令执行部件有独立的取指令部件、指令分析部件和指令执行部件•把一个集中的指令控制器，分解成三个独立的控制器：存储控把一个集中的指令控制器，分解成三个独立的控制器：存储控制器、指令控制器、运算控制器制器、指令控制器、运算控制器–要解决访问主存储器的冲突问题要解决访问主存储器的冲突问题•取指令、分析指令、执行指令都可能要访问存储器取指令、分析指令、执行指令都可能要访问存储器2、解决访存冲突的方法：、解决访存冲突的方法：（（1）指令和数据混合存放在同一个主存储器中，采用低）指令和数据混合存放在同一个主存储器中，采用低位交叉存取方式位交叉存取方式•只有取指令、读操作数、写结果所访问的不是同一个存储体时，只有取指令、读操作数、写结果所访问的不是同一个存储体时，才可能实现指令重叠才可能实现指令重叠•这种方法不能根本解决冲突问题这种方法不能根本解决冲突问题 (2)两个独立的存储器两个独立的存储器–独立的指令存储器和数据存储器独立的指令存储器和数据存储器•解决取指令和读操作数的冲突解决取指令和读操作数的冲突–如果再规定，执行指令所需要的操作数和执行结果只如果再规定，执行指令所需要的操作数和执行结果只写写到通用寄存器，而不是主存。
则取指令、分析指令到通用寄存器，而不是主存则取指令、分析指令和执行指令就可以同时进行和执行指令就可以同时进行–在许多高性能处理机中，有独立的指令在许多高性能处理机中，有独立的指令Cache和数据和数据Cache这种结构被称为这种结构被称为哈佛结构哈佛结构–指令存储器和数据存储器分开的明显缺点：对程序员指令存储器和数据存储器分开的明显缺点：对程序员不透明不透明(3)采用先行控制技术采用先行控制技术–先行控制技术的关键是缓冲技术和预处理技术先行控制技术的关键是缓冲技术和预处理技术–缓冲技术是在工作速度不固定的两个功能部件之间设缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作置缓冲栈，用以平滑它们的工作–在采用了缓冲技术和预处理技术之后，运算器能够专在采用了缓冲技术和预处理技术之后，运算器能够专心于数据的运算，从而大幅度提高程序的执行速度心于数据的运算，从而大幅度提高程序的执行速度 先行控制方式的处理机结构1、三个独立的控制器：、三个独立的控制器：–存储控制器、指令控制器、运算控制器存储控制器、指令控制器、运算控制器2、四个缓冲栈：、四个缓冲栈：–先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后行写数栈先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后行写数栈–四个缓冲栈合在一起称为先行缓冲栈四个缓冲栈合在一起称为先行缓冲栈 3、先行指令缓冲栈的组成、先行指令缓冲栈的组成–只要指令缓冲栈没有充满，就自动发出取指令的请求。
只要指令缓冲栈没有充满，就自动发出取指令的请求–设置两个程序计数器：设置两个程序计数器：–先行程序计数器先行程序计数器PC1，用来指示取指令，，用来指示取指令，–现行程序计数器现行程序计数器PC，记录指令分析器正在分析的指令地址，记录指令分析器正在分析的指令地址 4、存在的主要问题、存在的主要问题–各类指令各类指令“分析分析”和和“执行执行”所需的时间相差所需的时间相差很大很大–存在数据相关存在数据相关–转移指令或转子程序指令转移指令或转子程序指令•在本章的以下各节中，将分别介绍这三个在本章的以下各节中，将分别介绍这三个问题的解决方法问题的解决方法 先行控制方式的指令执行时序•设置了指令缓冲栈，取指令的时间就可以设置了指令缓冲栈，取指令的时间就可以忽略不计忽略不计1、分析指令和执行指令时间不相等时的情况、分析指令和执行指令时间不相等时的情况 2、采用先行缓冲栈的指令执行过程、采用先行缓冲栈的指令执行过程•先行读数栈先行读数栈•先行操作栈先行操作栈•后行写数栈后行写数栈 3、指令执行过程的、指令执行过程的时空图时空图表示方法表示方法•理想情况下，指令理想情况下，指令执行部件执行部件应该一直忙碌应该一直忙碌•连续执行连续执行n条指令的时间为：条指令的时间为： 先行缓冲栈•设置先行缓冲栈的目的：设置先行缓冲栈的目的：使指令分析器和指令执行使指令分析器和指令执行部件能够独立工作部件能够独立工作。
分为分为4个栈：个栈：1、先行指令缓冲栈：、先行指令缓冲栈：–位置：主存储器与指令分析器之间位置：主存储器与指令分析器之间–作用：作用：用它来平滑主存储器取指令和指令分析器的工作用它来平滑主存储器取指令和指令分析器的工作–RR型指令：不必处理，直接送先行操作栈型指令：不必处理，直接送先行操作栈–RS和和RX型指令：主存有效地址送先行读数栈，用该先型指令：主存有效地址送先行读数栈，用该先行读数栈的寄存器编号替换指令中的主存地址码部分，行读数栈的寄存器编号替换指令中的主存地址码部分，形成形成RR*指令送先行操作栈指令送先行操作栈–RI型指令：指令中的立即数送先行读数栈，用该先行读型指令：指令中的立即数送先行读数栈，用该先行读数栈的寄存器编号替换指令中的立即数部分，形成数栈的寄存器编号替换指令中的立即数部分，形成RR*指令送先行操作栈指令送先行操作栈–转移指令：一般在指令分析器中直接执行转移指令：一般在指令分析器中直接执行 •2、先行操作栈、先行操作栈–位置：指令分析器和运算控制器之间位置：指令分析器和运算控制器之间–作用：作用：使指令分析器和运算器能够各自独立工作使指令分析器和运算器能够各自独立工作–采用先进先出方式工作，由指令寄存器堆和控制逻辑采用先进先出方式工作，由指令寄存器堆和控制逻辑组成组成•3、先行读数栈、先行读数栈–位置：主存储器与运算器之间位置：主存储器与运算器之间–作用：作用：平滑运算器与主存储器的工作平滑运算器与主存储器的工作–每个缓冲寄存器由地址寄存器、操作数寄存器和标志每个缓冲寄存器由地址寄存器、操作数寄存器和标志三部分组成。
也可以把地址寄存器和操作数寄存器合三部分组成也可以把地址寄存器和操作数寄存器合为一个为一个–当收到从指令分析器中送来的有效地址时，就向主存当收到从指令分析器中送来的有效地址时，就向主存申请读操作数申请读操作数–读出的操作数存放在操作数寄存器中或覆盖掉地址寄读出的操作数存放在操作数寄存器中或覆盖掉地址寄存器中的地址存器中的地址 4、后行写数栈、后行写数栈–每个后行缓冲寄存器由地址寄存器、数据寄存每个后行缓冲寄存器由地址寄存器、数据寄存器和标志三部分组成器和标志三部分组成–指令分析器遇到向主存写结果的指令，把形成指令分析器遇到向主存写结果的指令，把形成的有效地址送入后行写数栈的地址寄存器中，的有效地址送入后行写数栈的地址寄存器中，并用该地址寄存器的编号替换指令的目的地址并用该地址寄存器的编号替换指令的目的地址部分，形成部分，形成RR*指令送入先行操作栈指令送入先行操作栈–当运算器执行这条当运算器执行这条RR*型写数指令时，型写数指令时，只要把只要把写到主存的数据送到后行写数栈的数据寄存器写到主存的数据送到后行写数栈的数据寄存器中即可中即可 5 5、采用先行控制方式时，一个程序的执行情况：、采用先行控制方式时，一个程序的执行情况： 6 6、、先行缓冲栈访问主存的优先级：先行缓冲栈访问主存的优先级： 后行写数栈 > 先行读数栈 > 先行指令缓冲栈7 7、其余缓冲栈的设计原则、其余缓冲栈的设计原则 各个缓冲栈的缓冲深度一般有如下关系：各个缓冲栈的缓冲深度一般有如下关系： DI≥≥DC≥≥DR≥≥DW 其中：其中：DI是先行指令缓冲栈的缓冲深度是先行指令缓冲栈的缓冲深度 DC是先行操作栈的缓冲深度是先行操作栈的缓冲深度 DR是先行读数栈的缓冲深度是先行读数栈的缓冲深度 DW是后行写数栈的缓冲深度是后行写数栈的缓冲深度例如：例如：IBM370/165IBM370/165机：机：DI＝＝4 4，，DC＝＝3 3，，DR＝＝2 2，，DW＝＝1 1 我国研制的两台大型计算机：我国研制的两台大型计算机： DI＝＝8 8，，DC＝＝DR＝＝4 4，，DW＝＝2 2 DI＝＝1212，，DC＝＝DR＝＝6 6，，DW＝＝2 2 相关性•定义定义:指一段程序的相近指令之间存在某种指一段程序的相近指令之间存在某种 关系，这种关系可能影响指令的重叠执行。
关系，这种关系可能影响指令的重叠执行•分类：数据相关、控制相关分类：数据相关、控制相关•数据相关：程序在执行一条指令时指令所数据相关：程序在执行一条指令时指令所 要用要用到的指令、操作数、变址偏移量等正好是前面的到的指令、操作数、变址偏移量等正好是前面的指令的执行结果则必须等待前面指令写结果后才指令的执行结果则必须等待前面指令写结果后才能进行•控制相关：由于程序的执行方向可能被改变而引控制相关：由于程序的执行方向可能被改变而引起的相关起的相关 数据相关性•数据相关分为：数据相关分为：•指令相关指令相关•主存操作数相关主存操作数相关•通用寄存器相关通用寄存器相关•变址相关变址相关 指令相关•定义：定义：k：：store R1,k+1 k+1: … … 其中：结果地址（其中：结果地址（k））=指令地址（指令地址（k+1），故称），故称指令相关指令相关•测试：把每条指令的结果地址与先行操作栈、指测试：把每条指令的结果地址与先行操作栈、指令分析器、先行指令缓冲栈中的所有指令地址比令分析器、先行指令缓冲栈中的所有指令地址比较，相等则有较，相等则有•办法：不允许指令修改；通过设置专门的执行指办法：不允许指令修改；通过设置专门的执行指令把指令相关变成数据相关令把指令相关变成数据相关•例：例：IBM370的执行指令：的执行指令： EXE（执行）R1X2B2D2 主存操作数相关•定义：定义： k: op A1,A2,A3 ;A1=(A2)op(A3) k+1: op A4,A5,A1 ;A4=(A5)op(A1)存在：结果地址（存在：结果地址（K））=主存操作数地址（主存操作数地址（K+1）） 则发生主存操作数相关。
则发生主存操作数相关•办法：推后处理办法：推后处理分析k分析k+1执行k分析k+1(推后)执行k+1 结果写主存A1读主存A1请求时间t 通用寄存器相关•定义：定义：k: op R1, A2 ;R1=(R1)op(A2) k+1: op R1, R2 ;R1=(R1)op(R2)有：有：R1(k)=R1(k+1), 称为称为R1数据相关；数据相关； R1(k)=R2(k+1), 称为称为R2数据相关数据相关•办法：办法：1、通用寄存器是、通用寄存器是D触发器且不设缓冲寄存器或锁触发器且不设缓冲寄存器或锁 存器则无相关存器则无相关2、指令分析推后一个周期、指令分析推后一个周期3、指令分析推后一个节拍、指令分析推后一个节拍4、采用专用的数据通道、采用专用的数据通道第1拍第2拍第3拍第4拍写R1读R1读R2执行k分析k+1执行k分析k+1写R1读R2读R1 通用寄存器相关（续）通用寄存器堆锁存器锁存器运算器专用通道设置专用数据通道解决寄存器数据相关 变址相关•定义：定义：k: op R1, R2 R1=(R1)op(R2) k+1: op R1, A2(X2) R1=(R1)op((A2)+(X2)) k+2: op R1, A2(X2) R1=(R1)op((A2)+(X2)) 若若R1(k)=X2(k+1),称一次变址相关；若称一次变址相关；若R1(k)=X2(k+2),称二次变址相关称二次变址相关•原因：发生二次变址相关的原因是写结果要一段稳定时间原因：发生二次变址相关的原因是写结果要一段稳定时间分析k执行k分析k+1执行k+1分析k+2执行k+2t1t2t2办法：推后处理和设置专用通道 数据相关数据相关的三种解决办法：数据相关的三种解决办法：•1、避免数据相关（调整指令流）；、避免数据相关（调整指令流）；•2、推后处理；、推后处理；•3、设置专用的数据通路。
设置专用的数据通路 控制相关•引起控制相关的原因有：引起控制相关的原因有： 无条件转移、一般条件转移、复合条件转移、无条件转移、一般条件转移、复合条件转移、子程序调用、中断等子程序调用、中断等•吸收型指令：在指令分析器中就执行完的吸收型指令：在指令分析器中就执行完的指令•无条件转移、一般条件转移是吸收型指令无条件转移、一般条件转移是吸收型指令•本节讨论几种转移指令引起的相关本节讨论几种转移指令引起的相关 无条件转移引起的相关•程序：程序： k: JMP L … : … … L: … …•分析：无条件转移是吸收型指令；分析：无条件转移是吸收型指令； 指令指令L分在先行指令缓冲栈和不在两种情况分在先行指令缓冲栈和不在两种情况•指令执行时序：指令执行时序：分析k-1执行k-1分析k取指令L分析L分析L分析L+1执行L执行L执行L+1指令L不在指令缓冲栈：指令L在指令缓冲栈：方法：在先行指令缓冲栈入口设置指令分析器方法：在先行指令缓冲栈入口设置指令分析器 一般条件转移引起的相关•程序：程序： k: … k+1:JMP(CC) L … : … L: …•分析：一般条件转移指令是吸收型指令；分析：一般条件转移指令是吸收型指令； 分三种情况：分三种情况：分析k执行k分析k+1取指令L分析L分析L分析L+1执行L执行L执行L+1执行k+2分析k+2分析k+1分析k+1成功，指令L不在指令缓冲栈：成功，指令L在指令缓冲栈：转移不成功方法：降低转移成功的概率；减少转移成功的对先行控制 器的影响 复合条件转移引起的相关•程序：程序： k: op L k+1: … … : … L : …•分析：非吸收型指令分析：非吸收型指令•执行时序：执行时序：分析k执行k分析k+1取指令L分析L分析L分析L+1执行L执行L执行L+1执行k+1成功，指令L不在指令缓冲栈：成功，指令L在指令缓冲栈：转移不成功方法：1、转移预测； 2、对于短循环程序设置开门指令和关门指令。
转移预测技术•1、延时转移、延时转移•2、指令取消、指令取消•3、软件猜测：编译时是进行，如图：、软件猜测：编译时是进行，如图：•4、硬件猜测：在先行指令缓冲栈入、硬件猜测：在先行指令缓冲栈入口设置指令分析器，检测转移指令，口设置指令分析器，检测转移指令， 有，则按目标地址预取有，则按目标地址预取•5、设置两个先行指令缓冲栈：一个、设置两个先行指令缓冲栈：一个预取转移指令下面的程序；一个预取预取转移指令下面的程序；一个预取目标程序目标程序•6、设置专门的短循环程序的开门和、设置专门的短循环程序的开门和关门指令关门指令in循环体ii-1i>0in循环体ii-1i=0in循环体ii-1i<0YNNNYY一般条件转移复合条件转移原来程序 5.2 流水线技术•开发处理机内部的并行性方法开发处理机内部的并行性方法–空间并行性空间并行性：设置多个独立的操作部件：设置多个独立的操作部件•如多操作部件处理机、超标量处理机如多操作部件处理机、超标量处理机–时间并行性时间并行性：采用：采用流水线技术流水线技术•不增加或只增加少量硬件就能使运算速度提高几倍不增加或只增加少量硬件就能使运算速度提高几倍•如流水线处理机、超流水线处理机如流水线处理机、超流水线处理机•本节主要内容：本节主要内容：5.2.1 流水线工作原理流水线工作原理5.2.2 流水线的分类流水线的分类5.2.3 线性流水线的性能分析线性流水线的性能分析5.2.4 非线性流水线的调度技术非线性流水线的调度技术 洗衣店的例子洗衣店的例子甩干要用甩干要用 30 分钟分钟叠衣物也需要叠衣物也需要 30 分钟分钟清洗要花清洗要花 30 分钟分钟A, B, C, D均有一些衣物要均有一些衣物要清洗，甩干，折叠清洗，甩干，折叠ABCD还要花费还要花费 30 分钟的时间分钟的时间将衣物放在衣柜里将衣物放在衣柜里流水线是很自然的! 洗洗4 个人的衣物，顺序操作需要个人的衣物，顺序操作需要 8 个小时个小时 如果使用流水线作业如果使用流水线作业, 将需要多少时间呢将需要多少时间呢?顺序操作任任务务顺顺序序303030BCDA时间30 3030303030303030303030306 下午下午 78910111212 上午上午 流水线作业30 30任务顺序122 上午上午6 下午下午78910111时间BCDA3030 303030 流水线作业洗流水线作业洗4个人的衣物只需要个人的衣物只需要 3.5 个小时个小时! 30 30任任务务顺顺序序6 下午下午789时间时间BCDA3030 303030有关流水线的问题•流水线无法帮助解决流水线无法帮助解决单个任务单个任务的时间的时间, 有利于减少有利于减少整个工作整个工作全部时间全部时间——吞吐量吞吐量•多个任务同时操作需要多个任务同时操作需要不同的不同的资源资源•可能的加速比可能的加速比 = 流水线的段数流水线的段数•流水线的速率受速度流水线的速率受速度最慢的最慢的流流水段的限制水段的限制•流水线各段流水线各段长度不均长度不均会降低加会降低加速比速比•充满充满流水线所需的时间和流水线所需的时间和排空排空流水线所需的时间影响加速比流水线所需的时间影响加速比•会由于会由于任务的相关任务的相关而造成阻塞而造成阻塞 流水线工作原理1、简单流水线、简单流水线–流水线的每一个阶段称为流水步、流水步骤、流水段、流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节流水线阶段、流水功能段、功能段、流水级、流水节拍等拍等–在每一个流水段的末尾或开头必须设置一个寄存器，在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等流称为流水寄存器、流水锁存器、流水闸门寄存器等流水锁存器会增加每条指令的执行时间，但采用流水线水锁存器会增加每条指令的执行时间，但采用流水线之后整个程序的执行时间会缩短之后整个程序的执行时间会缩短–为了简化，在一般流水线中不画出流水锁存器。
为了简化，在一般流水线中不画出流水锁存器 流水线工作原理2、流水线的表示方法、流水线的表示方法–流水线的连接图表示方法流水线的连接图表示方法•表示流水线的逻辑关系表示流水线的逻辑关系 流水线的时空图表示方法流水线的时空图表示方法 表示流水线的时间关系表示流水线的时间关系 流水线的预约表表示方法流水线的预约表表示方法 将在将在非线性流水线非线性流水线中介绍中介绍 一般处理机的指令流水线为一般处理机的指令流水线为 4 4 至至 12 12 个级个级 指令流水线等于和大于指令流水线等于和大于8 8级的称为级的称为超流水线处理机超流水线处理机 •一个浮点加法器流水线的时空图一个浮点加法器流水线的时空图–由由求阶差、对阶、尾数加和规格化求阶差、对阶、尾数加和规格化4 4个流水段组成个流水段组成3 3、流水线时空图、流水线时空图•一条一条简单流水线的时空图简单流水线的时空图 4、流水线的主要特点、流水线的主要特点–只有连续提供同类任务才能充分发挥流水线的效率只有连续提供同类任务才能充分发挥流水线的效率–对于指令流水线：要尽量减少因条件分支造成的对于指令流水线：要尽量减少因条件分支造成的“断流断流”–对于操作部件：主要通过编译技术，尽量提供连续的相同对于操作部件：主要通过编译技术，尽量提供连续的相同类型的操作。
类型的操作–在流水线的每一个流水线段中都要设置一个流水锁存器在流水线的每一个流水线段中都要设置一个流水锁存器•时间开销：流水线的执行时间加长，时间开销：流水线的执行时间加长，•是流水线中需要增加的主要硬件之一是流水线中需要增加的主要硬件之一–各流水段的时间应尽量相等各流水段的时间应尽量相等•流水线处理机的基本时钟周期等于时间最长的流水段的时间长度流水线处理机的基本时钟周期等于时间最长的流水段的时间长度–流水线需要有流水线需要有“装入时间装入时间”和和“排空时间排空时间”–Latency & throughput? •流水线技术在流水线技术在50年代后期被应用于处理器年代后期被应用于处理器•IBM Stretch----first general-purpose pipelined puter•CDC 6600 use load/store design to achieve efficient pipelining. 流水线的分类1、线性流水线与非线性流水线、线性流水线与非线性流水线–流水线的各个流水段之间是否有反馈信号流水线的各个流水段之间是否有反馈信号–线性流水线（线性流水线（Linear Pipelining））•每一个流水段都流过一次，而且仅流过一次每一个流水段都流过一次，而且仅流过一次•线性流水线能够用流水线连接图唯一表示线性流水线能够用流水线连接图唯一表示–非线性流水线（非线性流水线（Nonlinear Pipelining））•在流水线的某些流水段之间有反馈回路或前馈回路。
在流水线的某些流水段之间有反馈回路或前馈回路•非线性流水线必须用流水线连接图流水线预约表等共同表示非线性流水线必须用流水线连接图流水线预约表等共同表示 2、按照流水线的级别来分、按照流水线的级别来分–处理机级流水线，又称为处理机级流水线，又称为指令流水线指令流水线–例如：在采用先行控制器的处理机中，各功能部件之例如：在采用先行控制器的处理机中，各功能部件之间的流水线间的流水线 部件级流水线，即部件级流水线，即操作流水线操作流水线如浮点加法器流水线如浮点加法器流水线 –处理机之间的流水线称为处理机之间的流水线称为宏流水线宏流水线（（Macro Pipelining））•每个处理机对同一个数据流的不同部分分别进行处理每个处理机对同一个数据流的不同部分分别进行处理 3、单功能流水线与多功能流水线、单功能流水线与多功能流水线–单功能流水线：只能完成一种固定功能的流水单功能流水线：只能完成一种固定功能的流水线线•Cray-1计算机种有计算机种有12条条•YH-1计算机有计算机有18条条•Pentium有一条有一条5段的定点和一条段的定点和一条8段的浮点流水线段的浮点流水线•PentiumⅢ有两条定点指令流水线，一条浮点指令有两条定点指令流水线，一条浮点指令流水线。
流水线–多功能流水线：流水线的各段通过不同的连接多功能流水线：流水线的各段通过不同的连接实现不同的功能实现不同的功能•Texas公司的公司的ASC计算机中的计算机中的8段流水线，能够实现：段流水线，能够实现：–定点加减法、定点乘法定点加减法、定点乘法–浮点加法、浮点乘法浮点加法、浮点乘法–逻辑运算、移位操作逻辑运算、移位操作–数据转换、向量运算等数据转换、向量运算等 4、静态流水线与动态流水线、静态流水线与动态流水线–静态流水线静态流水线：同一段时间内，多功能流水线中的各个功能：同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能段只能按照一种固定的方式连接，实现一种固定的功能•只有连续出现同一种运算时，流水线的效率才能得到充分的发挥只有连续出现同一种运算时，流水线的效率才能得到充分的发挥 –动态流水线动态流水线：在同一段时间内，多功能流水线：在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行中的各段可以按照不同的方式连接，同时执行多种功能多种功能 5、流水线的其他分类方法、流水线的其他分类方法–按照数据表示方式：标量流水线和向量流水线按照数据表示方式：标量流水线和向量流水线–按照控制方式：同步流水线和异步流水线按照控制方式：同步流水线和异步流水线–顺序流水线与乱序流水线顺序流水线与乱序流水线•乱序流水线又称为无序流水线、错序流水线或异步流水线等乱序流水线又称为无序流水线、错序流水线或异步流水线等 线性流水线的性能分析 衡量流水线性能的主要指标有：衡量流水线性能的主要指标有：吞吐率、加速比和效率。
1、吞吐率（Though PutThough Put））• 计算流水线吞吐率的最基本公式： 其中：其中：n n为任务数，Ｔ为任务数，Ｔk k为完成为完成n n个任务所用的时间个任务所用的时间• 各段执行时间相等，输入连续任务情况下：各段执行时间相等，输入连续任务情况下： 完成完成n n个连续任务需要的总时间为：个连续任务需要的总时间为：Tk＝（k＋n－1）t 其中：其中：k 为流水线的段数，为流水线的段数， t t为时钟周期为时钟周期 吞吐率为： 最大吞吐率为：• 各段执行时间不相等，输入连续任务情况下： 吞吐率为： 最大吞吐率为：• 流水线各段执行时间不相等的解决办法 (1)将流水线的“瓶颈”部分再细分（如果可分的话） 2、加速比（（SpeedupSpeedup））• 计算流水线加速比的基本公式：• 各段执行时间相等，输入连续任务情况下：各段执行时间相等，输入连续任务情况下： 加速比为：加速比为： 最大加速比为：最大加速比为：•各段执行时间不相等，输入连续任务情况下各段执行时间不相等，输入连续任务情况下, , 实际加速比为：实际加速比为： • 当流水线段数增加时，需要连续输入的任务数也必须增加当流水线段数增加时，需要连续输入的任务数也必须增加 4、流水线最佳段数的选择 采用顺序执行方式完成一个任务的时间为采用顺序执行方式完成一个任务的时间为t t 在同等速度的在同等速度的k段流水线上执行一个任务的时间为：段流水线上执行一个任务的时间为：t／／k＋＋d 其中：其中：d为流水锁存器的延迟时间为流水锁存器的延迟时间 流水线的最大吞吐率为：流水线的最大吞吐率为： 流水线的总价格估计为：流水线的总价格估计为：C＝＝a＋＋b k，， 其中：其中：a为所有功能段本身的总价格，为所有功能段本身的总价格，b为每个锁存器的价格为每个锁存器的价格 A.G.Larson把流水线的性把流水线的性 能价格比能价格比PCR定义为：定义为： 求得到求得到PCR的最大值为：的最大值为： 5、流水线性能分析举例 对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。
容易计算出流水线的吞吐率、加速比和效率例：用一条用一条4 4段浮点加法器流水线求段浮点加法器流水线求8 8个浮点数的和：个浮点数的和： Z Z＝＝A A＋＋B B＋＋C C＋＋D D＋＋E E＋＋F F＋＋G G＋＋H H解：Z Z＝＝[ [（（A A＋＋B B）＋（）＋（C C＋＋D D））] ]＋＋[ [（（E E＋＋F F）＋（）＋（G G＋＋H H））] ] 流水线工作原理流水线的分类线性流水线的性能分析非线性流水线的调度技术 标量处理机标量处理机——流水线技术流水线技术 非线性流水线的调度技术 非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高1、非线性流水线的表示 线性流水线能够用流水线连接图唯一表示线性流水线能够用流水线连接图唯一表示 连接图不能用唯一表示非线性流水线的工作流程，因此，引入流水线连接图不能用唯一表示非线性流水线的工作流程，因此，引入流水线预约表预约表 • 与流水线预约表对应的流水线连接图与流水线预约表对应的流水线连接图 • 一张预约表可能与多个流水线连接图相对应一张预约表可能与多个流水线连接图相对应 • 一个流水线连接图对应与多张预约表一个流水线连接图对应与多张预约表 2、非线性流水线的冲突 流水线的启动距离：连续输入两个任务之间的时间间隔 流水线的冲突：几个任务争用同一个流水段几个任务争用同一个流水段 3、无冲突调度方法,由由E.S.DavidsonE.S.Davidson及其学生于及其学生于19711971年提出年提出 非线性流水线的禁止启动向量（集合）：预约表中每一行任意两个预约表中每一行任意两个“×” “×” 之间的距离都计算出来，去掉重复的。
上例中为之间的距离都计算出来，去掉重复的上例中为（3，4，6） 由禁止向量得到冲突向量：C＝（＝（CmCm-1…C2C1）） 其中：其中：m是是禁止向量中的最大值如果禁止向量中的最大值如果i在禁止向量中，在禁止向量中， 则则Ci＝＝1，否则，否则Ci＝＝0上例中例中 C＝（101100） 由冲突向量构造状态图： 把冲突向量送入一个m位逻辑右移移位器；如果移位器移出0，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；否则不作任何处理；如此重复m次 对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理 在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，当新形成的冲突向量出现重复时可以合并到一起 例5.3：一条有一条有4 4个功能段的非线性流水线，每个功能段的延迟个功能段的非线性流水线，每个功能段的延迟 时间都相等，它的预约表如下：时间都相等，它的预约表如下： (1) (1) 写出流水线的禁止向量和初始冲突向量写出流水线的禁止向量和初始冲突向量 (2) (2) 画出调度流水线的状态图。
画出调度流水线的状态图 (3) (3) 求流水线的最小启动循环和最小平均启动距离求流水线的最小启动循环和最小平均启动距离 (4) (4) 求平均启动距离最小的恒定循环求平均启动距离最小的恒定循环解：：(1)(1)禁止向量为：（禁止向量为：（2 2，，4 4，，6 6）） 初始冲突向量：101010 (2) (2)初始冲突向量逻辑右移初始冲突向量逻辑右移2 2、、4 4、、6 6位时，不作任何处理，位时，不作任何处理， 逻辑右移逻辑右移1 1、、3 3、、5 5和大于等于和大于等于7 7时，要进行处理时，要进行处理 初始冲突向量右移初始冲突向量右移1 1位之后：位之后：010101∨101010010101∨101010＝＝111111111111，，初始冲突向量右移初始冲突向量右移3 3位之后：位之后：000101∨101010000101∨101010＝＝101111101111，，初始冲突向量右移初始冲突向量右移5 5位之后：位之后：000001∨101010000001∨101010＝＝101011101011，，初始冲突向量右移初始冲突向量右移7 7位或大于位或大于7 7位后：还原到它本身。
位后：还原到它本身中间冲突向量中间冲突向量101111101111右移右移5 5位之后：位之后：000001∨101010000001∨101010＝＝101011101011，，中间冲突向量中间冲突向量101011101011右移右移3 3位之后：位之后：000101∨101010000101∨101010＝＝101111101111，，中间冲突向量中间冲突向量101011101011右移右移5 5位之后：位之后：000001∨101010000001∨101010＝＝101011101011 预约表与状态图是唯一对应， 但不同的预约表也可能有相同的状态图 简单循环：状态图中各种冲突向量只经过一次的启动循环状态图中各种冲突向量只经过一次的启动循环 简单循环的个数是有限的简单循环的个数是有限的, ,由简单循环计算平均启动距离由简单循环计算平均启动距离3)(3)最小的启动循环为（最小的启动循环为（1 1，，7 7）和（）和（3 3，，5 5））, ,平均启动距离为 44)(4)启动距离最小的恒定循环是（5） •简单循环中所包含的每一个等待时间都简单循环中所包含的每一个等待时间都来自此循环某一个状态的最小等待时间来自此循环某一个状态的最小等待时间（输出弧）。
输出弧） 4、优化调度方法• L.E.SharL.E.Shar于于19721972年提出流水线最小平均启动距离的限制范围年提出流水线最小平均启动距离的限制范围 (1)下限是预约表中任意一行里“×”的最多个数 (2)小于或等于状态图中任意一个简单循环的平均启动距离 (3)最小平均启动距离的上限是冲突向量中1的个数再加上1• 1992 1992年，年，L.E.SharL.E.Shar又证明了上述限制范围又证明了上述限制范围 最有用的是第最有用的是第1 1条预约表中条预约表中“×”“×”最多的行一定是最多的行一定是瓶颈流水段• 采用预留算法来调度非线性流水线，可以达到最优调度： (1)确定最小平均启动距离（MAL）预约表任一行中预约表任一行中“×”“×”的最多个数的最多个数 (2)确定最小启动循环一般恒定循环作为最小启动循环一般恒定循环作为最小启动循环 (3)通过插入非计算延迟段--修改预约表实现最小启动循环 对于上面的例5.3：最小平均启动距离为最小平均启动距离为2 2 最小启动循环为恒定循环（最小启动循环为恒定循环（2 2）。
任一行中与第1个“×”的距离为2的倍数的周期都要预留出来 • 每一行中与第1个“×”的距离为2的倍数的位置都要预留出来 S3行行的第的第2个个“×”从周期从周期5延迟到周期延迟到周期6为此， S2行行的第的第2个个“×”要向后延迟一个周期，从周期要向后延迟一个周期，从周期6延迟到周期延迟到周期7；； S1行行的第的第2个个“×”要向后延迟一个周期，从周期要向后延迟一个周期，从周期7延迟到周期延迟到周期8 实际上，只要在流水段实际上，只要在流水段S S4 4的输出端到流水段的输出端到流水段S S3 3的输入端中间插入一个非计算的输入端中间插入一个非计算延迟延迟D1 •在非线性流水线中，在非线性流水线中，“×”最多的流水段一定是最多的流水段一定是“瓶颈瓶颈“流水段•实现最优调度的目标是使实现最优调度的目标是使“瓶颈”流水段处于忙碌状态，没有空闲周期•最优调度方法能够使非线性流水线的吞吐率、加速比和效率最优调度方法能够使非线性流水线的吞吐率、加速比和效率达到最优达到最优 流水线的相关性•流水线的发生相关的可能性更大影响更严流水线的发生相关的可能性更大影响更严重重•分为：局部相关和全局相关分为：局部相关和全局相关•局部相关：块内；全局相关：块间局部相关：块内；全局相关：块间•局部相关有：局部相关有：WR、、RW、、WWB0B1B2 局部相关的原因及对策•1、顺序流动与乱序流动、顺序流动与乱序流动•程序：程序：k: R0(R1) k+1: k+2:R2 (R0)+(R3) k+3: k+4: k+5:•顺序流动：任务在流水线中的流入顺序与流出顺序顺序流动：任务在流水线中的流入顺序与流出顺序完全相同完全相同•乱序流动：允许无数据相关的后续指令进入相关指乱序流动：允许无数据相关的后续指令进入相关指令占有的功能段执行，并越过相关指令继续向前流令占有的功能段执行，并越过相关指令继续向前流动动 局部相关的原因及对策S1S2S3S4S5S6寄存器寄存器R0读读写写专用路径专用路径tsts 局部相关的原因及对策•程序：程序：k: R0=R1×R4 k+1: R6=R5+1 k+2: R2=R0×R3 k+3: R3=R4-1 k+4: R2=R5 •在乱序流动中存在三种相关在乱序流动中存在三种相关:WR、、RW、、WW。
局部相关的原因及对策•数据相关的对策：数据相关的对策： 1、延迟执行、延迟执行 2、建立专用的路径，分两类：、建立专用的路径，分两类： （（1））Tomasulo算法：分散控制的公共数据总线；算法：分散控制的公共数据总线； （（2））CDC记分牌法：集中控制记分牌法：集中控制 •数据重定向（专用路径）：数据重定向（专用路径）： （（1）先写后读数据相关）先写后读数据相关 （（2）写）写-写数据相关写数据相关ABCABCABCABCtt+Δtttt+Δtt+Δtt+Δt 全局相关及其对策•转移的影响转移的影响: （（1）逻辑错误：第）逻辑错误：第i+1条指令条指令((R1)+(R2)R1)执执行完行完,则寄存器内容写完则寄存器内容写完,程序结果错程序结果错. 办法办法:形成条件码前不执行形成条件码前不执行;执行但不写结果执行但不写结果. (2) 性能影响性能影响:TK-IF=(n+k-1) Δt+npq(k-1) Δti-1i+1i+2i+k-3ii+k-2pp+1p+k-4p+k-3形成条件码形成条件码转移指令转移指令转移不成功转移不成功转移成功转移成功形成条件转移形成条件转移 全局相关及其对策•对策对策: 1.延迟转移和指令取消技术延迟转移和指令取消技术 2.静态转移预测技术静态转移预测技术 3.动态转移预测技术动态转移预测技术 4.提前形成条件码提前形成条件码•中断的影响中断的影响:分精确断点和不精确断点分精确断点和不精确断点1.不精确断点硬件简单不精确断点硬件简单,但可能有逻辑错误但可能有逻辑错误,响应时间长响应时间长.2.精确断点响应及时精确断点响应及时,但硬件复杂但硬件复杂.S1S2S3S4S5S6S7S8i+5i+4i+3i+2i+1ii-1i-2 中断申请中断申请不精确断点不精确断点不精确断点不精确断点 5.3 超标量处理机和超流水线处理机•流水线处理机只有一条流水线、一个多功能操作部件流水线处理机只有一条流水线、一个多功能操作部件 指令级并行度指令级并行度 ILP<1•多操作部件处理机只有一条流水线、多个多功能操作部件多操作部件处理机只有一条流水线、多个多功能操作部件 指令级并行度指令级并行度 ILP<1•本节讨论超标量处理机、超流水线处理机、超标量超流水线处理机本节讨论超标量处理机、超流水线处理机、超标量超流水线处理机 它们的指令级并行度它们的指令级并行度 ILP>1本节主要内容：本节主要内容：•5.3.1 超标量处理机超标量处理机•5.3.2 超流水线处理机超流水线处理机•5.3.3 超标量超流水线处理机超标量超流水线处理机 超标量处理机•基本结构基本结构:多个操作部件多个操作部件.如如:一个或多个通用寄存器堆一个或多个通用寄存器堆;两个两个Cache;三种处理部三种处理部件件:定点处理单元定点处理单元,浮点处理单元浮点处理单元,图形处理单元图形处理单元.•例例:Motorola公司的公司的MC88110.整数整数部件部件整数整数部件部件位操作位操作部件部件浮点加浮点加部件部件乘法乘法部件部件图形图形部件部件除法除法部件部件图形图形部件部件读数读数/存数存数部件部件通用通用寄存器堆寄存器堆扩展扩展寄存器堆寄存器堆目标指令目标指令Cache指令分配指令分配/转移部件转移部件数据数据Cache(8KB)指令指令Cache(8KB)32位地址总线位地址总线64位数据总线位数据总线系统总线系统总线内部总线内部总线 单发射与多发射•单发射与多发射的时空图如下单发射与多发射的时空图如下:IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR时间时间时间时间指令指令指令指令单发射与多发射处理机的流水线如下单发射与多发射处理机的流水线如下: 单发射与多发射IFIDFA1FA2FA3MD1MD2MD3ALLSWRIFIDFA1FA2FA3MD1MD2MD3ALLSWRIFIDWR 单发射与多发射•一个时钟周期内同时发射多条指令的处理机称为超标量处一个时钟周期内同时发射多条指令的处理机称为超标量处理机理机•指令级并行度为：指令级并行度为：1
成•无先行控制窗口的多流水线只能实现顺序发射，有先行控制窗口的多无先行控制窗口的多流水线只能实现顺序发射，有先行控制窗口的多流水线既能实现顺序发射，又能实现顺乱发射流水线既能实现顺序发射，又能实现顺乱发射•调度要注意相关和功能部件冲突调度要注意相关和功能部件冲突•程序：程序：I1: LOAD R1, A ; R1(A)I2: FADD R2, R1 ; R2 ( R2)+(R1)I3: FMUL R3, R4 ; R3 (R3) × (R4)I4: FADD R4, R5 ; R4 (R4)+(R5)I5: DEC R6 ; R6 (R6)-1I6 FMUL R6, R7 ; R6 (R6)×(R7) 多流水线的调度•顺序发射顺序完成顺序发射顺序完成IF1IF2IF1IF2IF1IF2ID2ID1ID2ID1ID1ID2LSWR1FA1MD1ALFA2FA1MD2MD1FA3FA2MD3MD2WR2FA3MD3WR2WR1WR1WR2IF1IF2IF1IF2IF1IF2ID2ID1ID2ID1ID1ID2LSWR1FA1MD1ALFA2FA1MD2MD1FA3FA2MD3MD2WR2FA3MD3WR2WR1WR1WR2I1I2I3I4I5I6I1I2I3I4I5I6顺序发射乱序完成顺序发射乱序完成 多流水线的调度•乱序发射乱序完成乱序发射乱序完成IF1IF2IF3IF1IF2IF1ID2ID1ID1ID3ID2ID1LSMD1WR1MD2FA2ALMD3FA1FA3MD1FA2FA1MD2WR2FA3MD3WR2WR1WR1WR2I1I2I3I4I5I6超标量处理机的多功能部件可采用流水线，也可不采用流超标量处理机的多功能部件可采用流水线，也可不采用流水线水线不采用流水线时功能冲突更大不采用流水线时功能冲突更大 超流水线处理机•指令执行时序指令执行时序IFWREXIDIFWREXIDIFWREXIDIFWREXIDIFWREXIDIFWREXIDIFWREXIDI1I2I3I4I5I6I7超流水线处理机：一个周期内分时发射多条指令超流水线处理机：一个周期内分时发射多条指令典型的结构：典型的结构：MIPS系列系列1
写回结果 超标量超流水线处理机•指令时序：指令时序：IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR时间时间指令指令IFIDEXWRIFIDEXWRIFIDEXWR定义：一个周期内分时发射多次，每次发射多条指令定义：一个周期内分时发射多次，每次发射多条指令指令级并行度：指令级并行度：1
行部件的冲突小•2、、ILP较小时，性能随之增大变化较快，较小时，性能随之增大变化较快，ILP较大时变化较大时变化缓慢•3、对于特定的程序，由于数据和控制相关的存在，指令、对于特定的程序，由于数据和控制相关的存在，指令级并行度是确定的级并行度是确定的。