标量流水线技术

1、标量流水线技术第1页，共87页，2022年，5月20日，22点58分，星期四第4章 标量流水线技术4.1 概述4.2 标量流水线工作原理4.3 指令级流水线第2页，共87页，2022年，5月20日，22点58分，星期四4.1 概述4.1.1 控制流及其改变4.1.2 程序执行过程中的重叠操作与先 行控制第3页，共87页，2022年，5月20日，22点58分，星期四4.1.1 控制流及其改变 所谓控制流是指被执行的指令序列的处理顺序，其地址由程序计数器PC给出，一条接着一条地执行。在一般情况下，PC的值是时间的单调函数，如图4.1（a） 所示。但是当遇上转移类指令时，控制流将发生间断，转移到目标

2、地址后又顺序执行，PC中的值如图4.1（b） 所示。通常，改变程序顺序执行的因素有多种，常见的有以下4种。图4.1 程序计数器PC与时间t的关系 第4页，共87页，2022年，5月20日，22点58分，星期四（1）转移指令 转移指令可分为无条件转移和条件转移两种类型，且有多条，都是把转移目标地址送入程序计数器PC中，然后又顺序执行，如图4.1（b）所示。（2）过程调用与返回 即执行被调用的过程或子程序，其入口地址送入PC中；返回时，返回地址送入PC，另外还有嵌套和递归。 （3）协同程序 协同程序与过程调用程序有所不同，它是被调用过程未必从头开始执行，而是从上一次返回的位置开始，如图4.2所示。

3、 （4）中断与自陷 中断是由外部事件引起，自陷是由CPU的内部原因引起，CPU执行中断服务程序，执行完后返回原来被中断的程序。 以上几种情况都改变PC中的值，使控制流发生改变。图4.2 协同程序改变控制流第5页，共87页，2022年，5月20日，22点58分，星期四4.1.2 程序执行过程中的重叠操作与先行控制 1.程序执行过程中的重叠操作 在计算机运行的过程中，指令的解释方式可分为三种，即顺序、重叠和流水，依据不同的解释方式，可以产生不同的工作方式和过程。下面仅介绍顺序解释方式和重叠解释方式，流水线方式将在第4.2节介绍。（1）顺序解释方式 顺序解释是最简单的一种方式，它是一条指令执行完后再

4、去解释下一条指令。早期的计算机多采用这种方式，指令执行过程分为取指令、分析（译码）和执行三个阶段，顺序进行，其示意如图4.3 所示。图4.3 顺序执行方式 第6页，共87页，2022年，5月20日，22点58分，星期四 若取指令、分析和执行所用的时间（周期）相等，设为t，则顺序解释执行n条指令所需要的时间T=3nt。如果各部分时间表示为t取指、t分析和t执行，则顺序执行n条指令所用的时间为：（2）重叠解释方式是在两条相邻指令的解释过程中，存在某些时段可以重叠进行，其示意如图4.4所示。图4.4 重叠执行方法 T=(t取i+t分i+t执i)ni=1（4.1）第7页，共87页，2022年，5月20

5、日，22点58分，星期四图4.5 两阶段一次重叠工作方式图(a)是一次重叠方式，执行n条指令所用的时间为：T=(2n+1)t；图(b)是二次重叠方式，执行n条指令所用的时间为： T=3t+(n-1)t=(n+2)t。 为实现重叠解释方式，需要硬件支持，比如设置指令缓冲寄存器或称指令队列。又如程序与数据分别存储，以便分别迅速读取操作数。 若指令的解释过程可分为两个段，上述重叠解释过程可如图4.5所示。如果“分析”和“执行”的时间相同，那么解释执行n条指令的时间为： T=(n+1)t。第8页，共87页，2022年，5月20日，22点58分，星期四2.先行控制 在上述重叠解释方式中假设“分析”和“执

6、行”的时间相等，但是实际的解释执行过程中，“分析”和“执行”的时间往往不相等，如图4.6(a)所示，这样解释执行n条指令的时间为：T=t分max(t分i，t执i-1)+t执nni=2(4.2)图4.6 分析与执行时间不相等和先行控制方式第9页，共87页，2022年，5月20日，22点58分，星期四为解决重叠过程中的“空闲”，可采用先行控制技术，使“分析”和“执行”分别连续进行，如图4.6（b）所示。这时，执行n条指令所需要的时间为：ni=1T先行=t分t执i(4.3)图4.6 分析与执行时间不相等和先行控制方式第10页，共87页，2022年，5月20日，22点58分，星期四 为了实现“分析”和

7、“执行”分别连续进行，8086微处理器把CPU分为总线接口部件和执行部件，且设置一个指令队列，可在执行第k条指令时由总线接口部件预取第k+1、k+2甚至k+2条指令。 图4.7 先行控制逻辑 以上可见，先行控制技术实质上是预取处理技术和缓冲技术的结合，缓冲部件一般采用先进先出寄存器，其个数称为缓冲深度。先行控制逻辑如图4.7所示，其中缓冲区的深度一般应满足以下关系：D取指栈D操作数D读栈D写栈第11页，共87页，2022年，5月20日，22点58分，星期四4.2 标量流水线工作原理4.2.1 标量流水线工作原理4.2.2 标量流水线分类4.2.3 流水线性能分析4.2.4 流水线中的主要障碍4

