操作系统第五章ppt

1、第一章 基本概念第二章 指令系统第三章 存储系统第四章 输入输出系统第五章 标量处理机第六章 向量处理机第七章 互连网络第八章 并行处理机第九章 多处理机标量处理机具有标量数据表示和标量指令系统的处理机称为具有标量数据表示和标量指令系统的处理机称为标量处理机标量处理机提高指令执行速度的主要途径提高指令执行速度的主要途径提高处理机的工作主频提高处理机的工作主频采用更好的算法和设计更好的功能部件采用更好的算法和设计更好的功能部件采用指令级并行技术采用指令级并行技术 三种指令级并行处理机三种指令级并行处理机流水线（流水线（pipelining ）处理机超流水线（处理机超流水线（Superpipeli

2、ning ）处理机处理机超标量（超标量（Superscalar）处理机处理机超长指令字超长指令字(VLIW：Very Long Instruction Word)处理机处理机 四个基本技术四个基本技术先行控制技术先行控制技术 流水线技术流水线技术相关性分析技术相关性分析技术 动态调度技术动态调度技术本章主要内容5.1 先行控制技术先行控制技术5.2 流水线技术流水线技术5.3超标量与超流水线处理机超标量与超流水线处理机5.3.1超标量处理机超标量处理机5.3.2 超流水线处理机超流水线处理机5.3.3 超标量超流水线处理机超标量超流水线处理机 5.1先行控制技术先行控制先行控制(Lookahe

3、ad)技术技术最早在最早在IBM公司的公司的STRETCH机器中采用。目前，许多处理机中都机器中采用。目前，许多处理机中都已经采用了先行控制技术已经采用了先行控制技术先行控制技术的关键是先行控制技术的关键是缓冲技术缓冲技术和和预处理技术预处理技术本节主要内容本节主要内容指令的重叠执行方式指令的重叠执行方式先行控制方式的原理和结构先行控制方式的原理和结构先行控制方式的处理机结构先行控制方式的处理机结构先行控制方式的指令执行序列先行控制方式的指令执行序列先行缓冲栈先行缓冲栈缓冲深度的设计方法缓冲深度的设计方法数据相关数据相关控制相关控制相关指令的重叠执行方式1、顺序执行方式。、顺序执行方式。执行执

