计算机系统结构(ch-4)解析

1、第4章 流水线计算机设计技术,本章目标 加快机器指令执行的速度 主要方法 采用更高速的器件和更好的算法、提高微操作的并行度、减少所需时钟周期数等措施加快单条指令的解释 改革控制机构的方式（传统方式为顺序串行），让两条以上的指令以重叠、流水的方式执行（目前发展到了超级流水线） 按照资源重复的思想，重复设置多套指令部件，使多条指令同时执行，即超标量技术 超标量超流水线结合,第4章 流水线计算机设计技术,4.1 重叠解释方式 4.2 流水线的工作原理、特点和分类 4.3 相关问题及解决方法 4.4 流水线的性能分析与举例 4.5 非线性流水线的调度技术 4.6 先进的流水调度技术动态调度 4.7 转

2、移预测技术 4.8 超标量、超流水线和VLIW,4.1 重叠解释方式,4.1.1 重叠解释方式的提出 1、顺序执行方式 执行n条指令所用的时间为： 若每段时间都为t，则：T=3nt 主要优点：控制简单，节省设备。 主要缺点：执行指令的速度慢，功能部件的利用率很低。,若每个过程的时间相等，则执行n条指令的时间： T=(1+2n)t 主要优点： 执行时间缩短（与顺序方式相比） 功能部件的利用率明显提高 主要缺点： 需要增加一些硬件（如需要增加一个指令寄存器IR等） 控制过程稍复杂（解决访问存储器的冲突等）,2、一次重叠执行方式,3、二次重叠执行方式,理想情况下同时有三条指令在执行 如果三个过程的时

3、间相等，执行n条指令的时间为： T=(2+n)t 处理机的结构要作比较大的改变，必须采用先行控制技术（Look-Ahead）,二次重叠要解决的问题：,为了能同时完成取指令、分析指令、执行指令操作，必须有独立的存储控制器（存控）、指令控制器（指控）、运算控制器（运控）。 解决访存冲突的问题，有三个方法: 指令、数据单独存放，可以同时访问（哈佛结构，高级机器采用I-Cache和D-Cache) 指令、数据混合存放,但采用多体交叉的并行主存系统 增设指令缓冲寄存器，乘主存空闲期间取后续指令。如8086的指令队列。,上次课内容回顾,Cache存储系统与虚拟存储系统的比较 目的 实现方法 两级存储器速度

4、比 页(块)大小 等效存储容量 透明性 不命中时的处理方式 采用器件 第二级存储器与CPU通路,上次课内容回顾,主存内容的更新算法 写直达法(Write-Through) 写回法(Write-Back) 写Cache不命中时的取策略 不按写分配法 按写分配法 预取算法：使用之前就预先取入Cache 恒预取：访问第i块的信息时，预取第i+1块 不命中时预取：访问第i块不命中时，取i块时预取第i+1块,上次课内容回顾,指令执行方式,4.1.2 使用指令缓冲器后的一次重叠,指令缓冲器（先行指令缓冲栈）是利用主存储器的空闲时间来取指令的。因而只要主存的频带宽度足够，要分析的指令就都能从指令缓冲器中得到

5、，从而取指令只需要很短的时间就能完成，因此可以将取指令和分析指令合并到一起。,T=(n+1)t,4.2 流水线的工作原理、特点和分类,4.2.1 流水线的工作原理 4.2.2 流水线的特点 4.2.3 流水线的分类,1、简单的指令流水线 流水线的每一个阶段称为流水段、功能段、流水级或流水节拍。 在每一个流水段的末尾或开头必须设置一个寄存器，称为流水锁存器或流水寄存器。会增加指令的执行时间。 为了简化，在流水线中一般不画出流水锁存器，如P76图4.1。,4.2.1 流水线工作原理,2、进一步细分的指令流水线,典型五段流水线 取指：按PC值访存，取指令到IR，并修改PC指向下一指令 译码：根据OP