8、.2.5 流水线的实现与控制4.2.6 流水线的动态调度第12页，共87页，2022年，5月20日，22点58分，星期四4.2.1 标量流水线工作原理1.标量流水线工作原理如果能把指令的执行过程细分为五个部分，如图4.8 所示。这五个部分由相应的硬件来实现，因此也称为五个子过程或状态，用Si表示。这样，前一条指令只要走出第一子过程，就可以读取下一条指令。于是，构成标量流水线工作方式。 图4.8 流水过程示意图 第13页，共87页，2022年，5月20日，22点58分，星期四 设每一子过程时间相同，指令流入，经过五个子过程后从输出端流出，若用二维坐标表示，即可构成如图4.9所示时空图，即空间与时

9、间之间的二维关系图。在理想情况下每经一个时钟周期指令向右移动一格，新的指令从左边进入。经过4个时钟周期后五个部件全部工作，其中前4个时钟周期称为填入阶段；以后，称为填满，即正常工作；最后，各条指令一一退出，称为排空阶段。 若用m表示部件或空间段数，整个时间可为两个部分。mt是第一条指令流出时间，即流出第一个结果的时间；以后（n-1）t中，每经一拍流出一个结果。 图4.9 流水线各段组成与时空图 第14页，共87页，2022年，5月20日，22点58分，星期四 2.流水线工作特点 概括起来，流水线的工作特点主要有以下几点： （1）一条流水线通常由多个流水段组成； （2）在每一个流水段有专门的功能

10、部件，对指令进行某 种加工处理； （3）流水线的工作一般分为三个阶段，即建立（填入）、填满和排空； （4）在理想情况下，各流水段所需要的时间是相等的，流水线填满后每隔t时间就会有一个结果流出流水线。第15页，共87页，2022年，5月20日，22点58分，星期四4.2.2 标量流水线分类 处理机流水线是一种宏流水过程，其中每一个处理机完成某一专门的任务，各处理机产生的结果存放到与下一个处理机共享存储器中，如图4.10所示。 图4.10 处理机流水线 从不同的角度来看，有不同的分类方式，大致有以下几类。 1. 按照处理机分类 按照处理机分类，流水线可以分为操作部件级、指令级和处理机级。 操作部件

11、级流水线是按复杂的算术逻辑运算的过程构成流水线，比如把浮点加法运算分成求阶差、对阶、尾数相加和结果规格化四个子过程。 指令级流水线是把一条指令的解释执行过程分成若干个子过程，比如前面所说的取指令、译码、执行、访存和写回五个子过程。第16页，共87页，2022年，5月20日，22点58分，星期四2. 按照功能分类 按功能可分为单功能流水线和多功能流水线两种。单功能流水线是所有设备按照一种模式工作，仅完成一种功能；多功能流水线是指构成流水线的设备可不同组合，在不同的时间完成不同功能。图4.11所示是TI-ASC计算机的流水结构，可构成多种流水线，比如定点加、浮点加、定点乘和浮点向量点积等。第17页

12、，共87页，2022年，5月20日，22点58分，星期四图4.11 多功能流水线的多种连接 第18页，共87页，2022年，5月20日，22点58分，星期四 3. 按照工作方式分类 按工作方式可分为静态和动态流水线。静态流水线是在同一时间内只能以一种方式工作。其结构可以是单功能，也可以是多功能。其中多功能结构的流水线在同一时间只能进行一种工作；在从一种功能转换成另一种功能时流水线必须排空。一般不希望流水线功能频繁切换。 动态流水线则允许在同一时间内将不同的功能段连接成不同的子流水线集，以完成不同的运算功能。 显然，动态流水线必定是多功能流水线；单功能流水线必定是静态流水线。第19页，共87页，

13、2022年，5月20日，22点58分，星期四4. 按照连接方式分类 可分为线性流水线和非线性流水线。所谓线性流水线是指从输入到输出各功能部件只允许经过一次，没有反馈回路或者分支。非线性流水线是某些功能部件可能被反复使用，如图4.12所示，S3的输出可反馈到S2，S4的输出可反馈到S1。显然存在功能段使用冲突。 图4.12 非线性流水线示意图 第20页，共87页，2022年，5月20日，22点58分，星期四流水线性能分析 目前，衡量流水线性能的技术指标主要有三个，即吞吐率、效率和加速比。 1.吞吐率Tp 吞吐率是指单位时间内处理机所能处理的任务数或者输出的结果数，可分为最大吞吐率和实际吞吐率。（

14、1）最大吞吐率若以ti表示通过流水线各功能段所用的时间，那么在流水线稳定后可获得的最大吞吐率可表示为：显然，ti最大的一段将成为流水线的瓶颈。如果段的ti相差不大，则属于正常流水线。一般需要采取一定的措施，使各段的ti趋于一致。(4.4)Tpmax=1max(ti)ni=1第21页，共87页，2022年，5月20日，22点58分，星期四（2）流水线中的瓶颈 如图4.13(a)所示，由4个功能段构成流水线，其中通过第1、2、4段所用的时间为t，通过第3段所用的时间为3t，则时空图如图4.13(b)所示。显然，最大吞吐率将降为Tpmax=1/(3t)。图4.13 带瓶颈流水线及其消除时空图第22页

