第5章 标量处理机.ppt

1、第5章 标量处理机,5.1 先行控制技术 5.2 流水线技术 5.3 相关性分析技术 5.4 超标量处理机 5.5 超流水线处理机 5.6 超标量超流水线处理机,5.1 先行控制技术,5.1.1 指令的重叠执行方式 5.1.2 先行控制方式的原理 5.1.3 处理机结构 5.1.4 指令执行序列 5.1.5 先行缓冲栈 5.1.6 缓冲深度的设计方法,5.1.1 指令的重叠执行方式,1.顺序执行方式 执行n条指令所用的时间为：如果每段时间都为t，则执行n条指令所用的时间为：T3 n t主要优点：控制简单，节省设备 主要缺点：速度慢，功能部件的利用率低,2.一次重叠执行方式 如果两个过程的时间相

2、等，则执行n条指令的时间为：T(1+2n)t主要优点：指令的执行时间缩短，功能部件的利用率明显提高。 主要缺点：需要增加一些硬件，控制过程稍复杂。,3.二次重叠执行方式 如果三个过程的时间相等，执行n条指令的时间为：T(2n）t 在理想情况下，处理机中同时有三条指令在执行。 处理机的结构要作比较大的改变，需要采用先行控制技术。,5.1.2 先行控制方式的原理,1.采用二次重叠执行方式必须解决两个问题： (1)有独立的取指令部件、指令分析部件和指令执行部件把一个集中的指令控制器，分解成三个独立的控制器：存储控制器、指令控制器、运算控制器 (2)要解决访问主存储器的冲突问题取指令、分析指令、执行指

3、令都可能要访问存储器,2.解决访存冲突的方法： (1)采用低位交叉存取方式：这种方法不能根本解决冲突问题。指令、读操作数、写结果。 (2)两个独立的存储器：独立的指令存储器和数据存储器。 如果再规定，执行指令所需要的操作数和执行结果只写到通用寄存器，则取指令、分析指令和执行指令就可以同时进行。 在许多高性能处理机中，有独立的指令Cache和数据Cache。这种结构被称为哈佛结构。,(3)采用先行控制技术采用先行控制技术的关键是缓冲技术和预处理技术。 缓冲技术通常用在工作速度不固定的两个功能部件之间。设置缓冲栈的目的是用来以平滑功能部件之间的工作速度。 在采用了缓冲技术和预处理技术之后，运算器能

4、够专心于数据的运算，从而大幅度提高程序的执行速度。,5.1.3 处理机结构,1.三个独立的控制器： 存储控制器、指令控制器、运算控制器。 2.四个缓冲栈： 先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后行写数栈。 3.处理机组成,4.先行指令缓冲栈的组成 作用：只要指令缓冲栈没有充满，就自动发出取指令的请求。设置两个程序计数器： 先行程序计数器PC1，用来指示取指令， 现行程序计数器PC，记录指令分析器正在分析的指令地址。 5.存在的主要问题： 各类指令“分析”和“执行”的时间相差很大 数据相关 转移或转子程序指令,先行缓冲站的组成,5.1.4 指令执行时序,设置了指令缓冲栈，取指令的时间就可

5、以忽略不计。 一条指令的执行可分为2个过程 1.分析指令和执行指令时间不相等时的情况,2.采用先行缓冲栈的指令执行过程先行读数栈,先行操作栈,后行写数栈。理想情况下，指令执行部件应该一直忙碌。连续执行n条指令的时间为：,5.1.5 先行缓冲栈,设置先行缓冲栈的目的：使指令分析器和指令执行部件能够独立工作。 1.先行指令缓冲栈： 处于主存储器与指令分析器之间 用它来平滑主存储器取指令和指令分析器使用指令之间的速度差异 RR型指令，不必处理，直接送先行缓冲栈 RS型指令，主存有效地址送先行读数栈，用该先行读数栈的寄存器编号替换指令中的主存地址码部分，形成RR*指令送先行缓冲栈,RI型指令，指令中的

6、立即数送先行读数栈，用该先行读数栈的寄存器编号替换指令中的立即数部分，形成RR*指令送先行缓冲栈 转移指令，一般在指令分析器中直接执行。 2.先行操作栈 处于指令分析器和运算控制器之间 使指令分析器和运算器能够各自独立工作。 采用先进先出方式工作，由指令寄存器堆和控制逻辑组成。,3.先行读数栈 处于主存储器与运算器之间 滑运算器与主存储器的工作 每个缓冲寄存器由地址寄存器、操作数寄存器和标志三部分组成。也可以把地址寄存器和操作数寄存器合为一个。 当收到从指令分析器中送来的有效地址时，就向主存申请读操作数。 读出的操作数存放在操作数寄存器中或覆盖掉地址寄存器中的地址。,4.后行写数栈 每个后行缓

7、冲寄存器由地址寄存器、数据寄存器和标志三部分组成。 指令分析器遇到向主存写结果的指令时，把形成的有效地址送入后行写数栈的地址寄存器中，并用该地址寄存器的编号替换指令的目的地址部分，形成RR*指令送入先行操作栈。 当运算器执行这条RR*型写数指令时， 只要把写到主存的数据送到后行写数栈的数据寄存器中即可。,5.采用先行控制方式时一个程序的执行情况：,5.1.6 缓冲深度的设计方法,以静态分析为主，通过模拟来确定缓冲深度。 1.先行指令缓冲栈的设计考虑两种极端情况：假设缓冲深度为DI (1)先行指令缓冲栈已经充满 指令流出的速度最快，例如连续分析RR型指令，设这种指令序列的最大长度为L1，平均分析

8、一条这种指令的时间为t1； 指令流入的速度最慢，设平均取一条指令的时间为t2。从主存储器中取到先行指令缓冲栈中的指令条数是L1DI条。,应该满足如下关系：L1 t1(LIDI) t2计算出缓冲深度为：如果这种指令流的连续长度超过L1，则先行指令缓冲栈失去作用。 (2)先行指令缓冲栈原来为空 输入端指令流入的速度最快，每次取指令的时间最短；设这种指令序列的最大长度为 L2，平均取一条这种指令的时间为 t2；,输出端指令流出的速度最慢，指令分析器连续分析最难分析的指令；设平均分析一条指令的时间为 t1。分析的指令条数是L2DI条。 应该满足如下关系：(L2DI) t1LI t2计算出缓冲深度为：如

9、果这种指令流的连续长度超过L2，先行指令缓冲栈失去缓冲作用。,2.设计举例 在一般处理机中连续执行短指令的概率大。 例5.1：一个采用先行控制方式的处理机，指令分析器分析一条指令用一个周期，到主存储器中取一条指令装入先行指令缓冲栈平均用4个周期，如果这种指令的平均长度为9，即90的指令是执行时间短的指令。 解：计算先行指令缓冲栈的缓冲深度为：,3.先行指令缓冲栈的工作时间关系第1个周期，取走指令k+1，请求取指令 第4个周期末尾，指令k+8取到先行指令缓冲栈 第8个周期末尾，指令k+9取到先行指令缓冲栈 第9个周期，分析指令k+9，先行指令缓冲栈空 第10个周期，指令分析器等待,4.其余缓冲栈

10、的设计原则 一般有关系：DIDCDRDW其中：DI是先行指令缓冲栈的缓冲深度，DC是先行操作栈的缓冲深度，DR是先行读数栈的缓冲深度，DW是后行写数栈的缓冲深度。 例如：IBM370/165机：DI4，DC3，DR2，DW1。我国研制的两台大型计算机：DI8，DCDR4，DW2。DI12，DCDR6，DW2。,空间并行性：设置多个独立的操作部件时间并行性：分时使用同一个部件的不同部分5.2.1 流水线工作原理5.2.2 流水线的分类5.2.3 线性流水线的性能分析5.2.4 非线性流水线的调度,5.2 流水线技术,5.2.1 流水线工作原理,1. 流水寄存器 流水线的每一个阶段称为流水步、流水

11、步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。 在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等。 加入流水寄存器，会增加指令的执行时间。 在一般流水线时空图中不画出流水寄存器。,2.一种指令流水线 一般4至12个流水段，8个流水段的称为超流水线处理机3.流水线时空图,一个浮点加法器流水线的时空图,4.流水线的主要特点 只有连续提供同类任务才能发挥流水线效率 尽量减少因条件分支造成的“断流” 通过编译技术提供连续的相同类型操作 每个流水线段都要设置一个流水寄存器 时间开销：流水线的执行时间加长 是流水线中需要增加的主要硬件 各流水段

12、的时间应尽量相等流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。 流水线需要有“装入时间”和“排空时间”,5.2.2 流水线的分类,1.线性流水线与非线性流水线流水线的各个流水段之间是否有反馈信号 线性流水线（Linear Pipelining）：每一个流水段都流过一次，而且仅流过一次 非线性流水线（Nonlinear Pipelining）：某些流水段之间有反馈回路或前馈回路。 线性流水线能够用流水线连接图唯一表示 非线性流水线必须用流水线连接图和流水线预约表共同表示,2.按照流水线的级别来分处理机级流水线，又称为指令流水线。例如：在采用先行控制器的处理机中，各功能部件之间的流水线

13、,部件级流水线(操作流水线)如浮点加法器流水线宏流水线(Macro Pipelining)处理机之间的流水线称，每个处理机对同一个数据流的不同部分分别进行处理。,3. 单功能流水线与多功能流水线单功能流水线：只能完成一种固定功能的流水线。Cray-1计算机种有12条，YH-1计算机有18条Pentium有一条5段定点和一条8段浮点流水线。Pentium有两条定点和一条浮点指令流水线。多功能流水线：流水线的各段通过不同连接实现不同功能Texas公司的ASC机，8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。,4.静态流水线与动态流水线 静

14、态流水线：同一段时间内，各个功能段只能按照一种方式连接，实现一种固定的功能。,动态流水线：在同一段时间内，各段可以按照不同的方式连接，同时执行多种功能。,5.流水线的其他分类方法 按照数据表示方式：标量流水线和向量流水线 按照控制方式：同步流水线和异步流水线顺序流水线与乱序流水线，乱序流水线又称为无序流水线、错序流水线或异步流水线等。,5.2.3 线性流水线的性能分析,主要指标：吞吐率、加速比和效率 1.吞吐率（Though Put） 流水线吞吐率的最基本公式：其中：n为任务数，k为完成n个任务所用的时间。 各段执行时间相等，输入连续任务情况下，完成n个任务需要的总时间为：Tk(kn1)t其中

15、：k 为流水线的段数，t为时钟周期。,Tk= k t + (n-1) t = (k+n-1)t,吞吐率为：最大吞吐率为：,各段时间不等，完成n个连续任务：吞吐率：最大吞吐率：流水线各段执行时间不相等的解决办法,(1)将“瓶颈”部分再细分（如果可分的话）,2.加速比（Speedup）计算加速比的基本公式：各段执行时间相等，输入连续任务情况下,加速比：最大加速比：各段时间不等，输入连续任务情况下, 实际加速比为：,当流水线段数增加时，需要连续输入的任务数也必须增加,3.效率（Efficiency） 计算流水线效率的一般公式：各流水段时间相等，输入n个连续任务，流水线的效率为：最高效率为： 各流水段

16、时间不等，输入n个连续任务，流水线效率为：,各段设备量或价格不等时，流水线的效率为：即：其中，aik，且k。 流水线的吞吐率、加速比与效率的关系：因为：因此：ETPt，SkE,4. 流水线最佳段数的选择 采用顺序执行方式完成一个任务的时间为t 在同等速度的 k 段流水线上执行一个任务的时间为：tkd (d为流水锁存器的延迟时间) 流水线的最大吞吐率为：P=1(tkd) 流水线的总价格估计为：Cab k，其中：a为功能段身的总价格，b为每个锁存器的价格A.G.Larson把流水线的性能价格比PCR定义为：,求PCR的最大值为：,5. 流水线性能分析举例 对于单功能线性流水线，输入连续任务的情况，

17、通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。 对于输入不连续任务，或多功能流水线，通常采用基本公式计算。 例5.2：用一条4段浮点加法器流水线求8个浮点数的和：ZABCDEFGH,解：Z(AB)(CD)(EF)(GH),解：,5.2.4 非线性流水线的调度,非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。 1.非线性流水线的表示 线性流水线能够用流水线连接图唯一表示 对于非线形流水线，连接图不能唯一表示工作流程，因此，引入流水线预约表 例如：,非线形流水线的连接图和预约表,一张预约表

18、可能与多个流水线连接图相对应,一个流水线连接图对应与多张预约表,2.非线性流水线的冲突启动距离：连续输入两个任务之间的时间间隔流水线冲突：几个任务争用同一个流水段,3.无冲突调度方法 由E.S.Davidson及其学生于1971年提出 禁止向量：预约表中每一行任意两个“”之间距离的集合。上例中为（3，4，6） 冲突向量：C（CmCm-1C2C1）其中：m是禁止向量中的最大值。如果i在禁止向量中，则Ci1，否则Ci0。上例中C(101100),例5.3：一条4功能段的非线性流水线，每个功能段的延迟时间都相等，它的预约表如下：(1)写出流水线的禁止向量和初始冲突向量。(2)画出调度流水线的状态图。

19、(3)求最小启动循环和最小平均启动距离。(4)求平均启动距离最小的恒定循环。,解： (1)禁止向量为：(2，4，6)初始冲突向量：S = 101010 (2)构造状态图S逻辑右移2、4、6位时，不作任何处理，逻辑右移1、3、5和大于等于7时：S右移1位之后：010101101010111111，S右移3位之后：000101101010101111，S右移5位之后：000001101010101011，S右移7位或大于7位后：还原到它本身。,101111右移5位之后：000001101010101011， 101011右移3位之后：000101101010101111， 101011右移5位之后

20、：000001101010101011。,简单循环：状态图中各种冲突向量只经过一次的启动循环。 (3)最小的启动循环为（1，7）和（3，5）,平均启动距离为 4。 (4)启动距离最小的恒定循环为（5）,4.优化调度方法 L.E.Shar于1972年提出流水线最小平均启动距离的限制范围：(1)最小平均启动距离的下限是预约表中任意一行里“”的最多个数。(2)最小平均启动距离小于等于状态图中任意一个简单循环的平均启动距离。(3)最小平均启动距离的上限是冲突向量中1的个数再加上1。 1992年，L.E.Shar又证明了上述限制范围。 最有用的是第1条。预约表中“”最多的行一定是瓶颈流水段,对于例5.3

21、的预约表，在同一行中“”最多的为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。,在非线性流水线中，“”最多的流水段一定是“瓶颈“流水段。 实现最优调度的目标是使“瓶颈”流水段处于忙碌状态，没有空闲周期。 最优调度方法能够使非线性流水线的吞吐率、加速比

22、和效率达到最优。,5.3 相关性分析技术,5.3.1 数据相关 5.3.2 控制相关 5.3.3 条件分支对流水线的影响 5.3.4 静态分支预测技术 5.3.5 动态分支预测技术 5.3.6 提前形成条件码 5.3.7 精确断点与不精确断点,5.3.1 数据相关,数据相关：在执行本条指令的过程中，如果用到的指令、操作数、变址量等是前面指令的执行结果，这种相关称为数据相关。 控制相关：由条件分支指令、转子程序指令、中断等引起的相关。 解决数据相关的方法有两种： 推后处理 设置专用路径。,1.指令相关 发生指令相关的情况：n： STORE R1, n+1n+1： 满足关系： 结果地址(n)指令地

23、址(n+1) 当第n条指令还没有把执行结果写到主存之前，取出的第n+1条指令显然是错误的。 在k个流水段的流水线处理机中，第n条指令要修改从第n+1到第n+ k 指令中的任意一条指令，都可能造成程序执行结果发生错误。,在采用先行控制方式的处理机中，如果执行部件正在执行第n条指令，与下述情况之一发生相关，都可能造成程序执行结果发生错误。 存放在先行操作栈中的指令 正在指令分析器中分析的指令 已经预取到先行指令缓冲栈中的指令 指令执行结果还在后行缓冲栈中的指令 更严重的是：有些分支指令，可能已经在指令分析器中执行完成。,解决指令相关的根本办法是：在程序执行过程中不允许修改指令。 现代程序设计方法要

24、求程序具有再入性，可以被递归调用等，也要求不修改指令。 在IBM370系列机中，用“执行指令”来解决：在程序执行过程中既能够修改指令，程序又具有再入性。“执行指令”执行由第二地址(X2)+(B2)+D2)决定的主存数据区中的指令。,2.主存操作数相关 发生主存操作数相关的指令序列：n：OP A1，A2，A3 ；A1(A2) OP (A3)n+1：OP A1，A2，A3 ；A1(A2) OP (A3) 出现下列情况之一，就发生主存操作数相关：A1（n） A2（n1）A1（n） A3（n1） 解决办法： 运算结果写到通用寄存器，而不写到主存 对于访问主存储器的请求，写结果的优先级高于读操作数。,3

