并行计算机体系结构第三章.ppt

《并行计算机体系结构第三章.ppt》由会员分享，可在线阅读，更多相关《并行计算机体系结构第三章.ppt（215页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 流水和向量处理3.1提高计算机速度的措施MIPS=IPC*fc其中其中IPC为每拍流出的指令条数。提高为每拍流出的指令条数。提高IPC和和fc是提高是提高计算机速度最直接最有效的方法。计算机速度最直接最有效的方法。提高提高IPC：增加每拍并行流出的指令条数和配置更多的：增加每拍并行流出的指令条数和配置更多的功能部件。空间并行。功能部件。空间并行。提高提高fc：功能部件应该能在更高的频率下工作。时间平：功能部件应该能在更高的频率下工作。时间平行。行。可以用可以用P=O（s*f）衡量系统的潜在性能，）衡量系统的潜在性能，s是与设备是与设备量成正比的功能部件并行度，量成正比的功能部件并行度，

2、f是主频。是主频。3.1.1 提高频率提高系统的频率是提高系统性能的最直接的方法，但提高系统的频率是提高系统性能的最直接的方法，但是频率的提高具有很大的难度：是频率的提高具有很大的难度：1.器件的速度和集成度器件的速度和集成度 2.流水线分站的代价和效率流水线分站的代价和效率 3.高速信号传输高速信号传输 4.时钟沿的离散时钟沿的离散 5.高密度组装工艺和冷却技术高密度组装工艺和冷却技术*往往当通过提高频率来提高计算机的速度不能满足要往往当通过提高频率来提高计算机的速度不能满足要求时，我们才考虑空间并行性求时，我们才考虑空间并行性3.1.1 空间并行为了达到更高的主频，需要特殊技术并且代价巨大

3、。为了达到更高的主频，需要特殊技术并且代价巨大。这导致了大规模并行处理系统这导致了大规模并行处理系统MPP的出现。的出现。可以设置多个功能部件支持向量、超标量、超长指令可以设置多个功能部件支持向量、超标量、超长指令字和超流水结构。空间并行性可以有效提高计算机速字和超流水结构。空间并行性可以有效提高计算机速度，速度提高的最大倍数度，速度提高的最大倍数=e 性价比：性价比：PCR=1/(T/k+td)(C+kd)其中其中k为流水线站数，为流水线站数，T为每段执行时间，为每段执行时间，td为站流水为站流水线的延迟时间，线的延迟时间，C为功能部件的价格。为功能部件的价格。流水线的设计原理令（令（PCR

4、）=0，得到，得到因为因为（PCR）0，所以此时，所以此时k站流水线的性价比最高站流水线的性价比最高同时为了减少站寄存器的位数，分段时往往选在连线最少同时为了减少站寄存器的位数，分段时往往选在连线最少的部位。如果每段时间无法保持一致，则的部位。如果每段时间无法保持一致，则M（最大段执（最大段执行时间）和行时间）和td同时决定了流水线的工作周期。其频率为同时决定了流水线的工作周期。其频率为1/(M+td).由于工程实现时元件的布局和器件时间参数离散等原因，由于工程实现时元件的布局和器件时间参数离散等原因，到达各站寄存器的时钟信号时离散的。到达各站寄存器的时钟信号时离散的。流水线的设计原理设相邻两

5、站的最大离散值为设相邻两站的最大离散值为，则工作频率降低为，则工作频率降低为1/(M+td+)。书本书本35-36页，图页，图3.2 信号穿透问题。信号穿透问题。非线性流水线的调度非线性流水线调度的任务是要找出一个最小的循环周非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。效率最高。1.1.非线性流水线的表示非线性流水线的表示线性流水线能够用流水线连接图唯一表示线性流水线能够用流水线连接图唯一表示对于非线形流水线

6、，连接图不能唯一表示工作流程，对于非线形流水线，连接图不能唯一表示工作流程，因此，引入流水线预约表因此，引入流水线预约表例如：例如：非线形流水线的连接图和预约表非线形流水线的连接图和预约表 一张预约表可能与多个流水线连接图相对应 一个流水线连接图对应于多张预约表2.2.非线性流水线的冲突非线性流水线的冲突 启动距离：连续输入两个任务之间的时间间隔启动距离：连续输入两个任务之间的时间间隔 流水线冲突：几个任务争用同一个流水段流水线冲突：几个任务争用同一个流水段3.3.无冲突调度方法无冲突调度方法由由E.S.DavidsonE.S.Davidson及其学生于及其学生于19711971年提出年提出禁