6、译码并读寄存器取数 执行：对访存指令形成OD的有效地址，其他指令执行其功能 访存：根据有效地址EA访存取/存数 写会：运算结果写会寄存器堆RF,2、进一步细分的指令流水线,一般4至12个流水段，大于等于8个流水段的称为超级流水线。,取指单元段1: IFU1 取指单元段2: IFU2 取指单元段3：IFU3 译码段1 :DEC1 译码段2：DEC2 寄存器别名表和分配段：RAT,重排缓冲器段：ROB 派遣段：DIS 执行段：EX 写回段：WB 回收就绪段：RR 回收段：RET,Pentium II/III的超标量超流水的流水线可分为12段：,流水线的分析工具：时空图,运行的时刻,所在流水段,进行

7、的工作,简单流水线的时空图,流水线的分析工具：时空图,流水线明显比顺序方式效率高,4段浮点加法器流水线的时空图,流水线的分析工具时空图,只有连续提供同类任务才能充分发挥流水线的效率： 对于指令流水线：要尽量减少因条件分支造成的断流 对于操作部件：主要通过编译技术，尽量提供连续的同类操作 由多个功能段组成，每个功能段对应一个专用部件 在流水线的每一个流水线段中都要设置一个流水锁存器 时间开销：流水线的执行时间加长 硬件开销：流水线中需要增加的主要硬件之一 各流水段的时间应尽量相等 流水线处理机的基本时钟周期等于时间最长的流水段时间长度 流水线工作可以分为建立、满载和排空3个阶段，如图所示。,4.

8、2.2 流水线的主要特点,流水线的建立、满载和排空,上次课内容回顾,指令的解释方式 顺序方式 一次重叠方式 二次重叠方式 增设指令缓冲器后的一次重叠方式,上次课内容回顾,相关及处理 流水线 概念：重叠方式的进一步引申 特点 分析工具：时空图 分类,1、按连接方式分类 线性流水线（Linear Pipelining） 每个流水段都流过一次，且仅流过一次 线性流水线能够用流水线连接图唯一表示 非线性流水线（Nonlinear Pipelining） 在流水线的某些流水段之间有反馈回路或前馈回路 必须用流水线连接图、预约表等共同表示,4.2.3 流水线的分类,一种简单的非线性流水线,1）处理机流水线

9、（指令流水线）,2、按照流水线的级别分类,例如：在采用先行控制技术的处理机中，各功能部件之间的流水线：,3）处理机间流水线（宏流水线） 每个处理机对同一数据流的不同部分分别进行处理,2）部件流水线（操作流水线） 例如：浮点加法流水线：,2、按照流水线的级别分类,P79图4.5,单功能流水线： 只能完成一种固定功能的流水线 例：Cray-1计算机中有12条；YH-1计算机有18条；Pentium有一条5段的定点和一条8段的浮点流水线；Pentium 有三条指令流水线，其中两条定点指令流水线，一条浮点指令流水线。 多功能流水线： 流水线的各段通过不同连接实现不同功能 例：Texas公司的TI-AS

10、C计算机中的8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。,3、按流水线功能的多少分类,图4.6,静态流水线： 同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能。 只有连续出现同一种运算时，流水线的效率才能得到充分的发挥。如图所示 动态流水线： 在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。如图所示,3、按多功能流水线的工作方式分类,加法不使用这两个部件,浮点加法排空后才开始定点乘法指令,浮点加法未排空定点乘法就开始,按照数据表示方式： 标量流水线（本章） 向量流水

11、线（第六章） 按照任务流入和流出的顺序分： 顺序（in-order）流水线 乱序（out-of-order）流水线,4、流水线的其他分类方法,一种乱序流水线,流水线分类小结,分类,有无反馈：线性、非线性,级别：部件级、处理机级、处理机间级,功能多少：单功能、多功能,能否同时：静态、动态（仅对多功能流水线划分）,数据表示：标量、向量,输出顺序：顺序、乱序,4.3 相关问题及解决方法,相关是指在一段程序的相近指令之间存在某种关系，为避免出错，而使它们不能同时解释的现象。 资源相关：多条指令进入流水线后在同一个t内争用同一功能部件发生的相关。 控制相关（全局相关）：指由控制转移类指令（条件转移、子程