15、，共87页，2022年，5月20日，22点58分，星期四（3）消除瓶颈影响的方法 为消除瓶颈影响可采取相应的措施，比如把第3段细分，使之成为3段，每段所用的时间近乎于t，如图4.13(c)所示。这样，可使6个任务依次进入流水线，使最大吞吐率仍然保持为Tpmax=1/t。图4.13 带瓶颈流水线及其消除时空图第23页，共87页，2022年，5月20日，22点58分，星期四 也可采用空间重复因素，增设2个第3段，并列工作，如图4.13(d)所示。这样，连续的3个任务可分别通过S3a、S3b和S3c，其时空图如图4.13(e)所示。可在一定程度上减轻瓶颈引起的吞吐率下降。图4.13 带瓶颈流水线及其

16、消除时空图 续第24页，共87页，2022年，5月20日，22点58分，星期四(4.5)Tp= = =nmt+(n-1)t1t1+(m-1)/nTpmax1+(m-1)/n(4.6)Sp= = = = mt+(n-1)t1+(m-1)/nToTknmtnmm+n-1m （4）实际吞吐率 任何一个流水线都存在填入和排空过程，因此实际吞吐率总是小于最大吞吐率。设m为流水线中功能段数，从图4.9可以看出，完成n个任务所用的时间为： T=mt+(n-1)t 则实际吞吐率为：显然，当nm时，TpTpmax。 2.加速比Sp 加速比是指执行同一任务时不采用流水线技术所用的时间与采用流水线方式所用的时间之比

17、。对于n个任务，设有m段流水线。若不采用流水线，所用的时间为To，采用流水线后使用的时间为Tk，则加速比为：显然，nm时，Spm，即最大加速比。m增大，加速比提高。第25页，共87页，2022年，5月20日，22点58分，星期四 E= = = = n个任务占用时空区面积m段流水线总时空区面积m(m+n-1)tnmtnm+n-1Spm(4.7) 3.效率E 效率是指流水线中各功能段的时间利用率，也就是各功能段被实际利用的时空区与各功能段所提供总的时空区面积之比。如图4.9所示，效率可表示为： 图4.9 流水线各段组成与时空图 第26页，共87页，2022年，5月20日，22点58分，星期四 图4

18、.14 双功能静态流水线 【例4.1】流水线性能分析。设有A、B两个向量，每个向量有4个元素，要求在如图4.14所示的静态加、乘双功能流水线上计算 ，并求吞吐率、加速比和效率。第27页，共87页，2022年，5月20日，22点58分，星期四 解：在流水线中，由功能段S1、S2、S3、S4、S6构成乘法流水线，S1、S5、S6构成加法流水线。设经过每一个功能段的时间均为t，流水线的输出可直接返回输入端或者暂存到缓冲寄存器中，流水线功能切换时间忽略不计。为了在最短的时间内完成上述运算，可让流水线先进行两个向量中4个元素的加法运算，即求(a0+b0)、(a1+b1)、(a2+b2)、(a3+b3)；

19、然后切换成乘法功能，再按照(a0+b0)(a1+b1)(a2+b2)(a3+b3)的顺序进行三次乘法运算。根据分析，可画出流水线的时空图，如图4.15 所示。 从图中可以看出，在17t时间内输出了7个结果，因此实际吞吐率为： Tp=7/17t 顺序操作，则需要作4次加法运算和3次乘法运算。一次加法运算需要3t，一次乘法运算需要5t，总共需要To=43t+35t=27t。这样加速比为： Sp=To/Tp=27t/17t=1.88 流水线的效率可用阴影面积除以全部6个状态段的总时空面积而求得： E=(34t+53t)/(617t)=27/102=26.4%第28页，共87页，2022年，5月20日

20、，22点58分，星期四 图4.15 流水线时空图举例 第29页，共87页，2022年，5月20日，22点58分，星期四4.2.4 流水线中的主要障碍 在实际应用中，往往有这样或者那样的原因使流水线不能畅通，概括起来有三种：资源相关、数据相关和控制相关。 仍设流水线有五个功能段S1S5（IF、ID、EXE、MEM、WB）。但不同指令在流过时对流水线的使用不同。下面以ALU、LOAD和STORE、BRANCH指令为例，予以说明。 （1）ALU类指令 在S1取出，S2译码，S3执行，S4不进行任何操作，在S5把执行结果写回目标寄存器堆。 （2）传送类指令LOAD和STORE 在S1取出，S2译码及读

21、寄存器堆，S3计算有效地址，S4访问存储器： LOAD指令在S4读存储器，并送数据寄存器，在S5把读出的数据写回寄存器堆； STORE指令仅在S4把数据寄存器中的数据写入目标存储器单元。第30页，共87页，2022年，5月20日，22点58分，星期四 （3）分支转移类BRANCH 在S1取出，S2译码并读寄存器堆，S3生成转移目标地址，并形成条件码，S4判断条件，若成立，则将转移地址送入程序计数器PC；S5不进行任何操作。 三类指令对各功能段的占用如表4.1所示。表4.1 三类指令对流水线的使用 指令功能段)ALU指令LOAD/STOREBRANCHIf(S1)取指取指取指ID(S2)译码 读