7、止向量禁止向量：预约表中每一行任意两个：预约表中每一行任意两个“”之间距离之间距离的集合。上例中为的集合。上例中为（3 3，4 4，6 6）冲突向量冲突向量：C（CmCm-1C2C1）其中：其中：m是是禁止向量中的最大值。禁止向量中的最大值。如果如果i在禁止向量中，则在禁止向量中，则Ci1，否则，否则Ci0。上上例中例中C C(101100)(101100)例：一条例：一条4 4功能段的非线性流水线，每个功能段的延功能段的非线性流水线，每个功能段的延迟时间都相等为迟时间都相等为t ，它的预约表如下：，它的预约表如下：(1)(1)写出流水线的禁止向量和初始冲突向量。写出流水线的禁止向量和初始冲突

8、向量。(2)(2)画出调度流水线的状态图。画出调度流水线的状态图。(3)(3)求最小启动循环和最小平均启动距离。求最小启动循环和最小平均启动距离。(4)(4)求平均启动距离最小的恒定循环。求平均启动距离最小的恒定循环。(5)(5)按照最小启动循环连续输入按照最小启动循环连续输入4 4个任务，求流水线个任务，求流水线实际吞吐率。实际吞吐率。解：解：(1)(1)禁止向量为：禁止向量为：(2(2，4 4，6)6)初始冲突向量：初始冲突向量：S=101010S=101010(2)(2)构造状态图构造状态图 S S逻辑右移逻辑右移2 2、4 4、6 6位时，不作任何处理，位时，不作任何处理，逻辑右移逻辑

9、右移1 1、3 3、5 5和大于等于和大于等于7 7时：时：S S右移右移1 1位之后：位之后：010101101010010101101010111111111111，S S右移右移3 3位之后：位之后：000101101010000101101010101111101111，S S右移右移5 5位之后：位之后：000001101010000001101010101011101011，S S右移右移7 7位或大于位或大于7 7位后：还原到它本身。位后：还原到它本身。101111101111右移右移5 5位之后：位之后：000001101010000001101010101011101011，

10、101011101011右移右移3 3位之后：位之后：000101101010000101101010101111101111，101011101011右移右移5 5位之后：位之后：000001101010000001101010101011101011。简单循环：简单循环：状态图中各种冲突向量只经过一次的启动循环。状态图中各种冲突向量只经过一次的启动循环。(3)(3)最小的启动循环最小的启动循环为（为（1 1，7 7）和（）和（3 3，5 5）,平均启动距离为平均启动距离为 4 4。(4)(4)启动距离最小的恒定循环为（启动距离最小的恒定循环为（5 5）(4)(4)按照最小启动循环（按照最小

11、启动循环（1 1，7 7）连续输入）连续输入4 4个任务，流水线实际个任务，流水线实际吞吐率为：吞吐率为：1/1/（4 4 t）数据相关(局部相关)数据相关：在执行本条指令的过程中，如果用到的指数据相关：在执行本条指令的过程中，如果用到的指令、操作数、变址量等是前面指令的执行结果，这令、操作数、变址量等是前面指令的执行结果，这种相关称为数据相关。种相关称为数据相关。控制相关：由条件分支指令、转子程序指令、中断等控制相关：由条件分支指令、转子程序指令、中断等引起的相关。引起的相关。解决数据相关的方法有两种：解决数据相关的方法有两种：推后处理推后处理设置专用路径设置专用路径1.1.指令相关指令相关

12、发生指令相关的情况：发生指令相关的情况：n：STORE R1,STORE R1,n+1+1 n+1+1：满足关系：满足关系：结果地址结果地址(n)指令地址指令地址(n+1)+1)当第当第n条指令还没有把执行结果写到主存之前，取出条指令还没有把执行结果写到主存之前，取出的第的第n+1+1条指令显然是错误的。条指令显然是错误的。在在k个流水段的流水线处理机中，第个流水段的流水线处理机中，第n条指令要修改从条指令要修改从第第n+1到第到第n+k 指令中的任意一条指令，都可能指令中的任意一条指令，都可能造成程序执行结果发生错误。造成程序执行结果发生错误。在采用先行控制方式的处理机中，如果执行部件正在在

13、采用先行控制方式的处理机中，如果执行部件正在执行第执行第n条指令，与下述情况之一发生相关，都可条指令，与下述情况之一发生相关，都可能造成程序执行结果发生错误能造成程序执行结果发生错误:存放在先行操作栈中的指令存放在先行操作栈中的指令正在指令分析器中分析的指令正在指令分析器中分析的指令已经预取到先行指令缓冲栈中的指令已经预取到先行指令缓冲栈中的指令更严重的是：有些分支指令，可能已经在指令分析器更严重的是：有些分支指令，可能已经在指令分析器中执行完成。中执行完成。解决指令相关的根本办法是：解决指令相关的根本办法是：在程序执行过程中不允许修改指令。在程序执行过程中不允许修改指令。现代程序设计方法要求