25、. 通用寄存器数据相关 发生寄存器数据相关的可能性很大，影响面也很大n：OP R1，A2 ；R1(R1) OP (A2)n+1：OP R1，R2 ；R1(R1) OP (R2) 发生R1(n)R1(n1)称为R1数据相关。 发生R1(n)R2(n1)称为R2数据相关。,解决通用寄存器数据相关的方法： 方法一：把读操作数、写运算结果与指令执行合在一个节拍。从数据从通用寄存器读出，在运算器中完成运算，结果写回通用寄存器的整个回路中，只有通用寄存器是时序逻辑。当发生下述情况时，不能采用这种方法： 当寄存器个数多时，读写寄存器的时间长 当功能部件数量多时，寄存器的读写端口多 当功能部件的执行时间比较长

26、，或要求指令的执行时间短时,方法二：建立相关专用通路(ByPass) 由于发生寄存器数据相关的情况很普遍，一般计算机系统都采用专用数据通路。 把读通用寄存器、执行操作和写结果分为3个周期，或2个周期。 采用专用数据通路能够缩短1至2个周期。,变址相关：在采用变址寻址方式的处理机中，由于变址量放在寄存器中，因此，可能发生与通用寄存器数据相关类似变址相关,4. LOAD相关LOAD操作的执行时间可能比较长n： LOAD R1， A ；R1(A)n+1： ADD R1， R2 ；R1(R1) OP (R2)如果 R1(n)R2(n1)，或 R1(n)R1(n1)，则发生LOAD数据相关。解决方法：,