22、寄存器堆译码 读寄存器堆译码 读寄存器堆EX(S3)执行计算有效地址计算转移目标地址 设置条件码MEM(S4)访存（读或写）若条件成立 转移目标地址送PCWB(S5)结果写回寄存器堆读出数据写入寄存器堆第31页，共87页，2022年，5月20日，22点58分，星期四 1.资源相关 也称为资源或结构冲突。如图4.16所示，有5条指令相继进入流水线，其中第1条指令是存储器读LOAD。在时钟周期T4第1条指令执行到MEM段，和第i+3条指令的IF段发生冲突，即资源相关。 图4.16 两条指令同时访问存储器冲突 第32页，共87页，2022年，5月20日，22点58分，星期四图4.17 用停顿的方法解

23、决存储器冲突为了解决冲突，故在取第i+3条指令时暂停一拍，如图4.17所示。第33页，共87页，2022年，5月20日，22点58分，星期四2.数据相关(1) 数据相关往往发生在两条指令执行中，后一条指令所需要的操作数正好是前一条指令执行的结果。如有以下两条指令，其执行过程如图4.18所示。ADD R1，R2，R3 ；R2+R3R1SUB R4，R1，R5 ；R1-R5R4SUB指令需要在第3拍使用前一条ADD的执行结果，而ADD指令的结果要在第5拍时才能写入寄存器R1中。即读超前于写（RAW）。图4.18 数据相关冲突 第34页，共87页，2022年，5月20日，22点58分，星期四图4.1

24、9 加法运算结果定向传送（2）解决办法 可采用“定向传送”技术，也称为旁路技术或相关专用通路技术。如图4.19 所示，第一条指令ADD需在WB段才能把结果写回到R1中，而后继指令中除了XOR之外都要在此之前使用。若采用停顿法，需停顿3拍。而ADD指令则是在EX段就已产生了运算结果，因此可直接传送给后续的SUB、AND和OR指令的EX段。第35页，共87页，2022年，5月20日，22点58分，星期四 定向传送示意如图4.20(a)所示，定向传送的实现如图4.20(b)所示，即增加旁路，实现运算结果的定向传送。当然，这种方式将增加电路的复杂性。 图4.20 旁路定向传送 第36页，共87页，20

25、22年，5月20日，22点58分，星期四图4.19 加法运算结果定向传送在有些计算机中把时钟周期分为前半周期和后半周期。读操作一般在后半周期进行，写操作一般在前半周期进行。这样，对于图4.19所示的指令OR的定向传送可以取消，如图4.21所示。第37页，共87页，2022年，5月20日，22点58分，星期四 图4.21 减少定向传送措施 第38页，共87页，2022年，5月20日，22点58分，星期四 （3）数据相关类型 数据相关有三种类型，即RAW、WAR、WAW： RAW：是指令j试图在指令i写入寄存器之前读取寄存器中的数据，这样指令j读出的就是其原来的内容，简称为读超前于写。 WAR：是

26、指令j试图在指令i读出寄存器中的数据之前写入寄存器，这样指令i读出的就是寄存器中的新内容，简称为写超前于读。 WAW：是指令j试图在指令i写入寄存器之前写入寄存器，这样两条指令的写入过程颠倒，简称为j写超前于i写。（4）装入延迟 在RISC机中，执行指令LOAD存在一定的延迟，称为装入延迟。如图4.22(a)所示，指令LOAD在MEM段(S4)才能把数据从存储器中读出，而指令ADD则在EX段就要使用。 图4.22 (a) RISC机中的装入延迟 第39页，共87页，2022年，5月20日，22点58分，星期四图4.22(b) 装入延迟引起的停顿 由于是访问存储器，尚不能定向传送，多采用停顿的方

27、法，如图4.22(b) 所示，称为流水线装入延迟或者“空泡”。第40页，共87页，2022年，5月20日，22点58分，星期四 3.控制相关（1）控制相关也称为控制转移冲突，主要由转移类指令引起。统计表明，一般程序中转移指令占1/4。转移发生时，流水线受到破坏，程序计数器PC指向新的指令地址。由于一般在MEM段的末尾才能使PC值改变，于是需停顿3个时钟周期，如图4.23所示。 图4.23 控制相关引起的停顿 第41页，共87页，2022年，5月20日，22点58分，星期四 【例4.2】设在某一程序中，有25%的转移指令，其中2/3转移发生，试计算执行一条指令的平均时钟周期。 解：设执行一条指令

28、的平均时钟周期为Pi，则 Pi=175%+125%11/3+2/3(3+1)=1.5(周期) 显然，使流水线的性能下降33.3%。（2）减少控制相关对流水线性能影响的措施 常有以下几种。 尽早判断转移发生和生成转移地址。把原在MEM段进行目标地址的计算提前到ID段进行，并在条件成立时送入程序计数器PC。这样，可使流水线顿时间由3拍减少到1拍。 预取转移成功和不成功两个方向上的目标指令。设两个指令队列，预取两个队列。 加快和提前形成条件码。比如乘除法运算的结果符号可根据两 操作数的符号提前产生。 第42页，共87页，2022年，5月20日，22点58分，星期四 加快短循环程序的处理。对于反复执行