4、行n条指令所用的时间为：条指令所用的时间为：如果每段时间都为如果每段时间都为t，则执行则执行n条指令所用的时条指令所用的时间为：间为： T3 n t主要优点主要优点：控制简单，节省设备。：控制简单，节省设备。主要缺点主要缺点：执行指令的速度慢，功能部件的利：执行指令的速度慢，功能部件的利用率很低用率很低Ttttiiiin(取指令分析执行）1指令的重叠执行方式2、一次重叠执行方式、一次重叠执行方式一种最简单的流水线方式一种最简单的流水线方式如果两个过程的时间相等，则执行如果两个过程的时间相等，则执行n条指令的时间为：条指令的时间为： T（12n）t主要优点：主要优点：指令的执行时间缩短指令的执行

5、时间缩短功能部件的利用率明显提高功能部件的利用率明显提高主要缺点：主要缺点：需要增加一些硬件需要增加一些硬件控制过程稍复杂控制过程稍复杂指令的重叠执行方式3、二次重叠执行方式、二次重叠执行方式如果三过程的时间相等，执行如果三过程的时间相等，执行n条指令的时间为：条指令的时间为： T(2n）t在理想情况下，处理机中同时有三条指令在执行在理想情况下，处理机中同时有三条指令在执行处理机的结构要作比较大的改变，需要采用先行控制处理机的结构要作比较大的改变，需要采用先行控制技术来实现技术来实现 先行控制方式的原理1、采用二次重叠执行方式，必须解决两个问题：、采用二次重叠执行方式，必须解决两个问题：有独立

6、的取指令部件、指令分析部件和指令执行部件有独立的取指令部件、指令分析部件和指令执行部件把一个集中的指令控制器，分解成三个独立的控制器：存储控把一个集中的指令控制器，分解成三个独立的控制器：存储控制器、指令控制器、运算控制器制器、指令控制器、运算控制器要解决访问主存储器的冲突问题要解决访问主存储器的冲突问题取指令、分析指令、执行指令都可能要访问存储器取指令、分析指令、执行指令都可能要访问存储器2、解决访存冲突的方法：、解决访存冲突的方法：（1）指令和数据混合存放在同一个主存储器中，采用低）指令和数据混合存放在同一个主存储器中，采用低位交叉存取方式位交叉存取方式只有取指令、读操作数、写结果所访问的

7、不是同一个存储体时，只有取指令、读操作数、写结果所访问的不是同一个存储体时，才可能实现指令重叠才可能实现指令重叠这种方法不能根本解决冲突问题这种方法不能根本解决冲突问题(2)两个独立的存储器两个独立的存储器独立的指令存储器和数据存储器独立的指令存储器和数据存储器解决取指令和读操作数的冲突解决取指令和读操作数的冲突如果再规定，执行指令所需要的操作数和执行结果只如果再规定，执行指令所需要的操作数和执行结果只写写到通用寄存器，而不是主存。则取指令、分析指令到通用寄存器，而不是主存。则取指令、分析指令和执行指令就可以同时进行和执行指令就可以同时进行在许多高性能处理机中，有独立的指令在许多高性能处理机中

8、，有独立的指令Cache和数据和数据Cache。这种结构被称为这种结构被称为哈佛结构哈佛结构指令存储器和数据存储器分开的明显缺点：对程序员指令存储器和数据存储器分开的明显缺点：对程序员不透明不透明(3)采用先行控制技术采用先行控制技术先行控制技术的关键是缓冲技术和预处理技术先行控制技术的关键是缓冲技术和预处理技术缓冲技术是在工作速度不固定的两个功能部件之间设缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作置缓冲栈，用以平滑它们的工作在采用了缓冲技术和预处理技术之后，运算器能够专在采用了缓冲技术和预处理技术之后，运算器能够专心于数据的运算，从而大幅度提高程序的执行速度心

9、于数据的运算，从而大幅度提高程序的执行速度先行控制方式的处理机结构1、三个独立的控制器：、三个独立的控制器：存储控制器、指令控制器、运算控制器存储控制器、指令控制器、运算控制器2、四个缓冲栈：、四个缓冲栈：先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后行写数栈先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后行写数栈四个缓冲栈合在一起称为先行缓冲栈四个缓冲栈合在一起称为先行缓冲栈3、先行指令缓冲栈的组成、先行指令缓冲栈的组成只要指令缓冲栈没有充满，就自动发出取指令的请求。只要指令缓冲栈没有充满，就自动发出取指令的请求。设置两个程序计数器：设置两个程序计数器：先行程序计数器先行程序计数器PC1，用来

10、指示取指令，用来指示取指令，现行程序计数器现行程序计数器PC，记录指令分析器正在分析的指令地址记录指令分析器正在分析的指令地址4、存在的主要问题、存在的主要问题各类指令各类指令“分析分析”和和“执行执行”所需的时间相差所需的时间相差很大很大存在数据相关存在数据相关转移指令或转子程序指令转移指令或转子程序指令在本章的以下各节中，将分别介绍这三个在本章的以下各节中，将分别介绍这三个问题的解决方法问题的解决方法分分析析k k执执行行k k分分析析k k+ +1 1执执行行k k+ +1 1分分析析k k+ +2 2执执行行k k+ +2 2分分析析k k+ +3 3执执行行k k+ +3 3先行控制

11、方式的指令执行时序设置了指令缓冲栈，取指令的时间就可以设置了指令缓冲栈，取指令的时间就可以忽略不计忽略不计1、分析指令和执行指令时间不相等时的情况、分析指令和执行指令时间不相等时的情况分分析析 k k执执行行 k k分分析析 k k+ +1 1执执行行 k k+ +1 1分分析析 k k+ +2 2执执行行 k k+ +2 2分分析析 k k+ +3 3执执行行 k k+ +3 32、采用先行缓冲栈的指令执行过程、采用先行缓冲栈的指令执行过程先行读数栈先行读数栈先行操作栈先行操作栈后行写数栈后行写数栈3、指令执行过程的、指令执行过程的时空图时空图表示方法表示方法理想情况下，指令理想情况下，指令

12、执行部件执行部件应该一直忙碌应该一直忙碌连续执行连续执行n条指令的时间为：条指令的时间为：niiniitttT111执行执行分析先行 空空间间 指指令令执执行行部部件件 执执行行 k k 执执行行 k k+ +1 1 执执行行 k k+ +2 2 执执行行 k k+ +3 3 指指令令分分析析部部件件 分分析析 k k 分分析析 k k+ +1 1 分分析析 k k+ +2 2 分分析析 k k+ +3 3 时时间间 0 t1 t2 t3 t4 t5 先行缓冲栈设置先行缓冲栈的目的：设置先行缓冲栈的目的：使指令分析器和指令执使指令分析器和指令执行部件能够独立工作行部件能够独立工作。分为。分为4

13、个栈：个栈：1、先行指令缓冲栈：、先行指令缓冲栈：位置：主存储器与指令分析器之间位置：主存储器与指令分析器之间作用：作用：用它来平滑主存储器取指令和指令分析器的工作用它来平滑主存储器取指令和指令分析器的工作RR型指令：不必处理，直接送先行操作栈型指令：不必处理，直接送先行操作栈RS和和RX型指令：主存有效地址送先行读数栈，用该先型指令：主存有效地址送先行读数栈，用该先行读数栈的寄存器编号替换指令中的主存地址码部分，行读数栈的寄存器编号替换指令中的主存地址码部分，形成形成RR*指令送先行操作栈指令送先行操作栈RI型指令：指令中的立即数送先行读数栈，用该先行读型指令：指令中的立即数送先行读数栈，用

14、该先行读数栈的寄存器编号替换指令中的立即数部分，形成数栈的寄存器编号替换指令中的立即数部分，形成RR*指令送先行操作栈指令送先行操作栈转移指令：一般在指令分析器中直接执行转移指令：一般在指令分析器中直接执行2、先行操作栈、先行操作栈位置：指令分析器和运算控制器之间位置：指令分析器和运算控制器之间作用：作用：使指令分析器和运算器能够各自独立工作使指令分析器和运算器能够各自独立工作采用先进先出方式工作，由指令寄存器堆和控制逻辑采用先进先出方式工作，由指令寄存器堆和控制逻辑组成组成3、先行读数栈、先行读数栈位置：主存储器与运算器之间位置：主存储器与运算器之间作用：作用：平滑运算器与主存储器的工作平滑

15、运算器与主存储器的工作每个缓冲寄存器由地址寄存器、操作数寄存器和标志每个缓冲寄存器由地址寄存器、操作数寄存器和标志三部分组成。也可以把地址寄存器和操作数寄存器合三部分组成。也可以把地址寄存器和操作数寄存器合为一个为一个当收到从指令分析器中送来的有效地址时，就向主存当收到从指令分析器中送来的有效地址时，就向主存申请读操作数申请读操作数读出的操作数存放在操作数寄存器中或覆盖掉地址寄读出的操作数存放在操作数寄存器中或覆盖掉地址寄存器中的地址存器中的地址4、后行写数栈、后行写数栈每个后行缓冲寄存器由地址寄存器、数据寄存每个后行缓冲寄存器由地址寄存器、数据寄存器和标志三部分组成。器和标志三部分组成。指令

16、分析器遇到向主存写结果的指令，把形成指令分析器遇到向主存写结果的指令，把形成的有效地址送入后行写数栈的地址寄存器中，的有效地址送入后行写数栈的地址寄存器中，并用该地址寄存器的编号替换指令的目的地址并用该地址寄存器的编号替换指令的目的地址部分，形成部分，形成RR*指令送入先行操作栈。指令送入先行操作栈。当运算器执行这条当运算器执行这条RR*型写数指令时，型写数指令时，只要把只要把写到主存的数据送到后行写数栈的数据寄存器写到主存的数据送到后行写数栈的数据寄存器中即可中即可5 5、采用先行控制方式时，一个程序的执行情况：、采用先行控制方式时，一个程序的执行情况：指指令令地地址址 指指令令执执行行情情

17、况况 k-i-1 已已经经执执行行完完成成的的指指令令 k-i k-1 在在后后行行写写数数栈栈中中等等待待把把结结果果写写到到主主存存储储器器中中的的指指令令 k 正正在在指指令令执执行行部部件件中中执执行行的的指指令令 k+1 k+j 已已经经由由指指令令分分析析器器预预处处理理完完成成，存存放放在在先先行行操操作作栈栈中中的的R RR R* *型型指指令令，指指令令所所需需要要的的操操作作数数已已经经读读到到先先行行读读数数栈栈中中 k+j+1 k+j+n 已已经经由由指指令令分分析析器器预预处处理理完完成成，存存放放在在先先行行操操作作栈栈中中，指指令令所所需需要要的的操操作作数数还还

18、没没有有读读到到先先行行读读数数栈栈中中 k+j+n+1 正正在在指指令令分分析析器器中中进进行行分分析析和和预预处处理理的的指指令令 k+j+n+2 k+j+n+m 已已经经从从主主存存储储器器中中预预取取到到先先行行指指令令缓缓冲冲栈栈中中的的指指令令 k+j+n+m+1 还还没没有有进进入入处处理理机机的的指指令令 6 6、先行缓冲栈访问主存的优先级：先行缓冲栈访问主存的优先级： 后行写数栈 先行读数栈 先行指令缓冲栈7 7、其余缓冲栈的设计原则、其余缓冲栈的设计原则 各个缓冲栈的缓冲深度一般有如下关系：各个缓冲栈的缓冲深度一般有如下关系： DIDCDRDW 其中：其中：DI是先行指令缓

19、冲栈的缓冲深度是先行指令缓冲栈的缓冲深度 DC是先行操作栈的缓冲深度是先行操作栈的缓冲深度 DR是先行读数栈的缓冲深度是先行读数栈的缓冲深度 DW是后行写数栈的缓冲深度是后行写数栈的缓冲深度例如：例如：IBM370/165IBM370/165机：机：DI4 4，DC3 3，DR2 2，DW1 1 我国研制的两台大型计算机：我国研制的两台大型计算机： DI8 8，DCDR4 4，DW2 2 DI1212，DCDR6 6，DW2 2相关性定义定义:指一段程序的相近指令之间存在某种指一段程序的相近指令之间存在某种 关系，这种关系可能影响指令的重叠执行。关系，这种关系可能影响指令的重叠执行。分类：数据

20、相关、控制相关。分类：数据相关、控制相关。数据相关：程序在执行一条指令时指令所数据相关：程序在执行一条指令时指令所 要用要用到的指令、操作数、变址偏移量等正好是前面的到的指令、操作数、变址偏移量等正好是前面的指令的执行结果则必须等待前面指令写结果后才指令的执行结果则必须等待前面指令写结果后才能进行。能进行。控制相关：由于程序的执行方向可能被改变而引控制相关：由于程序的执行方向可能被改变而引起的相关。起的相关。数据相关性数据相关分为：数据相关分为：指令相关指令相关主存操作数相关主存操作数相关通用寄存器相关通用寄存器相关变址相关变址相关指令相关定义：定义：k：store R1,k+1 k+1: 其

21、中：结果地址（其中：结果地址（k）=指令地址（指令地址（k+1），），故称故称指令相关指令相关测试：把每条指令的结果地址与先行操作栈、指测试：把每条指令的结果地址与先行操作栈、指令分析器、先行指令缓冲栈中的所有指令地址比令分析器、先行指令缓冲栈中的所有指令地址比较，相等则有。较，相等则有。办法：不允许指令修改；通过设置专门的执行指办法：不允许指令修改；通过设置专门的执行指令把指令相关变成数据相关令把指令相关变成数据相关例：例：IBM370的执行指令：的执行指令： EXE（执行）R1X2B2D2主存操作数相关定义：定义： k: op A1,A2,A3 ;A1=(A2)op(A3) k+1: op

22、 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、通用寄存器是、通用寄存器

23、是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

24、)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、设置专用的数据通路。、设置专用的数据通路。控制相关引起控制相关的原因有：引起控制相关的原因有： 无条件转移、一

25、般条件转移、复合条件转无条件转移、一般条件转移、复合条件转移、子程序调用、中断等。移、子程序调用、中断等。吸收型指令：在指令分析器中就执行完的吸收型指令：在指令分析器中就执行完的指令。指令。无条件转移、一般条件转移是吸收型指令。无条件转移、一般条件转移是吸收型指令。本节讨论几种转移指令引起的相关。本节讨论几种转移指令引起的相关。无条件转移引起的相关程序：程序： k: JMP L : L: 分析：无条件转移是吸收型指令；分析：无条件转移是吸收型指令； 指令指令L分在先行指令缓冲栈和不在两种情况。分在先行指令缓冲栈和不在两种情况。指令执行时序：指令执行时序：分析k-1执行k-1分析k取指令L分析L

26、分析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在指令缓冲栈：转移不成功方法：降低转移成功的概率；减少转移成功的对先行控制 器的影响复合条件转移引起的相关程

27、序：程序： 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、硬件猜测：在先行指令缓冲栈入、硬件猜测：在先行指令缓冲栈入口设置指令分析器，检测转移指令，口设置指令分析器，检测转移指令， 有，则按目标地址预取有，则按目标

28、地址预取5、设置两个先行指令缓冲栈：一个、设置两个先行指令缓冲栈：一个预取转移指令下面的程序；一个预取预取转移指令下面的程序；一个预取目标程序。目标程序。6、设置专门的短循环程序的开门和、设置专门的短循环程序的开门和关门指令关门指令in循环体ii-1i0in循环体ii-1i=0in循环体ii-1i0YNNNYY一般条件转移复合条件转移原来程序5.2 流水线技术开发处理机内部的并行性方法开发处理机内部的并行性方法空间并行性空间并行性：设置多个独立的操作部件：设置多个独立的操作部件如多操作部件处理机、超标量处理机如多操作部件处理机、超标量处理机时间并行性时间并行性：采用：采用流水线技术流水线技术不

29、增加或只增加少量硬件就能使运算速度提高几倍不增加或只增加少量硬件就能使运算速度提高几倍如流水线处理机、超流水线处理机如流水线处理机、超流水线处理机本节主要内容：本节主要内容：5.2.1 流水线工作原理流水线工作原理5.2.2 流水线的分类流水线的分类5.2.3 线性流水线的性能分析线性流水线的性能分析5.2.4 非线性流水线的调度技术非线性流水线的调度技术 洗衣店的例子洗衣店的例子甩干要用甩干要用 30 分钟分钟叠衣物也需要叠衣物也需要 30 分钟分钟清洗要花清洗要花 30 分钟分钟A, B, C, D均有一些衣物要均有一些衣物要清洗，甩干，折叠清洗，甩干，折叠ABCD还要花费还要花费 30

30、分钟的时间分钟的时间将衣物放在衣柜里将衣物放在衣柜里流水线是很自然的! 洗洗4 个人的衣物，顺序操作需要个人的衣物，顺序操作需要 8 个小时个小时 如果使用流水线作业如果使用流水线作业, 将需要多少时间呢将需要多少时间呢?顺序操作任任务务顺顺序序303030BCDA时间30 3030303030303030303030306 下午下午 78910111212 上午上午流水线作业30 30任务顺序122 上午上午6 下午下午78910111时间BCDA3030 303030 流水线作业洗流水线作业洗4个人的衣物只需要个人的衣物只需要 3.5 个小时个小时!30 30任任务务顺顺序序6 下午下午7

31、89时间时间BCDA3030 303030有关流水线的问题流水线无法帮助解决流水线无法帮助解决单个任务单个任务的时间的时间, 有利于减少有利于减少整个工作整个工作全部时间全部时间吞吐量吞吐量多个任务同时操作需要多个任务同时操作需要不同的不同的资源资源可能的加速比可能的加速比 = 流水线的段数流水线的段数流水线的速率受速度流水线的速率受速度最慢的最慢的流流水段的限制水段的限制流水线各段流水线各段长度不均长度不均会降低加会降低加速比速比充满充满流水线所需的时间和流水线所需的时间和排空排空流水线所需的时间影响加速比流水线所需的时间影响加速比会由于会由于任务的相关任务的相关而造成阻塞而造成阻塞流水线工

32、作原理1、简单流水线、简单流水线流水线的每一个阶段称为流水步、流水步骤、流水段、流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节流水线阶段、流水功能段、功能段、流水级、流水节拍等拍等在每一个流水段的末尾或开头必须设置一个寄存器，在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等流称为流水寄存器、流水锁存器、流水闸门寄存器等流水锁存器会增加每条指令的执行时间，但采用流水线水锁存器会增加每条指令的执行时间，但采用流水线之后整个程序的执行时间会缩短之后整个程序的执行时间会缩短为了简化，在一般流水线中不画出流水锁存器

33、。为了简化，在一般流水线中不画出流水锁存器。输输入入指指令令分分析析器器分分析析 k k+ +1 1流流水水锁锁存存器器指指令令执执行行部部件件执执行行 k k流流水水锁锁存存器器输输出出t t1t t2流水线工作原理2、流水线的表示方法、流水线的表示方法流水线的连接图表示方法流水线的连接图表示方法表示流水线的逻辑关系表示流水线的逻辑关系 输输入入 取取指指令令 译译码码 形形成成操操作作 数数地地址址 取取操操作作数数 执执行行 保保存存结结果果 输输出出 1 1 2 2 3 3 4 4 5 5 6 6 流水线的时空图表示方法流水线的时空图表示方法 表示流水线的时间关系表示流水线的时间关系

34、流水线的预约表表示方法流水线的预约表表示方法 将在将在非线性流水线非线性流水线中介绍中介绍 一般处理机的指令流水线为一般处理机的指令流水线为 4 4 至至 12 12 个级个级 指令流水线等于和大于指令流水线等于和大于8 8级的称为级的称为超流水线处理机超流水线处理机一个浮点加法器流水线的时空图一个浮点加法器流水线的时空图由由求阶差、对阶、尾数加和规格化求阶差、对阶、尾数加和规格化4 4个流水段组成个流水段组成3 3、流水线时空图、流水线时空图一条一条简单流水线的时空图简单流水线的时空图 空空间间 指指令令执执行行部部件件 执执行行k k 执执行行k k+ +1 1 执执行行k k+ +2 2

35、 执执行行k k+ +3 3 指指令令分分析析部部件件 分分析析k k 分分析析k k+ +1 1 分分析析k k+ +2 2 分分析析k k+ +3 3 0 t1 t2 t3 t4 t5 时时间间 空空间间 规规格格化化 规规格格化化1 1 规规格格化化2 2 规规格格化化3 3 规规格格化化4 4 规规格格化化5 5 尾尾数数加加 尾尾数数加加1 1 尾尾数数加加2 2 尾尾数数加加3 3 尾尾数数加加4 4 尾尾数数加加5 5 对对 阶阶 对对阶阶1 1 对对阶阶2 2 对对阶阶3 3 对对阶阶4 4 对对阶阶5 5 求求阶阶差差 求求阶阶差差1 1 求求阶阶差差2 2 求求阶阶差差3

36、3 求求阶阶差差4 4 求求阶阶差差5 5 0 t1 t2 t3 t4 t5 t6 t7 t8 时时间间 4、流水线的主要特点、流水线的主要特点只有连续提供同类任务才能充分发挥流水线的效率只有连续提供同类任务才能充分发挥流水线的效率对于指令流水线：要尽量减少因条件分支造成的对于指令流水线：要尽量减少因条件分支造成的“断流断流”对于操作部件：主要通过编译技术，尽量提供连续的相同对于操作部件：主要通过编译技术，尽量提供连续的相同类型的操作。类型的操作。在流水线的每一个流水线段中都要设置一个流水锁存器。在流水线的每一个流水线段中都要设置一个流水锁存器。时间开销：流水线的执行时间加长，时间开销：流水线

37、的执行时间加长，是流水线中需要增加的主要硬件之一。是流水线中需要增加的主要硬件之一。各流水段的时间应尽量相等各流水段的时间应尽量相等流水线处理机的基本时钟周期等于时间最长的流水段的时间长度流水线处理机的基本时钟周期等于时间最长的流水段的时间长度流水线需要有流水线需要有“装入时间装入时间”和和“排空时间排空时间”Latency & throughput? 流水线技术在流水线技术在50年代后期被应用于处理器年代后期被应用于处理器IBM Stretch-first general-purpose pipelined computerCDC 6600 use load/store design

38、 to achieve efficient pipelining.流水线的分类1、线性流水线与非线性流水线、线性流水线与非线性流水线流水线的各个流水段之间是否有反馈信号流水线的各个流水段之间是否有反馈信号线性流水线（线性流水线（Linear Pipelining）每一个流水段都流过一次，而且仅流过一次每一个流水段都流过一次，而且仅流过一次线性流水线能够用流水线连接图唯一表示线性流水线能够用流水线连接图唯一表示非线性流水线（非线性流水线（Nonlinear Pipelining）在流水线的某些流水段之间有反馈回路或前馈回路。在流水线的某些流水段之间有反馈回路或前馈回路。非线性流水线必须用流水线连

39、接图流水线预约表等共同表示非线性流水线必须用流水线连接图流水线预约表等共同表示2、按照流水线的级别来分、按照流水线的级别来分处理机级流水线，又称为处理机级流水线，又称为指令流水线指令流水线例如：在采用先行控制器的处理机中，各功能部件之例如：在采用先行控制器的处理机中，各功能部件之间的流水线间的流水线 部件级流水线，即部件级流水线，即操作流水线操作流水线。如浮点加法器流水线。如浮点加法器流水线处理机之间的流水线称为处理机之间的流水线称为宏流水线宏流水线（Macro Pipelining）每个处理机对同一个数据流的不同部分分别进行处理每个处理机对同一个数据流的不同部分分别进行处理3、单功能流水线与

40、多功能流水线、单功能流水线与多功能流水线单功能流水线：只能完成一种固定功能的流水单功能流水线：只能完成一种固定功能的流水线线Cray-1计算机种有计算机种有12条条YH-1计算机有计算机有18条条Pentium有一条有一条5段的定点和一条段的定点和一条8段的浮点流水线段的浮点流水线Pentium有两条定点指令流水线，一条浮点指令有两条定点指令流水线，一条浮点指令流水线。流水线。多功能流水线：流水线的各段通过不同的连接多功能流水线：流水线的各段通过不同的连接实现不同的功能实现不同的功能Texas公司的公司的ASC计算机中的计算机中的8段流水线，能够实现：段流水线，能够实现： 定点加减法、定点乘法

41、定点加减法、定点乘法 浮点加法、浮点乘法浮点加法、浮点乘法 逻辑运算、移位操作逻辑运算、移位操作 数据转换、向量运算等数据转换、向量运算等 A B A B A B A B输 入输 入输 入输 入求 阶 差求 阶 差求 阶 差求 阶 差对 阶对 阶对 阶对 阶尾 数 加尾 数 加尾 数 加尾 数 加规 格 化规 格 化规 格 化规 格 化尾 数 乘尾 数 乘尾 数 乘尾 数 乘累 加累 加累 加累 加输 出输 出输 出输 出g=f(A,B)定 点 乘浮 点 加浮 点 点 积(a)功 能 段 间 的 互 连 (b)定 点 乘 法 (c)浮 点 加 法 (d)浮 点 点 积4、静态流水线与动态流水线

42、、静态流水线与动态流水线静态流水线静态流水线：同一段时间内，多功能流水线中的各个功能：同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能段只能按照一种固定的方式连接，实现一种固定的功能只有连续出现同一种运算时，流水线的效率才能得到充分的发挥只有连续出现同一种运算时，流水线的效率才能得到充分的发挥空空间间浮浮点点加加法法定定点点乘乘法法输出1 12 23 3 n n- -1 1 n n1 1累加1 12 2尾数乘1 12 23 3规格化1 12 23 3 n n- -1 1 n n尾数加1 12 23 3 n n- -1 1 n n对阶1 12 23 3 n

43、n- -1 1 n n求阶差1 12 23 3 n n- -1 1 n n输入1 12 23 3 n n- -1 1 n n1 12 23 34 4时时间间静静态态流流水水线线时时空空图图动态流水线动态流水线：在同一段时间内，多功能流水线：在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行中的各段可以按照不同的方式连接，同时执行多种功能多种功能 空空间间 浮浮点点加加法法 定定点点乘乘法法 输输入入 1 1 2 2 3 3 n n- -1 1 n n 1 1 2 2 3 3 求求阶阶差差 1 1 2 2 3 3 4 4 对对阶阶 1 1 2 2 3 3 4 4 5 5 尾尾数

44、数加加 1 1 2 2 3 3 n n- -1 1 n n 规规格格化化 1 1 2 2 3 3 n n- -1 1 n n 尾尾数数乘乘 1 1 2 2 3 3 n n- -1 1 n n 累累加加 1 1 2 2 3 3 n n- -1 1 n n 输输入入 1 1 2 2 3 3 n n- -1 1 n n 1 1 2 2 3 3 4 4 5 5 6 6 时时间间 动动态态流流水水线线时时空空图图 5、流水线的其他分类方法、流水线的其他分类方法按照数据表示方式：标量流水线和向量流水线按照数据表示方式：标量流水线和向量流水线按照控制方式：同步流水线和异步流水线按照控制方式：同步流水线和异步

45、流水线顺序流水线与乱序流水线顺序流水线与乱序流水线乱序流水线又称为无序流水线、错序流水线或异步流水线等乱序流水线又称为无序流水线、错序流水线或异步流水线等 输入输入 就绪就绪 回答回答 S1 就绪就绪 回答回答 S2 就绪就绪 回答回答 Sn 输出输出 就绪就绪 回答回答 一种异步流水线 线性流水线的性能分析 衡量流水线性能的主要指标有：衡量流水线性能的主要指标有：吞吐率、加速比和效率。1、吞吐率（Though PutThough Put） 计算流水线吞吐率的最基本公式： 其中：其中：n n为任务数，为任务数，k k为完成为完成n n个任务所用的时间。个任务所用的时间。 各段执行时间相等，输入

46、连续任务情况下：各段执行时间相等，输入连续任务情况下： 完成完成n n个连续任务需要的总时间为：个连续任务需要的总时间为：Tk（kn1）t 其中：其中：k 为流水线的段数，为流水线的段数， t t为时钟周期。为时钟周期。 空空间间S4123n-1nS3123n-1nS2123n-1nS11 12 23 3n n- -1 1n n时时间间kt(n1)tnt(k1)tTT PnTk 吞吐率为： 最大吞吐率为： 各段执行时间不相等，输入连续任务情况下： 吞吐率为： 最大吞吐率为： 流水线各段执行时间不相等的解决办法TPnknt() 1 nTPLimnkntt max() 11TPntntttiikk

47、1121() m ax(,),max(121ktttTP 输入输入S1S2S3S4输出输出 t1 t t23 t t3 t t4 t (1)将流水线的“瓶颈”部分再细分（如果可分的话）。空空间间S4123nS3123nS2123nS1123n时时间间 kiit1（n1） t2Tk各段执行时间不相等的流水线及其时空图输输入入S1S2-1S2-2S2-3S3S4输输出出 t t t t t t“瓶瓶颈颈”流流水水段段再再次次细细分分 S2 (3 t)( (2 2) )“瓶瓶颈颈“流流水水段段重重复复设设置置：增加分配器和收集器S2-3输输入入S1S2-2S3S4输输出出 t1 t t3 t t4

48、tS2-1 t23 t空空间间S4123456n-2 n-1nS3123456n-2 n-1nS2-336nS2-225n-1S2-114n-2S1123456n-2 n-1n时时间间流流水水段段重重复复设设置置的的流流水水线线2、加速比（SpeedupSpeedup） 计算流水线加速比的基本公式： 各段执行时间相等，输入连续任务情况下：各段执行时间相等，输入连续任务情况下： 加速比为：加速比为： 最大加速比为：最大加速比为：各段执行时间不相等，输入连续任务情况下各段执行时间不相等，输入连续任务情况下, , 实际加速比为：实际加速比为：STTk顺序执行时间流水线执行时间0Sk ntkntk n

49、kn () 11SLimk nknknmax1Snttntttiikiikk 11121() max(, ,） 当流水线段数增加时，需要连续输入的任务数也必须增加当流水线段数增加时，需要连续输入的任务数也必须增加 加加速速比比 S 10 加加 k=10 段段 8 速速 6 比比 k=6 段段 4 2 1 1 2 4 8 16 32 64 128 n 任任 务务 个个 数数3 3、效效率率（Efficiency） 计计算算流流水水线线效效率率的的一一般般公公式式：EnkTk Tk个任务占用的时空区个流水段的总的时空区0 各流水段执行时间相等，输入n个连续任：流水线的效率为：Ek ntk kntn

50、kn () 11流水线的最高效率为：ELimnknnmax 11 各流水段执行时间不相等，输入n个连续任：流水线效率为：Entktntttiikiikk 11121) max(, ,)（ 流水线各段的设备量或者各段的价格不相等时：流流水水线线的的效效率率为为：E空区个流水段的总的加权时区个任务占用的加权时空kn即：), ,max() 121111nkiikiikiiitttntatanE（其中，aik，且aiik1k。 流流水水线线的的吞吞吐吐率率、加加速速比比与与效效率率的的关关系系：因为：TPnknt() 1 ，1nknkS，Enkn1 因此：ETPt，SkE4、流水线最佳段数的选择 采用

51、顺序执行方式完成一个任务的时间为采用顺序执行方式完成一个任务的时间为t t 在同等速度的在同等速度的k段流水线上执行一个任务的时间为：段流水线上执行一个任务的时间为：tkd 其中：其中：d为流水锁存器的延迟时间为流水锁存器的延迟时间 流水线的最大吞吐率为：流水线的最大吞吐率为： 流水线的总价格估计为：流水线的总价格估计为：Cab k， 其中：其中：a为所有功能段本身的总价格，为所有功能段本身的总价格，b为每个锁存器的价格为每个锁存器的价格 A.G.Larson把流水线的性把流水线的性 能价格比能价格比PCR定义为：定义为： 求得到求得到PCR的最大值为：的最大值为：Ptkd1/PCRPCt k

52、d abk11/ktadb0 性能价格比PCR 峰值 最佳值(k0) 流水线段数k5、流水线性能分析举例 对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。容易计算出流水线的吞吐率、加速比和效率。例：用一条用一条4 4段浮点加法器流水线求段浮点加法器流水线求8 8个浮点数的和：个浮点数的和： Z ZA AB BC CD DE EF FG GH H解：Z Z （A AB B）（）（C CD D） （E EF F）（）（G GH H） 000)()()(0)(1)(0)1/1(2222

53、kbdatkbdbtkkbdadkkbdbtkadkatdktbkbkadkbkadktbkadktkbkadktdbtak 空间空间 周期周期 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 1111 1212 1313 1414 1515 规格化规格化 1 1 2 2 3 3 4 4 5 5 6 6 7 7 尾数加尾数加 1 1 2 2 3 3 4 4 5 5 6 6 7 7 对阶对阶 1 1 2 2 3 3 4 4 5 5 6 6 7 7 求阶差求阶差 1 1 2 2 3 3 4 4 5 5 6 6 7 7 时间时间 加数加数 A C E G A+B E

54、+F A+B+C+DA C E G A+B E+F A+B+C+D 加数加数 B D F H B D F H C+D G+H E+F+G+H C+D G+H E+F+G+H 结果结果 A+B C+D E+F g+H A+B+C+D Z A+B C+D E+F g+H A+B+C+D Z E+F+G+HE+F+G+H 用一条用一条 4 4 段浮点加法器流水线求段浮点加法器流水线求 8 8 个数之和的流水线时空图个数之和的流水线时空图 7 个个浮浮点点加加法法共共用用了了 15 个个时时钟钟周周期期。 流流水水线线的的吞吞吐吐率率为为：TPnTttk7150 471 流流水水线线的的加加速速比比为

55、为：STTttk 047151 87 流流水水线线的的效效率率为为：ETk Tttk 0474 150 47 流水线工作原理流水线的分类线性流水线的性能分析非线性流水线的调度技术 标量处理机标量处理机流水线技术流水线技术非线性流水线的调度技术 非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。1、非线性流水线的表示 线性流水线能够用流水线连接图唯一表示线性流水线能够用流水线连接图唯一表示 连接图不能用唯一表示非线性流水线的工作流程，因此，引入流水线连接图不能用唯一表示非线性流水线的工作流程，因此，引入

56、流水线预约表预约表时时间间功功能能段段1234567S1S2S3S4 输输出出输输入入S1S2S3S4前馈线反馈线 与流水线预约表对应的流水线连接图与流水线预约表对应的流水线连接图时时 间间功功 能能 段段1234567S1S2S3S4 输输出出S4输输入入S1S2S3前前馈馈线线反反馈馈线线 输输出出输输入入S1S2S3S4前馈线反馈线 一张预约表可能与多个流水线连接图相对应一张预约表可能与多个流水线连接图相对应时时间间功功能能段段1234567S1S2S3S4 输输出出输输入入S1S2S3S4前馈线反馈线 一个流水线连接图对应与多张预约表一个流水线连接图对应与多张预约表时时间间功功能能段段

57、1 12 23 34 45 56 67 7S1S2S3S42、非线性流水线的冲突 流水线的启动距离：连续输入两个任务之间的时间间隔 流水线的冲突：几个任务争用同一个流水段几个任务争用同一个流水段启启动动距距离离为为 3 3 的的流流水水线线冲冲突突情情况况时时间间功功能能段段1 12 23 34 45 56 67 78 89 91 10 01 11 1S1X X1 1X X1 1X X2 2X X1 1X X2 2X X3 3X X2 2X X3 3X X4 4S2X X1 1X X1 1X X2 2X X2 2X X3 3X X3 3X X4 4S3X X1 1X X2 2X X1 1X X

58、3 3X X2 2X X4 4S4X X1 1X X2 2X X3 3启启动动距距离离为为 2 2 的的流流水水线线冲冲突突情情况况 时时间间 功功能能段段 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 1 11 1 S S1 1 X X1 1 X X2 2 X X1 1 X X3 3 X X2 2 X X1 1X X4 4 X X3 3 X X2 2X X5 5 X X4 4 X X3 3X X6 6 S S2 2 X X1 1 X X2 2 X X1 1 X X3 3 X X2 2 X X4 4 X X3 3 X X5 5 X X4 4 S S3 3

59、 X X1 1 X X2 2 X X1 1X X3 3 X X2 2X X4 4 X X3 3X X5 5 S S4 4 X X1 1 X X2 2 X X3 3 X X4 4 X X5 5 启启动动距距离离为为 5 5 时时的的流流水水线线不不冲冲突突时时间间功功能能段段1 12 23 34 45 56 67 78 89 91 10 01 11 1S S1 1X X1 1X X1 1X X2 2X X1 1X X2 2X X3 3S S2 2X X1 1X X1 1X X2 2X X2 2S S3 3X X1 1X X1 1X X2 2X X2 2S S4 4X X1 1X X2 2启启动动

60、周周期期重重复复启启动动周周期期启启动动距距离离为为( (1 1, ,7 7) )循循环环时时的的流流水水线线预预约约表表时时间间功功能能段段1 12 23 34 45 56 67 78 89 91 10 01 11 11 12 21 13 31 14 41 15 51 16 6S S1 1X X1 1X X2 2X X1 1X X2 2X X1 1X X2 2X X3 3X X4 4X X3 3X X4 4X X3 3X X4 4S S2 2X X1 1X X2 2X X1 1X X2 2X X3 3X X4 4X X3 3X X4 4S S3 3X X1 1X X2 2X X1 1X X2 2X