27、方法一：由编译器在LOAD之后插入不发生数据相关的指令，由于LOAD的执行时间不确定，不能根本解决问题 方法二：由硬件自动插入空操作，直到LOAD操作完成 在单条流水线处理机中，也可以停止节拍发生器，直到数据从存储器中读出为止。,5.3.2 控制相关,因程序的执行方向可能被改变而引起的相关，也称为全局相关。 主要包括：无条件转移、一般条件转移、复合条件转移、中断等。 1. 无条件转移 在流水线处理机中，无条件转移指令不进入执行流水段，一般在指令译码阶段就实际执行完成。 如果在处理机中设置有指令先行缓冲栈，则要全部或部分作废先行指令缓冲栈中的指令。,如果转移目标指令L不在先行指令缓冲栈中，则要将

28、先行指令缓冲栈中的所有指令全部作废，并等待取出转移目标指令L。 如果转移目标指令L在先行指令缓冲栈中，只要作废先行指令缓冲栈中的部分指令。 无条件转移指令一般对指令执行部件的工作不会造成影响。 为进一步减少无条件转移指令造成的影响，在先行指令缓冲栈的入口处增设一个专门处理无条件转移指令的指令分析器,2.一般条件转移k： ;置条件码CCk+1：JMP(CC) L ;如果CC为真转向LL：当条件码是上一条指令产生时，相关最严重,无论转移是否成功，条转移指令都在指令分析阶段就已经执行完成。 无论转移不成功或不成功，指令分析器要停顿一段时间，等待条件码产生。,如果转移成功：指令L已经在先行指令缓冲栈，