29、的短循环程序可以全部取出，放入指令缓冲器中，以提高处理速度。 提高转移方向的预测率预测方法可用状态图表示，如图4.25所示。图4.25 转移预测状态图第43页，共87页，2022年，5月20日，22点58分，星期四其中使用两位二进制数表示是否转移，11和10表示预测转移发生状态，00和01表示预测转移不发生状态。 如果状态标志处在11状态，即预测转移发生，这时如发生转移，原状态保持；若不发生转移，则低位清0，状态标志变为10，仍是预测转移发生状态。 在10状态，如果发生转移，则低位置1，状态标志变为11；若不发生转移，则高位清0，状态标志变为00。 在00状态，如果不发生转移，原状态保持；若发

30、生转移，则低位置1，状态标志变为01，仍 预测转移不发生。 在01状态，如果发生转移，则高位置1，状态标志变为11；若不发生转移，则低位清0,状态标志变为00。统计表明，预测准确率达83%。第44页，共87页，2022年，5月20日，22点58分，星期四 采用延迟转移技术 如图4.24所示，在执行转移指令时流水线停顿，即转移延迟。延迟时间称为延迟槽。可取适当的指令在延迟遭执行，即填补延迟槽。常用方法有三种，如图4.26所示。 图4.26 采用延迟转移技术的3种方法 第45页，共87页，2022年，5月20日，22点58分，星期四 在图4.26(a)中，是用条件转移指令IF的前一条指令ADD R

31、1，R2，R3填补到延迟槽。 在图4.26(b)中，是用转移目标处的第一条指令SUB R4，R5，R6填补延迟槽，而原来位置的指令仍然保留。 在图4.26(c)中，是用非转移方向的指令填补延迟槽。前提是不发生数据相关。实践表明，第一种方案较好于其它两种。第46页，共87页，2022年，5月20日，22点58分，星期四流水线的实现与控制 1.流水线中的中断处理 在早期的流水线计算机中，只对中断的现场进行不精确保护，即对进入流水线的指令处理完毕，再去响应中断请求。显然，此时已不再是中断请求时的现场。这对于外部设备的中断请求可能影响不大，但是对于陷阱和内部中断影响就大了。 现在采用的是精确断点保护法

32、，即使用大量的后援寄存器，以使进入流水线的所有指令的现场都得到保护和恢复。 2.非线性流水线中功能段的竞争与调度 对于非线性流水线，存在前馈和反馈。若不能很好地调度，就会出现两条指令或任务争用某一功能段。若要不发生冲突，就要相隔适当的时间调度下一条指令或任务进入流水线。下面借助于预约表进行分析。第47页，共87页，2022年，5月20日，22点58分，星期四 设有一个非线性、单功能流水线P，由K个功能段组成，每一个任务流过流水线需要的时钟周期数为N（t1,t2,tn），纵向表示功能段，横向表示时钟周期，可画出如图4.27所示的预约表。图中的每一行表示P的一个功能段，每一列表示一个时钟周期，总列

33、数表示任务从流入到流出所经过的总时钟周期数。若某任务在某一时刻ti使用功能段Si，用“” 表示。一行中有多个“”，表示重复使用该功能段。 根据预约表很容易看出第一段间隔数为8，第二段间隔数为1，5，6等。把所有行的间隔节拍数都列出来，可构成一个间隔禁止表F(Forbidden list)，即F=1，5，6，8，表示禁止相隔这些拍数调度。图4.27 预约表 第48页，共87页，2022年，5月20日，22点58分，星期四 可用N-1位的二进制向量C=(Cn-1，Cn-2，C2，C1)表示，称为冲突向量(Collision vector)。其中第i位的状态表示与当前任务相隔i拍调入下任务时，是否发

34、生冲突。0表示不冲突，1表示冲突。冲突向量取N-1位是因为经过N拍后任务就流出流水线，又由于位数N是最大禁止间隔，因此Cn-1位总是1。 根据上述禁止表F，可形成相应的冲突向量（10110001），称为原始冲突向量。第2，3，4，7位为0，可与当前任务相隔2拍、3拍、4拍或7拍调入下一任务。下一任务进入流水线后，将产生新的冲突向量。然后再根据新的冲突向量确定第三个任务何时调入。第49页，共87页，2022年，5月20日，22点58分，星期四 如何形成新的冲突向量呢？任何一个任务在流水线中每经一拍向前推进一段，相当于原始冲突向量右移一位，左边补0。这样，就形成了新的冲突向量。 例如选择第二个任务

35、在2拍后调入流水线，则原始冲突向量应当逻辑右移两位，即（00101100）。为使第三个任务调入后不与前两个任务发生冲突，新的冲突向量应当是第二个任务的当前冲突向量（00101100）与第二个任务的初始冲突向量（10110001）按位“或”，结果为（10111101）。按照这一方式，选择各种可能的间隔拍数调入新的任务，并产生新的冲突向量，一直进行到不再产生新的冲突向量为止。第50页，共87页，2022年，5月20日，22点58分，星期四 需要注意的是，在产生新的冲突向量时每次右移后的位向量应与原始冲突向量按位“或”。由此可以画出用冲突向量表示的流水线状态转移图，如图4.28所示。图4.28 流水