14、程序具有再入性，可以被递归现代程序设计方法要求程序具有再入性，可以被递归调用等，也要求不修改指令。调用等，也要求不修改指令。在在IBM370IBM370系列机中，用系列机中，用“执行执行”指令来解决：在程序指令来解决：在程序执行过程中既能够修改指令，程序又具有再入性。执行过程中既能够修改指令，程序又具有再入性。“执行执行”指令执行由第二地址指令执行由第二地址(X(X2 2)+(B)+(B2 2)+D)+D2 2)决定的主存数据区决定的主存数据区中的指令。中的指令。2.2.主存操作数相关主存操作数相关(相邻两条指令之间出现对主存同相邻两条指令之间出现对主存同一单元要求先写后读的关联一单元要求先写

15、后读的关联)发生主存操作数相关的指令序列：发生主存操作数相关的指令序列：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.3.通用寄存器数据相关通用寄存器数据相关发生寄存器数据相关的可能

16、性很大，影响面也很大发生寄存器数据相关的可能性很大，影响面也很大 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)称为称为R R2数据数据相关。相关。解决通用寄存器数据相关的方法：解决通用寄存器数据相关的方法：方法一：把读操作数、写运算结果与指令执行合在一方法一：把读操作数、写运算结果与指令执行合在一个节拍。个节拍。采用一种典型的运算器结构，通用寄存器到运算器采用一种典型的运算器结构，通用寄存器到运算器之间建立有直接数据通路，即不设置缓冲寄存器或之间建

17、立有直接数据通路，即不设置缓冲寄存器或锁存器。锁存器。当发生下述情况时，不能采用这种方法：当发生下述情况时，不能采用这种方法：当寄存器个数多时，读写寄存器的时间长当寄存器个数多时，读写寄存器的时间长当功能部件的执行时间比较长，或要求指令的执行时当功能部件的执行时间比较长，或要求指令的执行时间短时间短时 方法二：建立相关专用通路方法二：建立相关专用通路(ByPass)(ByPass)由于发生寄存器数据相关的情况很普遍，一般计算机由于发生寄存器数据相关的情况很普遍，一般计算机系统都采用专用数据通路，以增加硬件为代价减少系统都采用专用数据通路，以增加硬件为代价减少速度损失。速度损失。在运算器的输出端

18、到锁存器输入端之间建立一条专用在运算器的输出端到锁存器输入端之间建立一条专用的数据通路。的数据通路。变址相关：变址相关：在采用变址寻址方式的处理机中，由于变在采用变址寻址方式的处理机中，由于变址量放在寄存器中，因此，可能发生与通用寄存器址量放在寄存器中，因此，可能发生与通用寄存器数据相关类似变址相关，发生概率较高，通常多采数据相关类似变址相关，发生概率较高，通常多采用设置专用通路的方法解决相关问题。用设置专用通路的方法解决相关问题。4.LOAD4.LOAD相关相关 LOAD操作的执行时间可能比较长 n：LOAD R1，A ；R1(A)n+1：ADD R1，R2 ；R1(R1)OP(R2)如果

19、R1(n)R2(n1)，或 R1(n)R1(n1)，则发生LOAD数据相关。解决方法：解决方法：方法一：方法一：由编译器在由编译器在LOADLOAD之后插入不发生数据相关的之后插入不发生数据相关的指令，指令，由于由于LOADLOAD的执行时间不确定，不能根本解决的执行时间不确定，不能根本解决问题问题方法二：方法二：由硬件自动插入空操作，直到由硬件自动插入空操作，直到LOADLOAD操作完成操作完成在单条流水线处理机中，也可以停止节拍发生器，直在单条流水线处理机中，也可以停止节拍发生器，直到数据从存储器中读出为止。到数据从存储器中读出为止。控制相关(全局相关)因程序的执行方向可能被改变而引起的相

20、关，也称为因程序的执行方向可能被改变而引起的相关，也称为全局相关全局相关。主要包括：主要包括：无条件转移、一般条件转移、复合条件转无条件转移、一般条件转移、复合条件转移、中断移、中断等。等。1.1.无条件转移无条件转移在流水线处理机中，无条件转移指令不进入执行流水在流水线处理机中，无条件转移指令不进入执行流水段，一般在指令译码阶段就实际执行完成。段，一般在指令译码阶段就实际执行完成。如果在处理机中设置有指令先行缓冲栈，则要全部或如果在处理机中设置有指令先行缓冲栈，则要全部或部分作废先行指令缓冲栈中的指令。部分作废先行指令缓冲栈中的指令。如果转移目标指令如果转移目标指令L L不在先行指令缓冲栈中