29、指令分析器接着“分析L”，如果指令L不在先行指令缓冲栈，指令分析器要等待一个周期。 转移不成功，对程序执行影响不大， 当转移成功时，不仅指令执行过程变成完全串行，而且要作废先行指令缓冲栈中的大量指令。 在采用流水线方式的处理机中，要通过软件与硬件的多种手段来近可能地降低转移成功的概率，减少转移成功造成的影响。,3.复合条件转移k：OP L ;产生条件码，并决定是否转向LL： 如果转移不成功：不造成任何影响，就象普通的运算型指令一样 如果转移成功：造成的影响比一般条件转移指令还要大得多。全部或部分作废先行指令缓冲栈、先行操作栈、先行读数栈和指令分析器中的指令。 必须采取策略，减小转移成功造成的影

30、响。,5.3.3 条件分支对流水线的影响,处理好条件转移和中断的关键问题有两个： 要确保流水线能够正常工作 减少因“断流”引起的吞吐率和效率的下降 1.条件分支的处理方法 条件转移指令对流水线的影响很大，必须采取措施来减少这种影响。可能的措施有： (1)延迟转移技术和指令取消技术 只能用于单流水线处理机中，且流水线的级数不能太多；,据统计，编译器调度一条指令成功的概率在90以上，而调度两条指令成功的概率只有40左右。 当没有合适的指令可调度时，编译器只能插入空操作。 (2)动态分支预测技术 根据近期转移是否成功的记录来预测下一次转移的方向。 所有的动态转移预测方法都能够随程序的执行过程动态地改