36、线状态图第51页，共87页，2022年，5月20日，22点58分，星期四表4.2 各调度方案平均间隔拍数调度策略平均间隔拍数 (3,4) (4,3) (2,7) (2,2,7) (3,4,3,7) (3,4,7) (4,3,7) (3,7) (4,7) (7)3.503.504.503.674.254.674.675.005.507.00 采用图中任何一个闭合回路进行调度，都不会发生功能部件冲突。但需找到一个最佳策略，以便获得最高吞吐率。其方法是计算出每一种调度法的平均间隔拍数，如表4.2所示。然后，找出最小的一个。这里，平均间隔为3.5拍的调度策略有两种，即（3,4）和（4,3）。第52页，

37、共87页，2022年，5月20日，22点58分，星期四4.2.6 流水线的动态调度 静态调度主要借助于软件对指令的执行顺序进行调整，目前已经得到广泛应用。动态调度起始更早，但是直到20世纪后期才得以发展。它主要是通过硬件重新安排指令的执行顺序，以减少流水线中的停顿。有以下优点： 能处理在编译时难以发现的相关； 能简化编译程序； 使代码具有可移植性。 其缺点主要是硬件电路复杂。目前主要有两种方法，一种是集中式动态调度，另一种是分布式动态调度。第53页，共87页，2022年，5月20日，22点58分，星期四 1.集中式动态调度集中式动态调度是依赖硬件在程序运行的过程中对可能出现的相关进行预测，从而

38、保证流水线中的各个功能部件能最大限度地重叠工作，其示意如图4.29所示。 图中主要设置了一个状态寄存器RF和一个记录控制器（也称为记分牌），用来对各功能部件的工作状态、进入流水线中的各条指令的状态、 图4.29 集中式动态调度 使用的源寄存器和目标寄存器的状况进行集中统一的记录和调度。早期的CDC6600计算机采用的就是这一技术，现在的RISC超级标量机很多也采用与之类似的措施，以提高流水线的性能。第54页，共87页，2022年，5月20日，22点58分，星期四2.分布式动态调度 是把调度控制分配到各功能部件上。早期的IBM360/91采用了这一技术，其示意如图4.30所示。其中每一个浮点数寄

39、存器FLR设置一个“忙”标志，以表示指令间所用的数据是否会发生冲突。其浮点运算器主要包括以下部件。 （1）运算器：由相互独立的加法器和乘除法器组成。 （2）保存站：在加法器中有三个A1A3，在乘除法器中有两个M1M2，当两个数据都到齐后，若运算器空闲，立即进行运算。每一个保存站都有地址，称为站号。保存站与浮点操作数缓冲寄存器FLB统一编址，如图3.30所示。 （3）指令处理部件：也称为浮点操作栈，用来存放取出的指令，经译码产生控制信号，送往相应的部件。 （4）浮点数据预取缓冲器FLB：暂存存储器中预取出来的浮点数，作为源操作数。 （5）浮点数据寄存器FLR：作为另一源操作数；或者存放运算结果或

40、中间结果，即目标寄存器。各寄存器有一个“忙”标志，其中“1”表示寄存器正被使用。另外，每个寄存器设有“站号标记”，表示数据由何而来。该组寄存器表示为F0F7。 （6）数据存储缓冲器SDB：用来暂存欲存入存储器的数据，也设有站号，表示数据由何而来。 （7）公用数据总线CDB：用来连接上述各个部件，传送数据。第55页，共87页，2022年，5月20日，22点58分，星期四 图4.30 IBM 360/91流水线的分布式动态调度示意图 第56页，共87页，2022年，5月20日，22点58分，星期四F0置忙 M1：源1站号置0001 源2站号置0010F0置1000A1：源1站号置0011 源2站号

41、置0100F0置1010S1：LD F0，FLB1 F00001 S2：MD F0，FLB2 S3：STD F0，A C1站1000S4：LD F0，FLB3 F0站0011S5：ADD F0，FLB4第57页，共87页，2022年，5月20日，22点58分，星期四 这种调度方法是把数据的传送控制分派到各个单元的站号的设置上，即分布式动态调度方式。其特点可概括为以下几点。（1）通过公用数据总线把数据直接传送到所需要的部件，减少了流水线中的停顿周期。（2）通过加法器保存站和乘除法保存站，可缓解资源使用中冲突的机会。（2）通过修改站号实现分布式动态调度，可消除WAR和WAW数据相关的可能性。（3）

42、通过对FLR寄存器“忙”标志的判断，可检查是否存在RAW数据相关。 第58页，共87页，2022年，5月20日，22点58分，星期四 图4.31 转移目标缓冲器 3.硬件动态预测转移法 是由转移目标缓冲器BTB（Branch target buffer）来实现。BTB由高速存储器或者寄存器堆组成，按内容访问，图4.31 所示。第59页，共87页，2022年，5月20日，22点58分，星期四 其中存放转移指令的地址（即PC值）、转移目标地址和2位状态标志。标志位按照图4.25设置，用于转移预测。 图4.25 转移预测状态图 遇到转移指令时，用PC值与BTB中的内容进行比较。若有相符合内容，则判断