21、不在先行指令缓冲栈中，则要将，则要将先行指令缓冲栈中的所有指令全部作废，并等待取先行指令缓冲栈中的所有指令全部作废，并等待取出转移目标指令出转移目标指令L L。如果转移目标指令如果转移目标指令L L在先行指令缓冲栈中在先行指令缓冲栈中，只要作废，只要作废先行指令缓冲栈中的部分指令。先行指令缓冲栈中的部分指令。无条件转移指令一般对指令执行部件的工作不会造成无条件转移指令一般对指令执行部件的工作不会造成影响。影响。为进一步减少无条件转移指令造成的影响，为进一步减少无条件转移指令造成的影响，在先行指在先行指令缓冲栈的入口处增设一个专门处理无条件转移指令缓冲栈的入口处增设一个专门处理无条件转移指令的指

22、令分析器令的指令分析器2.2.一般条件转移一般条件转移 k：;置条件码CC k+1：JMP(CC)L ;如果CC为真转向L L：当条件码是上一条指令产生时，相关最严重当条件码是上一条指令产生时，相关最严重无论转移是否成功，条转移指令都在指令分析阶段就无论转移是否成功，条转移指令都在指令分析阶段就已经执行完成。已经执行完成。无论转移不成功或不成功，指令分析器要停顿一段时无论转移不成功或不成功，指令分析器要停顿一段时间，等待条件码产生。间，等待条件码产生。如果转移成功：指令如果转移成功：指令L L已经在先行指令缓冲栈，指令已经在先行指令缓冲栈，指令分析器接着分析器接着“分析分析L L”，如果指令，

23、如果指令L L不在先行指令缓不在先行指令缓冲栈，指令分析器要等待一个周期。冲栈，指令分析器要等待一个周期。转移不成功，对程序执行影响不大，转移不成功，对程序执行影响不大，当转移成功时，不仅指令执行过程变成完全串行，而当转移成功时，不仅指令执行过程变成完全串行，而且要作废先行指令缓冲栈中的大量指令。且要作废先行指令缓冲栈中的大量指令。在采用流水线方式的处理机中，要通过软件与硬件的在采用流水线方式的处理机中，要通过软件与硬件的多种手段来近可能地降低转移成功的概率，减少转多种手段来近可能地降低转移成功的概率，减少转移成功造成的影响。移成功造成的影响。3.3.复合条件转移复合条件转移 k k：OP L

24、;OP L;产生条件码，并决定是否转向产生条件码，并决定是否转向L L L L：如果转移不成功：不造成任何影响，就象普通的运算如果转移不成功：不造成任何影响，就象普通的运算型指令一样型指令一样如果转移成功：造成的影响比一般条件转移指令还要如果转移成功：造成的影响比一般条件转移指令还要大得多。大得多。全部或部分作废先行指令缓冲栈、先行操全部或部分作废先行指令缓冲栈、先行操作栈、先行读数栈和指令分析器中的指令。作栈、先行读数栈和指令分析器中的指令。必须采取策略，减小转移成功造成的影响。必须采取策略，减小转移成功造成的影响。条件分支对流水线的影响处理好条件转移和中断的关键问题有两个：处理好条件转移和

25、中断的关键问题有两个：要确保流水线能够正常工作要确保流水线能够正常工作减少因减少因“断流断流”引起的吞吐率和效率的下降引起的吞吐率和效率的下降1.1.条件分支的处理方法条件分支的处理方法条件转移指令对流水线的影响很大，必须采取措施来条件转移指令对流水线的影响很大，必须采取措施来减少这种影响。可能的措施有：减少这种影响。可能的措施有：(1)(1)延迟转移技术和指令取消技术延迟转移技术和指令取消技术只能用于单流水线处理机中，且流水线的级数不能太只能用于单流水线处理机中，且流水线的级数不能太多；多；据统计，据统计，编译器调度一条指令成功的概率在编译器调度一条指令成功的概率在90以以上，而调度两条指令

26、成功的概率只有上，而调度两条指令成功的概率只有40左右。左右。当没有合适的指令可调度时，编译器只能插入空操作。当没有合适的指令可调度时，编译器只能插入空操作。(2)(2)动态分支预测技术动态分支预测技术根据近期转移是否成功的记录来预测下一次转移的方根据近期转移是否成功的记录来预测下一次转移的方向。向。所有的动态转移预测方法都能够随程序的执行过程动所有的动态转移预测方法都能够随程序的执行过程动态地改变转移的预测方向。态地改变转移的预测方向。(3)(3)静态分支预测技术静态分支预测技术转移预测的方向是确定的，或者预测转移不成功，或转移预测的方向是确定的，或者预测转移不成功，或者预测转移成功，者预测