12、序调用与返回、中断等）引起的相关。 数据相关(局部相关）：指由于相邻的两条或多条指令使用了相同的数据地址（包括寄存器地址和存储单元地址）而发生的关联 。,4.3.1资源相关,资源相关：多条指令进入流水线后在同一个t内争用同一功能部件发生的相关。 用I1 I2表示,在第4个周期，指令1、4争用访存部件,4.3.1资源相关,解决存储器资源相关的方法主要有以下五种： 从时间上推后下一条指令的访存操作。 让操作数和指令分别存放于两个独立编址且可同时访问的主存储器中。称哈弗结构。 仍然维持指令和操作数混存，但采用多模块交叉主存结构。 在CPU内增设I-Cache，乘主存空闲时预取指令。 在CPU内增设I

13、-Cache和D-Cache。 解决其它资源相关的方法主要是从时间上推后下一条指令对资源的使用和重复设置多套硬件资源。,4.3.2 数据相关,数据相关(局部相关）：指由于相邻的两条或多条指令使用了相同的数据地址（包括寄存器地址和存储单元地址）而发生的关联，说明指令间的有序关系。 先写后读相关：I1写的地址与I2读的地址相同，则称指令I2与指令I1存在先写后读相关，用“ ”表示。 先读后写相关 ：I2写的地址与I1读的地址相同，则称指令I2与指令I1存在先读后写相关，用“ ”表示。 写写相关：I2与I1有相同的写地址（寄存器或存储器），则称I2与I1存在写写相关，用“ ”表示。 顺序流水线中只存

14、在先写后读相关，乱序流水线三种相关都存在,顺序流动和乱序流动,h的目的操作数是j的源操作数，则发生先写后读相关 乱序执行后，若k，j写同一地址，则发生写-写相关 乱序执行后，若j读与k写的地址相同，则发生先读后写相关。,j读h的结果,越过j，继续往前流动,4.3.2 数据相关,I1： ADD R1，R2，R3/(R2)+(R3)R1/ I2： SUB R1，R4，R5/(R4)-(R5)R1/ I3： AND R4，R1，R7/(R1)(R7)R4/,I3与I1、I2的先写后读相关，导致I3读数错误,I1与I2的写写相关，由于顺序执行，不会导致错误,4.3.2 数据相关,先写后读相关解决的方法

15、 推后相关单元的读,后推导致性能下降,I3读后推至I2写完成,先写后读相关解决的方法 相关专用通路（定向传送技术）,4.3.2 数据相关,提高了性能，增加了硬件复杂度,例4.1,例4.1用图示的方法画出以下4条指令之间存在的数据相关和资源相关。 I1：MUL R1，R2，R3/(R2)(R3)R1/ I2：ADD R5，R4，R1/(R4)+(R1)R5/ I3：ADD R6，R7，R1/(R7)+(R1)R6/ I4：AND R1，R8，R5/(R8)(R5)R1/,4.3.3 控制相关,控制相关（全局相关）：指由控制转移类指令（条件转移、子程序调用与返回、中断等）引起的相关。 延迟转移技术

16、。编译程序重排指令序列，将转移指令与其前面的与转移指令无关的一条或几条指令对换位置，让成功转移总是在紧跟的指令被执行之后发生，从而使预取的指令不作废。见第二章RISC关键技术。 转移预测技术。直接由硬件来实现，转移预测技术可分为静态转移预测和动态转移预测两种。见4.7,4.4 线性流水线的性能分析,4.4.1 线性流水线的性能分析 4.4.2 线性流水线性能分析举例,衡量流水线性能的主要指标：吞吐率、加速比和效率 1、吞吐率（ThoughPut Rate） 指单位时间内从流水线流出的任务（结果）数。 TP = n / Tkn任务（结果）数, Tk完成n个任务（结果）所用时间 若各段执行时间相等

17、（ Dt ），从时空图可以看出任务连续的情况下，完成n个任务需要的总时间为： Tk= (k+n-1) Dt k为流水线的段数，D t为时钟周期,4.4 线性流水线的性能分析,流水线各段执行时间相等的时空图,吞吐率： 最大吞吐率为： 各段执行时间不相等、输入连续任务情况下： 吞吐率为： 最大吞吐率为：,吞吐率计算公式,流水线各段执行时间不相等的时空图,将瓶颈段进一步细分(如果可能的话)：,重复设置多个瓶颈段（需要MUX和DEMUX）：,“瓶颈”部件的解决方法：,在子部件中依次分配,重复设置流水段的流水线时空图,各段执行时间相等，输入连续任务情况: 加速比为： 最大加速比为：,2. 加速比（Spe

18、edup ratio）,采用流水线方式后的工作速度与等效的顺序串行方式的工作速度之比称为流水线的加速比。 Sp = 顺序串行执行时间TO / 流水线执行时间Tk,注意： 1.程序存在相关性，n不会很大 2.由于硬件工艺的限制，流水段也不会很多 3.由于每个流水段间都要有流水锁存器，增加了延时,k越大越好？,各段执行时间不等，输入连续任务情况下实际加速比为：,2. 加速比(speedup ratio),流水线的效率是指流水线的设备利用率。 各流水段执行时间相等，输入n个连续任务 流水线的效率为： 流水线的最高效率为：,3、效率（Efficiency）,流水线各段执行时间相等的时空图,各流水段执行

19、时间不等，输入n个连续任务时流水线的效率为：,3、效率（Efficiency）,流水线各段的设备量或各段的价格不相等时： 流水线的效率为（加权效率）： 即： 其中，ai k，且,3、效率（Efficiency）,所以：E=TP Dt 或 TP=E/ Dt Sp=k E,流水线的吞吐率、加速比与效率的关系,因为：,4.4.2 线性流水线性能分析举例,对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。其它情况下要根据实际时-空图计算。 例4.3：用一条4段浮点加法器流水线求8个浮点数的和： ZABCDEFGH,解：Z = (A+B) + (C+D

20、) + (E+F) + (G+H),例4.3,7个浮点加法共用了15个时钟周期。 流水线的吞吐率为： 流水线的加速比为： 流水线的效率为：,例4.3,例4.4,设有二个向量A、B，各有4个元素，要在如图4.19所示的静态双功能流水线上，计算向量点积AB=aibi。在该双功能流水线中，S1S2S3S5组成加法流水线，S1S4S5组成乘法流水线。设每个流水段所经过的时间为t，而且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中，其延迟时间和功能切换时间忽略不计。使用合理的算法，能使完成向量点积AB运算所用的时间最短，并求出流水线在此期间的实际吞吐率TP、加速比SP和效率E。,例4.4,

21、选择适合于静态流水线工作的算法： 连续计算a1b1、a2b2、a3b3、a4b4 4次乘法； 乘法工作排空后，进行功能部件的切换，连续计算(a1b1+a2b2)、(a3b3+a4b4)； 再最后计算：(a1b1+a2b2)+(a3b3+a4b4)。 由时-空图可见，最后总共流入多功能流水线的任务数为7个，完成任务所需的时间为15t，而顺序完成7个任务需要的时间为43t+34t=24t。 TP=7/(15t)；SP=24/15=1.6；E=24t/(515t)=32% 练习：将流水线改为动态流水线,上次课内容回顾,流水线的吞吐率 各段时间相等的 存在瓶颈段的 瓶颈段的消除方法,上次课内容回顾,流

22、水线的加速比 各段时间相等的 存在瓶颈段的,上次课内容回顾,流水线的效率 各段时间相等的 存在瓶颈段的,4.5 非线性流水线的调度技术,非线性流水线的调度问题： 在非线性流水线的输入端，究竟每间隔多少个时钟周期向流水线输入一个新任务才能使流水线的效率最高并且各个功能段都不发生冲突。,非线性流水线调度的任务： 找出一个最小的循环周期，按照这个周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。,以下介绍： 非线性流水线的表示方法 冲突情况的分析 无冲突调度方法,非线性流水线的表示,一条非线性流水线一般需要一个各功能段间的连接图和一张预约表共同表示。,对于非线性

23、流水线预约表的说明,预约表的横坐标表示流水线的时钟周期，纵坐标表示流水线的功能段，中间有“”的表示该功能段在这一个时钟周期处于工作状态，即在这个时钟周期有任务通过这个功能段；空白的表示该功能段在这一个时钟周期不处于工作状态。,预约表行数是非线性流水线的段数；而列数是一个任务从进入流水线到从流水线中输出所经历的时钟周期数。 一张非线性流水线的预约表可能与多个非线性流水线连接图相对应；同样，一个非线性流水线的连接图也可能对应有多张预约表。多对多,非线性流水线的冲突,非线性流水线的启动距离：向非线性流水线的输入端连续输入两个任务之间的时间间隔。 非线性流水线的冲突：当以某个启动距离向非线性流水线连续

24、输入任务时，可能存在多个任务同时争用某个或某几个功能段的情况。 上图所示的非线性流水线中，当启动距离为3时，冲突情况如图：,而当启动距离为5时，无冲突，如下图,非线性流水线的冲突,引起非线性流水线功能段冲突的启动距离称为禁止启动距离 在非线性流水线中，不发生冲突的距离不一定是一个常数，也可以是一个循环数列 将一条非线性流水线的所有禁止启动距离组合成一个数列，称为非线性流水线的禁止向量（延迟禁止表F， forbidden list ） 禁止向量的构造方法：把预约表每一行中任意两个“” 的距离计算出来，去掉重复的即可。,非线性流水线的冲突,禁止向量,3，6,3,4,可得该流水线预约表的禁止向量为（

25、3，4，6）,上次课内容回顾,线性流水线性能分析 吞吐率、效率、加速比 公式法、时空图法 非线性流水线调度 解决的问题 预约表禁止向量原始冲突向量流水线状态图全部调度方案选取符合要求的方案,非线性流水线的无冲突调度方法,目标：找出具有最小平均启动距离的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲突。,步骤： 1、根据预约表求禁止向量进而得冲突向量（collision vector） 冲突向量是一个m位二进制位向量，其中m是禁止向量中的最大值（若预约表的列数为k，则：mk-1)。 冲突向量用C=（CmCm-1 Ci C2C1

26、)表示。如果i在禁止向量中，则 Ci=1，否则Ci=0。其中Cm一定为1，因为m必定在禁止向量中。如上图所示的预约表，因为其禁止向量为（ 3，4，6），所以冲突向量C=（101100）。,2 由冲突向量可以构造状态图,将上述冲突向量（101100）作为初始冲突 向量送入一个m位的逻辑右移移位寄存器。 进行逻辑右移操作（代表指令在流水线中向前流动） 当右移移出的位为0时，用移位器中的值与初始冲突向量做“按位或”运算，得到一个新的冲突向量；代表送入一个新任务 若右移移出的位为1，不作处理。不能送入新任务 对新生成的冲突向量也如此反复，直到无新冲突向量产生为止。,101100,111110,1011