43、标志位，以确定是否取出转移目标地址。若转移条件成立，则根据取出的目标地址执行程序；若转移条件不成立，则取消本次操作，并修改状态标志位。第60页，共87页，2022年，5月20日，22点58分，星期四4.3 指令级流水线4.3.1 指令级流水线4.3.2 超级标量流水线4.3.3 超长指令字4.3.4 展开循环体后调度4.3.5 软件流水法4.3.6 超级流水机举例第61页，共87页，2022年，5月20日，22点58分，星期四4.3.1 指令级流水线 流水线可分为粗粒度和细粒度两种类型，其中细粒度流水线指的就是指令级流水线。20世纪80年代发展起来的RISC机在指令级流水线的开发中取得了很大的

44、成就，它的目标是使CPI达到1。新一代RISC机还试图使CPI小于1。 指令级流水线的并行性常用并行度来衡量，是指在不存在相关，可同时并行执行的指令的条数。下面举例说明。 第62页，共87页，2022年，5月20日，22点58分，星期四【例4.2】分析下面两个程序段的并行度。 程序段1 程序段2 LOAD R1，MR7 ADD R2，R1，1 ADD R3，R3，1 SUB R4，R3，R2 FPMUL F3，F3，F4 STORE MR4，R5 解：由于在程序段1中，3条指令所使用的数据地址不存在相关，因此可并行执行，其并行度为3。而在程序段2中，ADD指令的目标寄存器是R2，而在SUB指令

45、中R2是源操作数，存在RAW相关；同时，在SUB指令中R4是目标寄存器，而在STORE指令中R4作为基地址寄存器，也是一种RAW相关。因此，在程序段2中3条指令只能顺序执行，即并行度为1。目前在指令级流水线中，主要使用的方法有超级标量流水线法和超长指令字法。 第63页，共87页，2022年，5月20日，22点58分，星期四4.3.2 超级标量流水线 1.基本概念 在理想的流水线中，每一个时钟周期可启动一条指令。执行过程分为4个阶段，理想流水线的示意如图4.32所示。 在超级标量流水线中，人们希望在一个时钟周期内启动多条指令。如图4.33所示同时启动了3条指令，因此并行度为3。 图4.32 理想

46、流水线 图4.33 每拍启动三条指令 第64页，共87页，2022年，5月20日，22点58分，星期四 图4.34 每1/2拍或每1/3拍启动一条或三条指令 也可以每1/2周期或者每1/3周期启动一条指令，如图4.34(a)所示每1/2周期启动一条指令，并行度为2。还可以每1/2周期或者1/3周期启动多条指令，如图4.34(b)所示每1/3周期启动了3条指令，其并行度为9。第65页，共87页，2022年，5月20日，22点58分，星期四 图4.37 超长指令字（VLIW） 另外，也可以通过超长指令字实现每个时钟周期完成多个操作，如图4.37所示。第66页，共87页，2022年，5月20日，22

47、点58分，星期四2.超级标量机的组成特点 在超级标量流水线计算机中要实现一拍完成多个操作，就必须有相应的功能部件予以支持。如图4.35(a)所示，只有一个ALU，每一拍只能进行一种操作，即启动一条指令。如图4.35(b)提供一个ALU和一个浮点运算器FP，可在一拍中进行两种操作，即启动两条指令。图中I-Cache表示指令高速缓冲存储器，RF表示寄存器堆。 图4.35 超级标量机多执行部件第67页，共87页，2022年，5月20日，22点58分，星期四 图4.36 超级标量机典型结构 3.超级标量机的典型结构 图4.36所示是一种超级标量机的典型结构，由存储部件、ALU部件及控制部件组成。第68

48、页，共87页，2022年，5月20日，22点58分，星期四 程序执行时同时取出两条指令，分别送相应的译码器。译码后，根据状态记录部件中记录的功能部件与寄存器使用情况，确定哪些指令可以送入执行部件中同时执行；有关寄存器和执行部件的状态可能发生变化，送状态记录部件，供下一次判断使用。 即根据状态记录部件中记录的相关信息来确定多条指令可否同时被调度和执行。 自20世纪80年代末，超级标量机陆续问世，比如Intel公司的i860、IBM公司的RS6000以及Motorola公司的88110等。在一个周期内可启动24条指令。但是在实际运行时，一个时钟周期启动的指令条数往往小于IPC（Instructio

49、n per cycle）的值。主要特点: 配置有多个性能不同的处理部件，采用多条流水线并行处理。 能同时对多条指令进行译码，并根据状态记录部件中记录的状态将可执行指令送入相应的执行部件。 通过硬件实现多条指令的调度，即用硬件资源重复来实现空间上的并行操作。 第69页，共87页，2022年，5月20日，22点58分，星期四4.3.3 超长指令字1.超长指令字 超长指令字VLIW（Very long instruction word）是在20世纪80年代初由美国耶鲁大学的Fisher教授首先提出来的。它的一条指令很长可达上百位，甚至上千位，主要在于减少访存次数，如图4.37所示在一个周期完成多个操