27、转移成功，在程序实际执行过程中，转移预测的方向不能改变。在程序实际执行过程中，转移预测的方向不能改变。静态转移预测可以只用软件实现，也可用硬件来实现，静态转移预测可以只用软件实现，也可用硬件来实现，还可以在转移的两个方向上都预取指令。还可以在转移的两个方向上都预取指令。TITI公司的公司的SuperSPARCSuperSPARC处理机采用了静态转移预测技术，处理机采用了静态转移预测技术，而且设置有转移目标缓冲栈，在两个方向上都预取而且设置有转移目标缓冲栈，在两个方向上都预取指令。指令。2.2.条件分支在流水线中的执行过程条件分支在流水线中的执行过程因为第因为第i i条指令所需要的条件码由第条指

28、令所需要的条件码由第i-1i-1条指令给出；条指令给出；在一条由在一条由k k个功能段的流水线中，第个功能段的流水线中，第i-1i-1条指令要等条指令要等到第到第i+k-2i+k-2条指令进入流水线时才能形成条件码。条指令进入流水线时才能形成条件码。转移不成功，猜测正确，流水线的吞吐率和效率没有转移不成功，猜测正确，流水线的吞吐率和效率没有降低，降低，转移成功，猜测错误，要先作废流水线中已经执行的转移成功，猜测错误，要先作废流水线中已经执行的i+1i+1、i+2i+2、i+k-2i+k-2指令；然后再从分支点开始指令；然后再从分支点开始执行第执行第P P、p+1p+1、指令。指令。条件分支指令