27、11,111111,101101,在状态转移图中找出各种冲突向量最多只经过一次的所有启动循环，进而得到平均启动距离最小的启动循环。,启动循环,注意：必须从第一个状态进入循环,路径及平均启动距离,4.5 非线性流水线的调度技术,4.5 非线性流水线的调度技术,注意：教材中的冲突向量固定为N-1位，N为预约表中时钟周期数,最佳,4.5 非线性流水线的调度技术,4.6 先进的流水技术动态调度（异步流动）,流水线的调度 静态调度(static scheduling) ：运行前调度，如编译阶段，尽量通过分离有相关的指令使它们避免产生冲突，从而减少暂停对流水线的影响。 动态调度(dynamic sched

28、uling) ：运行时调度，依据当时资源使用情况动态进行，基于乱序技术，可使流水线的效率最大限度的得到发挥。 动态调度相比与静态调度的优点： 能处理某些在编译时无法知道的相关情况，简化编译器的设计；使代码具有可移植性。,4.6.1 集中式动态调度记分板机制,源自CDC6600，记分板（状态记录控制器）对流水线中的各个功能部件的工作状态、进入流水线中的各条指令的工作状态、它们所使用的源寄存器和目的寄存器情况等进行集中的统一（集中式）记录和调度。 采用顺序发射乱序完成机制。会出现RAW、WAR、WAW三种数据相关。 每条指令都从记分板通过，并建立相应的数据相关结构。然后由记分板部件决定何时可取得操