50、作。 图4.37 超长指令字（VLIW） 特点：单一控制器，每个周期启动一条指令。在其内部，一条超长指令字被分成多个控制字段，独立控制一个功能部件。第70页，共87页，2022年，5月20日，22点58分，星期四2.超长指令字计算机的组成原理 超长指令字计算机的结构示意如图4.38所示，包含两个存储器读/写部件、一个浮点加法部件和一个浮点乘法部件。所有功能部件均由统一的时钟信号驱动，根据超长指令的各个控制字段工作。 图中包括存/取1、存/取2、浮点加、浮点乘及其相关的数据通路，可同时进行两路存储器访问、浮点加和浮点乘操作。 这种计算机是在编译时处理可能出现的数据相关和资源相关，因此硬件电路比较

51、简单。而且，在编译阶段完成超长字指令中多个可并行执行的操作的调度。图4.38 超长指令字计算机结构示意图 第71页，共87页，2022年，5月20日，22点58分，星期四表4.3顺序执行序列源代码操 作需用周期C=A+B LOAD A LOAD B C=A+B STORE C1111K=I+J LOAD I LOAD J K=I+J STORE K1111L=M-K LOAD M L=M-K STORE L111Q=CK Q= CK STORE Q21 合计 14个周期3.超长指令字的生成设有以下赋值运算：C=A+BK=I+JL=M-KQ=CK若按照顺序操作，所使用的指令序列如表4.3所示，共

52、需要14个周期。从中找出不存在任何相关的操作同时进行，即可得到如表4.4所示的并/串行操作序列。这样，每一行可构成一个超长字指令，编译时可把13条指令压缩成6条，仅需要6个周期即可完成。表4.4 并行操作序列周期操 作1LOAD ALOAD B2LOAD ILOAD JC=A+B3LOAD MSTORE CK=I+J4STORE KL=M-KQ= CK5STORE L6STORE Q第72页，共87页，2022年，5月20日，22点58分，星期四 4. VLIW压缩调度技术 上述压缩采用的是表调度法，而且是一种局部压缩调度法。目前常用的压缩调度方法可分为局部压缩和全局压缩。 （1）局部压缩 局

53、部压缩是在小范围内进行，即一个基本的程序块，仅有一个入口和一个出口。 （2）全局压缩 全局压缩允许代码在基本程序块之间移动。当然，这种移动必须保证各个基本程序块原语义不变。目前全局压缩有三种方式，即路径调度、渗透调度和软件流水。 路径调度法是在编译时把代码划分为若干不相交的子集，称之为路径，然后选择执行概率最高的路径作为主路径。对主路径采用表调度法进行压缩，且允许代码在一定约束条件下在基本块之间移动。这种方式可能牺牲非主路径的性能，以获得主路径的最佳效果。但是非主路径需要进行补偿。第73页，共87页，2022年，5月20日，22点58分，星期四 图4.39表示沿主路径压缩及补偿的示意。在图4.

54、39中，(a)的阴影框表示主路径，（b）表示压缩后对非主路径造成的影响，(c)表示补偿，其中R表示重聚补偿，S表示分裂补偿。补偿的具体过程如图4.40所示。 图4.39 沿主路径压缩与补偿示意图 第74页，共87页，2022年，5月20日，22点58分，星期四 在图4.40中，是对主路径进行调度后而进行的补偿。其中图(a)是用第一条指令填补if语句的延迟槽，而对if语句进行的分裂补偿。图(b)是用第二条指令填补乘法语句的延迟槽，而对乘法指令进行重聚补偿。 图4.40 路径调度与补偿 第75页，共87页，2022年，5月20日，22点58分，星期四 渗透调度法（Percolation sched

55、uling） 是通过一系列语义的等价变换，把操作不断地推向前进，即渗透。渗透后把属于不同基本块的操作最大限度地重叠起来。不是根据转移分支的概率选择操作，而是设法让后续的操作近早执行。具体的实施方法，请参阅高级编译技术的有关章节。 软件流水法（Software pipelining） 主要是加快循环程序的执行，在4.3.5节介绍。 第76页，共87页，2022年，5月20日，22点58分，星期四4.3.4 展开循环体后调度 展开循环体后调度是在编译时多次展开循环体，然后在程序语义保持不变的前提下对指令序列重新排列，以提高流水线的并行度。下面举例说明： 设有以下循环体程序段，为存储器中的某一向量加

56、上F2中的一个指定的标量值。 LOOP：LD F0，0(R1) ；F0M(R1)+0，读向量元素 ADDD F4，F0，F2 ；F4(F0)+(F2) SD 0(R1)，F4 ；M(R1)+0F4，存向量元素 SUB R1，R1，#8 ；R1(R1)-8，将指针减8 BNEZ R1，LOOP ；若(R1)0，则转移到LOOP第77页，共87页，2022年，5月20日，22点58分，星期四 设浮点加法需要3个周期，寄存器整型运算需要1个周期，分支指令需要2个周期，读存储器需要2个周期，写存储器时只要送入存储缓冲器即可，因此仅1个周期。为了使流水线正确工作，须插入等待周期，用STALL表示： LOOP：LD F0，0(R1) ；F0M(R1)+0，读向量元素 STALL ；停顿 ADDD F4，F0，F2 ；F4(F0)+(F2) STALL STALL SD 0(R1)，F4 ；M(R1)+0F4，存向量元素 SUB R1，R1，#8 ；R1(R1)-8，将指针减8