29、在流水线中的执行过程条件分支指令在流水线中的执行过程当分支的执行方向猜测错误时，可能造成程序执行结当分支的执行方向猜测错误时，可能造成程序执行结果发生错误。果发生错误。例如，若第例如，若第i+1条指令是：条指令是：(R1(R2)R1，寄寄存器存器R1中内容就被破坏，整个程序执行的结果是错中内容就被破坏，整个程序执行的结果是错误的。误的。目前的处理机有两种做法：目前的处理机有两种做法：一种方法是只进行指令译码和准备好运算所需要的操一种方法是只进行指令译码和准备好运算所需要的操作数，在转移条件没有形成之前不执行运算；作数，在转移条件没有形成之前不执行运算；另一种方法是一直执行到运算完成，但不送回运

30、算结另一种方法是一直执行到运算完成，但不送回运算结果。果。静态分支预测技术静态分支预测：静态分支预测：在程序执行过程中转移预测方向不能改变在程序执行过程中转移预测方向不能改变动态分支预测：动态分支预测：在程序执行过程中能够改变转移预测方向在程序执行过程中能够改变转移预测方向本节讲静态预测技术本节讲静态预测技术1.1.软件软件“猜测法猜测法”目标：目标：通过编译器尽量降低转移成功的概率。通过编译器尽量降低转移成功的概率。例如：对于循环程序，普通编译器生成的目标代码，例如：对于循环程序，普通编译器生成的目标代码，转移成功的概率很高，不成功的只有一次。这种编转移成功的概率很高，不成功的只有一次。这种

31、编译结果对流水线极为不利。译结果对流水线极为不利。软件软件“猜测法猜测法”：通过编译器降低转移成功的概率通过编译器降低转移成功的概率2.2.硬件硬件“猜测法猜测法”方法：方法：通过改变硬件结构来降低转移指令对流水线的通过改变硬件结构来降低转移指令对流水线的影响影响在先行指令缓冲栈的人口处设置一个简单的指令分析在先行指令缓冲栈的人口处设置一个简单的指令分析器，当检测到转移指令时，就把转移目标地址器，当检测到转移指令时，就把转移目标地址L L送入送入先行程序计数器先行程序计数器PC1中，同时保留当前中，同时保留当前PC1中的内容中的内容到另一寄存器中。到另一寄存器中。转移成功，猜测正确。对转移指令

32、对流水线不造成影转移成功，猜测正确。对转移指令对流水线不造成影响。响。转移不成功，用保存下来的地址恢复转移不成功，用保存下来的地址恢复PC1和和PC。软硬件共同配合，都往同一个方向去猜测。软硬件共同配合，都往同一个方向去猜测。3.3.两个先行指令缓冲栈两个先行指令缓冲栈向前条件转移，转移成功与不成功各向前条件转移，转移成功与不成功各50%50%在先行指令缓冲栈中在先行指令缓冲栈中增加一个先行目标缓冲栈增加一个先行目标缓冲栈按照转移成功的方向预取指令到先行目标缓冲栈中。按照转移成功的方向预取指令到先行目标缓冲栈中。先行指令缓冲栈仍然按照转移不成功的方向继续预取指先行指令缓冲栈仍然按照转移不成功的

33、方向继续预取指令。令。如果转移不成功，则继续分析原来先行指令缓冲栈中指如果转移不成功，则继续分析原来先行指令缓冲栈中指令。令。如果转移成功，则分析新增设的先行目标缓冲栈中的指如果转移成功，则分析新增设的先行目标缓冲栈中的指令。令。提前形成条件码必要性：对提高流水线的性能非常有效必要性：对提高流水线的性能非常有效可能性：可能性：可在运算开始或中间产生条件码可在运算开始或中间产生条件码对于乘除法，两个源操作数的符号相同结果为正，符号对于乘除法，两个源操作数的符号相同结果为正，符号相反结果为负相反结果为负对于乘法，有一个操作数为对于乘法，有一个操作数为0，则乘积为，则乘积为0被除数为被除数为0，商为

34、，商为0；除数为除数为0，除法结果溢出，除法结果溢出同号加或异号减，结果符号与第一操作数相同同号加或异号减，结果符号与第一操作数相同异号加或同号减，结果的符号与绝对值大的操作数相同异号加或同号减，结果的符号与绝对值大的操作数相同溢出及是否为溢出及是否为0可以通过一个比较器提前产生可以通过一个比较器提前产生精确断点与不精确断点对于输入输出设备的中断服务，实际上不需要有精确对于输入输出设备的中断服务，实际上不需要有精确断点。断点。比较简单的处理方法是：让已经进入流水线的所有指比较简单的处理方法是：让已经进入流水线的所有指令都执行完成，断点就是最后进入流水线的那条指令都执行完成，断点就是最后进入流水

35、线的那条指令的地址。令的地址。对于程序性错误和机器故障等引起的中断，它们出现对于程序性错误和机器故障等引起的中断，它们出现的概率很低，处理原则：的概率很低，处理原则：不在于缩短时间，关键是不在于缩短时间，关键是要正确保存现场和正确恢复断点。要正确保存现场和正确恢复断点。不精确断点不精确断点(Imprecise)，流水线可以不断流流水线可以不断流需要的硬件比较少，控制逻辑比较简单需要的硬件比较少，控制逻辑比较简单中断响应时间加长中断响应时间加长 采用不精确断点法可能会发生如下两个问题：采用不精确断点法可能会发生如下两个问题：(1)(1)程序的调试困难程序的调试困难早期的流水线处理机，多采用不精确

36、断点法早期的流水线处理机，多采用不精确断点法近期的流水线处理机一般都采用精确断点法近期的流水线处理机一般都采用精确断点法(2)(2)程序执行的结果可能出错，例如：程序执行的结果可能出错，例如：i i：FADD R1,R2 FADD R1,R2 ；(R1)(R1)(R2)R1(R2)R1 i+1 i+1：FMUL R3,R1 FMUL R3,R1 ；(R3)(R3)(R1)R3(R1)R3当第当第i i条指令执行到条指令执行到S6段时发现浮点加法结果溢出，段时发现浮点加法结果溢出，于是发出中断服务申请。由于采用不精确断点法，于是发出中断服务申请。由于采用不精确断点法，已经进入流水线的第已经进入流

37、水线的第i+1i+1条指令将执行完成；因为第条指令将执行完成；因为第i+1i+1条指令使用了不正确的条指令使用了不正确的R1R1，所以浮点乘法的执行，所以浮点乘法的执行结果是不正确的。结果是不正确的。采用精确断采用精确断(Precise)(Precise)点法，要设置一定数量的后援点法，要设置一定数量的后援寄存器寄存器，把整个流水线中所有指令的执行结果和现，把整个流水线中所有指令的执行结果和现场都保存下来。场都保存下来。动态调度技术动态调度技术实现方法：实现方法：由硬件动态调整指令执行顺序，以减少数据相关造由硬件动态调整指令执行顺序，以减少数据相关造成的影响。成的影响。主要优点：主要优点：能够

38、处理在编译时无法确定的相关，并简化编译器设能够处理在编译时无法确定的相关，并简化编译器设计计在其他流水线机器上编译的目标代码也能够高效运行在其他流水线机器上编译的目标代码也能够高效运行用静态调度法生成的代码也能在动态调度法的机器中用静态调度法生成的代码也能在动态调度法的机器中运行运行主要缺点：主要缺点：指令级并行度低，因为只能在比较小的范指令级并行度低，因为只能在比较小的范围内寻找并行性围内寻找并行性顺序流动与乱序流动1.1.顺序流动方式：顺序流动方式：任务按顺序流入流水线任务按顺序流入流水线,也按顺序也按顺序流出流水线流出流水线把如下一段程序输入到这条流水线中：把如下一段程序输入到这条流水线

39、中：k：R0（R1）k+1：k+2：R2（R0）（）（R3）k+3：k+4：k+5：指令指令k+2k+2无法继续执行，要在功能段无法继续执行，要在功能段S2中等待。中等待。后续的指令后续的指令k+4k+4、k+5k+5、等也不能进入流水线。等也不能进入流水线。功能段功能段S3、S4、S5将逐渐空闲。将逐渐空闲。缺点：缺点：吞吐率和效率降低吞吐率和效率降低优点：优点：流水线的控制逻辑比较简单流水线的控制逻辑比较简单流水线流水线“断流断流”，有些功能段，有些功能段“空闲空闲”2.2.乱序乱序(Out of order)流动方式：流动方式：指令流出流水线指令流出流水线的顺序与流入流水线的顺序不同。的

40、顺序与流入流水线的顺序不同。又称为又称为错序流动错序流动方式、无序流动方式、异步流动方式等。方式、无序流动方式、异步流动方式等。乱序流动中的数据相关在乱序流动方式中，可能发生三种数据相关在乱序流动方式中，可能发生三种数据相关 写写相关写写相关 k k：LOAD F1,A ;F1LOAD F1,A ;F1（A A）写读相关写读相关 k+1k+1：FADD F2,F1;F2FADD F2,F1;F2（F2F2）+（F1F1）k+2k+2：FMUL F1,F3;F1FMUL F1,F3;F1（F1F1）（F3F3）k+3k+3：STORE F1,B ;BSTORE F1,B ;B（F1F1）读写相关

41、读写相关(1)写读相关：写读相关：指令指令k与指令与指令k+1之间关于之间关于F1的相关，的相关，又称为数据相关、先写后读相关、流相关、又称为数据相关、先写后读相关、流相关、WR相关、相关、RAW相关等。相关等。(2)读写相关：读写相关：指令指令k+1与指令与指令k+2之间关于之间关于F1的的相关，变量名相关、先读后写相关、反相关、相关，变量名相关、先读后写相关、反相关、RW相关、相关、WAR相关等。相关等。(3)写写相关：写写相关：指令指令k与指令与指令k+2左边的左边的F1之间的相之间的相关关系称为：输出相关、写写相关、关关系称为：输出相关、写写相关、WW相关、相关、WAW相关或写后再写相

42、关等。相关或写后再写相关等。有时把有时把相关相关称为称为“冒险冒险”(hazard)(hazard)、“竟争竟争”(competition)(competition)等。等。在程序执行过程中，只有避免相关，执行结果才是正在程序执行过程中，只有避免相关，执行结果才是正确的。确的。三种数据相关可以用下列关系式来表示：三种数据相关可以用下列关系式来表示：对于写读相关对于写读相关 D(i)S(j)对于读写相关对于读写相关 S(i)D(j)对于写写相关对于写写相关 D(i)D(j)数据重定向方法1.1.三种数据相关的重定向三种数据相关的重定向 重定向之前，重定向之前，j j只能在只能在i i之后执行。之

43、后执行。重定向之后，可以做到：重定向之后，可以做到：(1)(1)写读相关，写读相关，j j与与i i可以同时执行可以同时执行 即专用数据通路即专用数据通路(2)(2)写写相关，写写相关，先后顺序无关先后顺序无关(3)(3)读写相关，读写相关，先后顺序无关先后顺序无关 后两种情况又称为后两种情况又称为“变量换名技术变量换名技术”2.2.变量换名技术变量换名技术用来自动消除用来自动消除读写数据相关读写数据相关和和写写数据相关写写数据相关规则：规则：一个变量只允许定值一次一个变量只允许定值一次在三种数据相关中，实际上只有写读数据相关必须依在三种数据相关中，实际上只有写读数据相关必须依靠硬件、或采用软

44、硬件结合的方法来解决靠硬件、或采用软硬件结合的方法来解决 解决方法：解决方法：推后处理推后处理或或专用数据通路专用数据通路在上面的数据重定向图中，把在上面的数据重定向图中，把B换成了换成了B，并在以后，并在以后的都引用的都引用B读写数据相关和写写数据相关就不存在读写数据相关和写写数据相关就不存在了。了。三种主流处理机三种主流处理机(指令级高度并行的超级处理机指令级高度并行的超级处理机)：超标量处理机超标量处理机 超流水线处理机超流水线处理机 超标量超流水线处理机超标量超流水线处理机基本结构普通标量流水线处理机：普通标量流水线处理机：一条指令流水线一条指令流水线，一个多功能操作部件，一个多功能操

45、作部件，每个时钟周期平均执行指令的条数小于每个时钟周期平均执行指令的条数小于1。多操作部件标量处理机：多操作部件标量处理机：一条指令流水线一条指令流水线，多个独立的操作部件，多个独立的操作部件，指令级并行度小于指令级并行度小于1。超标量处理机典型结构：超标量处理机典型结构：多条并行工作的指令流水线多条并行工作的指令流水线，多个独立的操作部件，多个独立的操作部件，指令级并行度（指令级并行度（ILP）大于）大于1。MotorolaMotorola公司的公司的MC88110MC88110有有1010个操作部件个操作部件两个寄存器堆：两个寄存器堆：整数部件通用寄存器堆，整数部件通用寄存器堆，3232个

46、个3232位寄存器位寄存器浮点部件扩展寄存器堆，浮点部件扩展寄存器堆，3232个个8080位寄存器位寄存器缓冲深度为缓冲深度为4 4的先行读数栈的先行读数栈缓冲深度为缓冲深度为3 3的后行写数栈的后行写数栈两个独立的高速两个独立的高速CacheCache中，各为中，各为8KB8KB，采用两路组相联，采用两路组相联方式方式转移目标指令转移目标指令CacheCache，用于存放另一条分支上的指令，用于存放另一条分支上的指令单发射与多发射1.1.单发射处理机单发射处理机(普通流水线标量处理机普通流水线标量处理机)：每个周期只取一条指令、只译码一条指令，只执行一每个周期只取一条指令、只译码一条指令，只

47、执行一条指令，只写回一个运算结果。条指令，只写回一个运算结果。取指令部件和指令译码部件各设置一套；取指令部件和指令译码部件各设置一套；只设置一个多功能操作部件或设置多个独立的操作部只设置一个多功能操作部件或设置多个独立的操作部件；件；操作部件中可以采用流水线结构，也可以不采用流水操作部件中可以采用流水线结构，也可以不采用流水线结构。线结构。目标是每个时钟周期平均执行一条指令，目标是每个时钟周期平均执行一条指令，ILPILP的期望的期望值为值为1 1。2.2.多发射处理机：多发射处理机：每个周期同时取多条指令、同时译码多条指令，同时每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时

48、写回多个运算结果。执行多条指令，同时写回多个运算结果。多个取指令部件，多个指令译码部件和多个写结果部多个取指令部件，多个指令译码部件和多个写结果部件。件。设置多个指令执行部件，有些指令执行部件采用流水设置多个指令执行部件，有些指令执行部件采用流水线结构。线结构。目标是每个时钟周期平均执行多条指令，目标是每个时钟周期平均执行多条指令，ILPILP的期望的期望值大于值大于1 1。3.3.超标量处理机超标量处理机(一个时钟周期内同时发射多条指令一个时钟周期内同时发射多条指令的处理机的处理机)：有两条或两条以上能同时工作的指令流水线。有两条或两条以上能同时工作的指令流水线。先行指令窗口先行指令窗口：能

49、够从指令：能够从指令CacheCache中预取多条指令，中预取多条指令，能够对窗口内的指令进行数据相关性分析和功能部能够对窗口内的指令进行数据相关性分析和功能部件冲突检测，提高功能部件利用率，一般取件冲突检测，提高功能部件利用率，一般取2-82-8条指条指令。令。由于程序中指令并行性的开发有限，所以度由于程序中指令并行性的开发有限，所以度m比较比较低，理论上最佳低，理论上最佳m=3。超标量处理机的指令级并行度：超标量处理机的指令级并行度：1ILPm。超标量处理机非常适合于求解像稀疏向量或矩阵这超标量处理机非常适合于求解像稀疏向量或矩阵这类标量计算问题。类标量计算问题。多流水线调度顺序发射顺序发

50、射(in-order issue)与乱序发射与乱序发射(out-order issue)：指令发射顺序是按照程序中指令指令发射顺序是按照程序中指令排列顺序进行的称为顺序发射排列顺序进行的称为顺序发射顺序完成顺序完成(in-order completion)与乱序完成与乱序完成(out-order completion)：指令完成顺序是按指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成照程序中指令排列顺序进行的称为顺序完成多流水线的调度主要有三种方法：多流水线的调度主要有三种方法：顺序发射顺序完成顺序发射顺序完成顺序发射乱序完成顺序发射乱序完成乱序发射乱序完成乱序发射乱序完成以如下以如下6