29、作数及执行该指令，若判断该指令当前还不能立即执行，则会监视硬件上的每一个变化，并决定该指令何时能执行。记录控制器还可控制指令写入目标寄存器的操作，所有的相关检测及消除工作都由记分板完成。,4.6.1 集中式动态调度记分板机制,4.6.1 集中式动态调度记分板机制,译码阶段 根据记录的状态决定是否将译码后的指令发送给有关功能部件，即检查是否存在资源使用冲突（功能部件冲突）。 检查是否存在“先写后读”、“先读后写”、“写-写”的数据相关。 执行阶段 读操作数时，监视源操作数的可用情况，若无已发射的活动指令写该操作数，或存放该操作数的寄存器没有被某个活动的功能部件写入，则源操作数是可用的。即解决了先

30、写后读相关。 回写结果阶段 检查是否有先读后写相关,ADDD F10,F0,F8 SUBD F8,F8,F14,记分板停止SUBD写F8，直到ADDD读取F8后,4.6.2 分布式动态调度Tomasulo方法,运用寄存器重命名技术来避免先读后写和写-写相关 通过设置保留站避免先读后写和写-写相关,保留站缓存了即将要发射的指令所需要的操作数 当多个操作写同一个寄存器时，只允许最后一个写操作实际更新寄存器 指令发射后操作数寄存器名换成保留站名，即寄存器重命名技术。由于保留站数量比寄存器多，因此，可以消除原先编译器不能消除的相关 与记分板方法的显著差别： 相关检测和执行控制是分散的 结果从保留站直接