31、变转移的预测方向。,(2)静态分支预测技术 转移预测的方向是确定的，或者预测转移不成功，或者预测转移成功， 在程序实际执行过程中，转移预测的方向不能改变。 静态转移预测可以只用软件实现，也可用硬件来实现，还可以在转移的两个方向上都预取指令。 TI公司的SuperSPARC处理机采用了静态转移预测技术，而且设置有转移目标缓冲栈，在两个方向上都预取指令。,2.条件分支在流水线中的执行过程 因为第i条指令所需要的条件码由第i-1条指令给出；在一条由k个功能段的流水线中，第i-1条指令要等到第i+k-2条指令进入流水线时才能形成条件码。 转移不成功，猜测正确，流水线的吞吐率和效率没有降低， 转移成功，

32、猜测错误，要先作废流水线中已经执行的i+1、i+2、i+k-2指令；然后再从分支点开始执行第P、p+1、指令。一条k段流水线有k-2个功能段是浪费的。,条件分支指令在流水线中的执行过程,当分支的执行方向猜测错误时，可能造成程序执行结果发生错误。例如，若第i+1条指令是：(R1(R2)R1，寄存器R1中内容就被破坏，整个程序执行的结果是错误的。目前的处理机有两种做法： 一种方法是只进行指令译码和准备好运算所需要的操作数，在转移条件没有形成之前不执行运算； 另一种方法是一直执行到运算完成，但不送回运算结果。,3. 条件分支对流水线性能的影响 假设条件转移指令在一般程序中所占的比例为p，转移成功的概

33、率为q。 n条指令的总的执行时间是：TK-IF(n+k-1)t + npq(k-1)t 有条件转移影响的流水线吞吐率为：有条件转移影响的流水线最大吞吐率为：,流水线吞吐率下降的百分比为：在典型程序中，转移指令占的比例为p20，转移成功的概率为60。 对于一条8功能段的指令流水线，由于条件转移指令的影响，流水线的最大吞吐率要下降：如果指令流水线的功能段数为10，由于条件转移指令的影响，流水线的最大吞吐率将下降一半以下：,5.3.4 静态分支预测技术,静态分支预测：在程序执行过程中转移预测方向不能改变 动态分支预测：在程序执行过程中能够改变转移预测方向 本节讲静态预测技术,下节讲动态预测技术 1.

34、软件“猜测法” 目标：通过编译器尽量降低转移成功的概率。 例如：对于循环程序，普通编译器生成的目标代码，转移成功的概率很高，不成功的只有一次。这种编译结果对流水线极为不利。,软件“猜测法”：通过编译器降低转移成功的概率,2.硬件“猜测法” 方法：通过改变硬件结构来降低转移指令对流水线的影响 在先行指令缓冲栈的人口处设置一个简单的指令分析器，当检测到转移指令时，就把转移目标地址L送入先行程序计数器PC1中，同时保留当前PC1中的内容到另一寄存器中。 转移成功，猜测正确。对转移指令对流水线不造成影响。 转移不成功，用保存下来的地址恢复PC1和PC。 软硬件共同配合，都往同一个方向去猜测。,3.两个

35、先行指令缓冲栈 向前条件转移，转移成功与不成功各50% 在先行指令缓冲栈中增加一个先行目标缓冲栈 按照转移成功的方向预取指令到先行目标缓冲栈中。 先行指令缓冲栈仍然按照转移不成功的方向继续预取指令。 如果转移不成功，则继续分析原来先行指令缓冲栈中指令。 如果转移成功，则分析新增设的先行目标缓冲栈中的指令。,5.3.5 动态分支预测技术,动态转移预测技术的两个关键问题： 如何记录转移历史信息 如何根据记录的转移历史信息预测转移方向 记录转移历史信息的方法有三种： (1)最近一次或几次转移是否成功的信息记录在转移指令中 (2)用一个高速缓冲栈保存条件转移指令的转移目标地址 (3)用Cache保存转

36、移目标地址之后的n条指令,1. 在指令Cache中记录转移历史信息 在指令Cache中专门设置一个字段，称为“转移历史表”。 在执行转移指令时，把转移成功或不成功的信息记录在这个表中。 当下次再执行到这条指令时，转移预测逻辑根据“转移历史表”中记录的信息预测转移成功或不成功。,只记录最近一次转移是否成功的历史信息 如果“转移历史表”中记录的内容是“T”，则预测转移成功，如果记录的是“N”，则按照转移不成功的方向继续取指令。 并用实际转移是否成功的信息来修改“转移历史表”。,记录最近两次转移是否成功的历史信息 图中采用偏向成功的预测策略：只有历史上最近两次执行这条转移指令时转移都没有成功，本次才

37、预测转移不成功 也可以采用其他预测策略,“转移历史表”的修改规则和转移预测规则可以有多种多样， 记录转移预测是否成功的信息。 用最近预测是否成功的信息作为是否转移的依据 当“转移历史表”是空白时，可以有两种做法： 在“转移历史表”中预置转移历史信息。 根据指令本身的偏移字段的符号来预测转移的方向如果偏移字段为负，则预测转移成功，否则预测转移不成功,主要优点： 不必专门设置转移缓冲栈， 所记录的转移历史信息比较少。 例如： DEC公司的Alpha 21064处理机就采用了这种转移预测方法， 在它的一级指令Cache中有一个专门的“转移历史表”字段。 Alpha 21064的结构框图：,2.设置转

38、移目标地址缓冲栈 用高速缓冲栈保存最近k条转移指令的“转移历史表”和转移目标地址 当前指令地址与转移目标缓冲栈中的所有转移指令地址进行比较；如果发现有相等的，则根据所记录的历史信息预测本次转移方向。 根据某种规则修改“转移历史表”。,3.设置转移目标指令缓冲栈 把上面方法中的“转移目标地址”字段改为存放转移目标地址之后的n条指令。 预测转移方向的规则和修改“转移历史表”的规则与上面的方法相同。,5.3.6 提前形成条件码,必要性：对提高流水线的性能非常有效 可能性：可在运算开始或中间产生条件码 对于乘除法，两个源操作数的符号相同结果为正，符号相反结果为负 对于乘法，有一个操作数为0，则乘积为0

39、 被除数为0，商为0； 除数为0，除法结果溢出 同号加或异号减，结果符号与第一操作数相同 异号加或同号减，结果的符号与绝对值大的操作数相同 溢出及是否为0可以通过一个比较器提前产生,只要在一个时钟周期之内产生条件码，流水线就不会“断流”。 如Amdahl470V/6在运算部件的入口处设置药有一个LOCK部件，提前形成条件码 把产生条件码与使用条件码的指令分开LOAD R1,NUM ;循环次数初值装入R1LOOP： ;循体开始DEC R1 ;循环次数减“1”BNE LOOP ;测试循环是否则结束HALT ;程序结束NUM: n,可以编译成如下程序：LOAD R1,NUM ;循环次数装入R1中LO

40、OP：LDEC R1 ;一条专用的;循环次数减1指令 ;循体开始LBNE LOOP ;一条专用的测试循环;是否结束的指令HALT ;程序结束NUM: n ;循环次数 指令LDEC和LBNE使用专用的条件码寄存器,5.3.7 精确断点与不精确断点,对于输入输出设备的中断服务，实际上不需要有精确断点。 比较简单的处理方法是：让已经进入流水线的所有指令都执行完成，断点就是最后进入流水线的那条指令的地址。 对于程序性错误和机器故障等引起的中断，它们出现的概率很低，处理原则：不在于缩短时间，关键是要正确保存现场和正确恢复断点。,不精确断点(Imprecise)，流水线可以不断流 需要的硬件比较少，控制逻

41、辑比较简单 中断响应时间加长采用不精确断点法可能会发生如下两个问题： (1)程序的调试困难 早期的流水线处理机，多采用不精确断点法 近期的流水线处理机一般都采用精确断点法,(2)程序执行的结果可能出错，例如：i：FADD R1, R2 ；(R1)(R2)R1i+1：FMUL R3, R1 ；(R3)(R1)R3 当第i条指令执行到S6段时发现浮点加法结果溢出，于是发出中断服务申请。由于采用不精确断点法，已经进入流水线的第i+1条指令将执行完成；因为第i+1条指令使用了不正确的R1，所以浮点乘法的执行结果是不正确的。 采用精确断(Precise)点法，要设置一定数量的后援寄存器，把整个流水线中所

42、有指令的执行结果和现场都保存下来。,5.4 动态调度技术,5.4.1 顺序流动与乱序流动 5.4.2 乱序流动中的数据相关 5.4.3 数据重定向方法 5.4.4 Tomasulo动态调度算法,实现方法：由硬件动态调整指令执行顺序，以减少数据相关造成的影响。 主要优点： 能够处理在编译时无法确定的相关，并简化编译器设计 在其他流水线机器上编译的目标代码也能够高效运行 用静态调度法生成的代码也能在动态调度法的机器中运行 主要缺点：指令级并行度低，因为只能在比较小的范围内寻找并行性,5.4.1 顺序流动与乱序流动,1.顺序流动方式：任务按顺序流入流水线,也按顺序流出流水线 把如下一段程序输入到这条

43、流水线中：k： R0（R1）k+1： k+2： R2（R0）（R3）k+3： k+4： k+5： ,指令k+2无法继续执行，要在功能段S2中等待。 后续的指令k+4、k+5、等也不能进入流水线。 功能段S3、S4、S5将逐渐空闲。 缺点：吞吐率和效率降低 优点：流水线的控制逻辑比较简单,流水线“断流”，有些功能段“空闲”,2.乱序(Out of order)流动方式：指令流出流水线的顺序与流入流水线的顺序不同。又称为错序流动方式、无序流动方式、异步流动方式等。,5.4.2 乱序流动中的数据相关,在乱序流动方式中，可能发生三种数据相关 写写相关k： LOAD F1, A ;F1（A） 写读相关k

44、+1：FADD F2, F1 ;F2（F2）+（F1）k+2：FMUL F1, F3 ;F1（F1）（F3）k+3：STORE F1, B ;B（F1）读写相关 (1)写读相关：指令k与指令k+1之间关于F1的相关，又称为数据相关、先写后读相关、流相关、WR相关、RAW相关等。,(2)读写相关：指令k+1与指令k+2之间关于F1的相关，变量名相关、先读后写相关、反相关、RW相关、WAR相关等。 (3)写写相关：指令k与指令k+2左边的F1之间的相关关系称为：输出相关、写写相关、WW相关、WAW相关或写后再写相关等。 有时把相关称为“冒险”(hazard)、“竟争” (competition)等

45、。 在程序执行过程中，只有避免相关，执行结果才是正确的。,三种数据相关可以用下列关系式来表示：对于写读相关 D(i) S(j) 对于读写相关 S(i) D(j) 对于写写相关 D(i) D(j) ,5.4.3 数据重定向方法,1.三种数据相关的重定向重定向之前，j只能在i之后执行。重定向之后，可以做到： (1)写读相关，j与i可以同时执行即专用数据通路 (2)写写相关，先后顺序无关 (3)读写相关，先后顺序无关后两种情况又称为“变量换名技术”,2.变量换名技术 用来自动消除读写数据相关和写写数据相关 规则：一个变量只允许定值一次 在三种数据相关中，实际上只有写读数据相关必须依靠硬件、或采用软硬

46、件结合的方法来解决解决方法：推后处理或专用数据通路 在上面的数据重定向图中，把B换成了B，并在以后的都引用B读写数据相关和写写数据相关就不存在了。 一个实际例子：,Loop: LD F0, 0(R1)ADD F0, F2SD 0(R1), F0LD F0, -8(R1)ADD F0, F2SD -8(R1), F0LD F0, -16(R1)ADD F0, F2SD -16(R1), F0LD F0, -24(R1)ADD F0, F2SD -24(R1), F0SUBI R1, R1, #32BNEZ R1, Loop,Loop: LD F0, 0(R1)LD F4, -8(R1)LD F6

47、, -16(R1)LD F8, -24(R1)ADD F0，F2ADD F4，F2ADD F6，F2ADD F8，F2SD 0(R1), F0SD -8(R1), F4SUBI R1, R1, #32SD -16(R1), F6BNEZ R1, LoopSD -24(R1), F8,3.一个简单的程序：k： LOAD F1, Ak+1： FADD F1, F2k+2： FMUL F1, F3k+3： STORE F1, B,专门设置：AFADD、FMULB、FADDFMUL三条专用路径。 撤消：F1FADD、F1FMUL、FADDF1 、AF1的路径。,5.4.4 Tomasulo动态调度算法

48、,实用的动态调度算法主要有两种: (1)集中控制：CDC计分牌(scorebord)算法，最先在CDC 6600大型机中采用。 (2)分散控制：Tomasulo算法, 公共数据总线法，令牌法等。最早在大型机IBM 360/91的浮点处理部件中被采用。 以上面的一段程序为例说明Tomasulo算法k： LOAD F1, Ak+1： FADD F1, F2k+2： FMUL F1, F3k+3： STORE F1, B,5.5 超标量处理机,5.5.1 基本结构5.5.2 单发射与多发射5.5.3 多流水线调度5.5.4 资源冲突5.5.5 超标量处理机性能,三种主流处理机：超标量处理机超流水线处

49、理机超标量超流水线处理机,5.5.1 基本结构,普通标量流水线处理机：一条指令流水线，一个多功能操作部件，每个时钟周期平均执行指令的条数小于1。 多操作部件标量处理机：一条指令流水线，多个独立的操作部件，指令级并行度小于1。 超标量处理机典型结构：多条并行工作的指令流水线，多个独立的操作部件，指令级并行度（ILP）大于1。,Motorola公司的MC88110 有10个操作部件 两个寄存器堆： 整数部件通用寄存器堆，32个32位寄存器 浮点部件扩展寄存器堆，32个80位寄存器 缓冲深度为4的先行读数栈 缓冲深度为3的后行写数栈 两个独立的高速Cache中，各为8KB，采用两路组相联方式 转移目标指令Cache，用于存放另一条分支上的指令,