31、送到功能部件中，而不是通过寄存器传送，为此使用了一条公共数据总线CDB(Common Data Bus),相关专用通路,缓存主存数据,待写数据的缓冲,缓存待发射指令的数据,缓存浮点操作,F2,FLB1,1,A1,A1,FLB2,M1,ADD F2，FLB1 MD F2，FLB2,上次课内容回顾,非线性流水线调度 解决的问题 实现的目标 预约表禁止向量原始冲突向量流水线状态图全部调度方案选取符合要求的方案,4.7 转移预测技术,流水线只有不断流，才能获得高效率 造成流水线断流的原因： 编译生成的目的程序不能发挥流水线性能 存储系统不能为连续流动提供所需的指令和数据 存在相关问题 数据相关 资源相

32、关 控制相关 存在中断问题,本节重点讨论,后推、相关专用通路,4.7.1 转移对流水线的影响,作废,条件转移指令：,变成了顺序方式,流水效率下降,4.7.1 转移对流水线的影响,基本术语 转移取：在执行一条转移指令后，取一条非顺序的或是远程指令的行为（转移成功） 转移目标：在转移取之后要执行的指令 延迟时间片（延迟槽） ：是指在转移取与转移目标之间损失的流水线时钟周期数，用b表示，0bk-1,4.7.1 转移对流水线的影响,考虑转移的影响，连续执行n条指令的总时间 考虑转移影响后的吞吐率 最小吞吐率（n、b=k-1）,因转移影响，多付出的代价,4.7.1 转移对流水线的影响,最大吞吐率（p=q

33、=0） 性能衰减因子,P=0.2，q=0.6，k=8时，D=0.46,4.7.2 转移预测技术,分支预测法 如图4.35所示 静态预测： 按概率预测 概率猜不成功方向（已经预取入指缓） 不同猜大概率方向（如ADD AX,BX /JNZ L1） 按转移方向预测 向后分支预测成功方向 向前分支预测不成功方向 BM360/91采用转移不成功分支 无论猜哪个方向，猜错概率都不小于30%,4.7.2 转移预测技术,动态预测： 根据转移历史动态预测转移方向。如图所示 预测准确度可达90%，如Power PC 、Inter Pentium。,分支预测技术,遇转移时，继续预测某个方向执行,如何预测，准确度更高

34、？,动态分支预测技术,4.7.3 动态硬件转移预测方法,BTB（Branch Target Buffer）,预测错误时的现场恢复,对猜测的指令只译码和准备好操作数，不执行； 对猜测的指令完成运算，但不回送运算结果； 对猜测的指令全部执行完成，但用后援寄存器保存可能被破坏的原始状态。,上次课内容回顾,非线性流水线的调度 解决的问题 预约表禁止向量原始冲突向量流水线状态转移图全部调度方案选取符合要求的最佳方案 流水机器的相关处理 局部相关 种类：RAW、WAR、WAW、RAR（顺序、乱序流动） 解决方法：后推、相关专用通路 全局相关 分支预测：静态预测、动态预测 加快和提前形成条件码 延迟转移 加

35、快短循环处理,加快和提前形成条件码 加快单条指令内部条件码的形成，如Amdahl 470v/6 在一段程序内提前形成条件码，如循环程序，P119 延迟转移 调整指令顺序 加快短循环程序的处理：小于5条语句的短循环比例占87%。 恒猜测循环成功方向（首尾联接）。 一次性取入指缓并暂停预取；如IBM360 “向后8条”检查。要求循环长度小于指缓。,4.7.4 控制相关的其它处理方法,在一段程序内提前形成条件码,MOV SI,-2 MOV DI,-2 MOV CX,10 L:INC SI INC SI INC DI INC DI MOV AX,ASI MOV BDI,AX DEC CX JNZ L,

36、延迟转移技术,ADD R1,R2 JMP NEXT2 NEXT1:SUB R3,R4 NEXT2:MOV R4,A,DO循环的语句数目,4.7.5 中断处理,不精确断点法 不允许再进入新指令，让已经进入流水线的指令全部执行完成，再进入中断处理程序。（中断响应时刻不是中断请求的时刻） 优点：硬件少，控制简单 缺点：中断响应时间长 精确断点法 采用大量后援寄存器，把整条流水线中所有指令的执行结果和现场都保存下来，对中断及时响应并在中断处理完成后恢复到精确断点 优点：可以正确处理程序性错误和机器故障，便于程序调试。 缺点：硬件代价高，控制逻辑复杂,4.8 超标量、超流水线和VLIW,4.8.1 超标

37、量处理机 4.8.2 超流水线处理机 4.8.3 超标量超流水线处理机 4.8.4 VLIW处理机,4.8.1 超标量处理机-基本概念,单发射基准流水线（一般流水线）,同时发射多条指令,4.8.1 超标量处理机-基本概念,每个机器周期同时发射多条指令并产生多个结果。 主要是借助硬件资源重复来实现空间上的并行操作。 最大并行度取决于硬件技术与编译器结合所能够达到的最大指令级并行性。 主要特点： 有多个性能不同的处理部件，采用多条流水线并行处理； 能同时对若干条指令进行译码，将可并行执行的指令送往不同的执行部件，从而达到在每个周期启动多条指令的目的； 在程序运行期间由硬件（通常是状态记录部件和调度

38、部件）完成指令调度。 典型处理机：P101,4.8.1 超标量处理机-调度方法,发射顺序 顺序发射（in-order issue） 乱序发射（out-order issue） 完成顺序 顺序完成（in-order completion） 乱序完成（out-order completion ） 调度方法 顺序发射顺序完成 顺序发射乱序完成 乱序发射乱序完成,例4.5,流水线如图，执行如下程序 I1：LOAD R0，A I2：ADD R1，R0 I3：LOAD R2，B I4：MUL R3，R4 I5：AND R4，R5 I6：ADD R2，R5 问题 列出全部数据相关 顺序发射顺序完成 顺序发射

39、乱序完成 顺序发射乱序完成，有相关专用通路,乱序发射乱序完成，有相关专用通路,例4.5,I1：LOAD R0，A I2：ADD R1，R0 I3：LOAD R2，B I4：MUL R3，R4 I5：AND R4，R5 I6：ADD R2，R5 列出全部数据相关 I2与I1关于R0有RAW相关； I5与I4关于R4有WAR相关； I6与指令I3关于R2同时有RAW相关和WAW相关。,例4.5,顺序发射顺序完成 I1：LOAD R0，A I2：ADD R1，R0 I3：LOAD R2，B I4：MUL R3，R4 I5：AND R4，R5 I6：ADD R2，R5,例4.5,顺序发射乱序完成 I1

40、：LOAD R0，A I2：ADD R1，R0 I3：LOAD R2，B I4：MUL R3，R4 I5：AND R4，R5 I6：ADD R2，R5,例4.5,顺序发射乱序完成，有相关专用通路 I1：LOAD R0，A I2：ADD R1，R0 I3：LOAD R2，B I4：MUL R3，R4 I5：AND R4，R5 I6：ADD R2，R5,例4.5,乱序发射乱序完成，有相关专用通路 I1：LOAD R0，A I2：ADD R1，R0 I3：LOAD R2，B I4：MUL R3，R4 I5：AND R4，R5 I6：ADD R2，R5 数据相关和执行段资源相关如图所示,？,4.8.2

41、 超流水线处理机,采用的基本技术是细化流水线（大于8段）、增加级数、提高主频。 在每个基本时钟周期内并发（非同时）发射多条指令（且每一时刻只发射一条指令），并产生多个结果的流水线。 与超标量流水线的不同点：每一节拍仍只流出一个结果，但节拍只是机器时钟周期的几分之一，所以在一个基本时钟周期内，流水线仍可流出几个结果。着重开发时间并行性。 如1991年2月MIPS公司的64位RISC计算机 MIPS R4000，实现的是MIPS 3指令集，有8个流水段，即最多可达8条指令同时在流水线中，流水以每时钟周期两段的速率在流水线中推进。,4.8.2 超流水线处理机,每周期分时发射3次,4.8.3 超标量超

42、流水线处理机,超标量流水线与超流水流水线的结合。 每个时钟周期发射多次，每次发射多条指令。 如1992年，美国DEC公司（已被Compaq公司并购）推出的 Alpha 21064处理器，就采用了超标量超流水结构。,4.8.3 超标量超流水线处理机,每周期分时发射3次，每次发射3条,上次课内容回顾,流水机器的相关处理 局部相关 种类：RAW、WAR、WAW、RAR 解决方法：后推、相关专用通路 全局相关 分支预测：静态预测、动态预测 加快和提前形成条件码 延迟转移 加快短循环处理 中断处理 不精确断点 精确断点,上次课内容回顾,先进流水技术动态调度 集中式记分板机制 分布式Tomasulo方法

43、指令级高度并行的超级处理机 超标量处理机：资源重复，每个周期同时发射多条 超流水线处理机：流水细化，每个周期分时发射多条 超标量超流水线处理机：两者结合，更高ILP 超长指令字处理机,4.8.4 VLIW处理机,指令字超长（可达数百位），每个指令字包含多个操作字段，每个操作字段控制一个功能部件，相当于同时执行多条指令，是一种单指令多操作码多数据的系统结构（SIMOMD）。 可看成是超标量处理器的一个极端，所有独立或不相关的操作在编译时已打包在一起，压缩成一条VLIW指令（由编译软件完成），运行时不再用软件或硬件检测其并行性。 如80年代早期Multiflow计算机的指令字可以是256位或102

44、4位。Multiflow VLIW处理器是用微程序控制实现的。256位的Multiflow模型允许最多有7条指令并发地执行。失败原因主要是无法得到真正强有力的编译器。,4.8.4 VLIW处理机,单指令多操作码,相当于同时执行多条指令,1、VLIW处理机的流水工作方式,0 1 2 3 4 5 6 7 时间,每拍启动一条长指令，执行3个操作，相当于3条指令，要求并行度=3,2、VLIW处理机的优、缺点,优点： 并行操作的同步全在编译时间完成，比超标量效率更高。 当短格式用户代码中有高的可用ILP（指令级并行度）时，VLIW程序的代码长度要短得多。即经编译的VLIW程序有短得多的执行时间。 大大简化了运行时的资源调度，因为VLIW体系结构中的指令并行性和数据移动完全是在编译时完成。 缺点： 需要智能编译器的支持； 软件兼容性差； 软件的可移植性差。,VLIW与超标量的比较,4.8.4 VLIW处理机,Intel和HP联合开发基于IA-64结构的处理器已重新唤起使用超长指令字方法开发更多并行性的兴趣。 VLIW的特征是以硬件最容易执行的方式排列指令，与现在超标量技术单以硬件作并行处理方式不同。 当然，目前超标量