《计算机系统结构》电子教案(课).ppt

3.4 3.4 RISCRISC的基本流水线的基本流水线(P70)P70)下面是下面是RISC的指令流水线简化结构图（的指令流水线简化结构图（5段结构），每段段结构），每段1个时钟周期。个时钟周期。1计算机系统结构(1)(1)流水运行方式流水运行方式RISCRISC流水线流水线5 5段功能的初步定义（时钟周期图段功能的初步定义（时钟周期图CycleCycle）IFIFIDIDEXEXMemMemWBWBIFIFIDIDEXEXMemMemWBWB指令指令K K指令指令K+1K+1取指取指PC+4PC+4译码译码取数取数计算计算判断判断访存访存送送PCPC写回写回(2)(2)顺序运行方式顺序运行方式IFIFIDIDEXEXMemMemWBWBIFIFIDIDEXEXMemMemWBWB指令指令K K指令指令K+1K+1取指取指译码译码取数取数计算计算判断判断访存访存送送PCPC写回写回2计算机系统结构RISCRISC流水线流水线5 5段功能的初步定义段功能的初步定义3计算机系统结构 为了简单，先考虑顺序处理方式下的工作过程（即不考虑并行处理多条指为了简单，先考虑顺序处理方式下的工作过程（即不考虑并行处理多条指令）：令）：(1)IF 取指周期（后来称取指周期（后来称IM）(2)ID 指令译码指令译码/读寄存器周期读寄存器周期(3)EX 执行执行/地址计算周期地址计算周期 做做4种操作之一：存储器地址计算、寄存器种操作之一：存储器地址计算、寄存器/寄存器寄存器ALU运算、寄存器运算、寄存器/立立即数即数ALU运算、分支地址计算与条件判断。运算、分支地址计算与条件判断。(4)MEM 存储器访问存储器访问/分支完成周期（分支完成周期（ALU指令不需要）（后来称指令不需要）（后来称DM）做做2种操作之一：存储器访问、根据分支条件对种操作之一：存储器访问、根据分支条件对PC赋值。赋值。(5)WB 写回寄存器周期（分支指令不需要）写回寄存器周期（分支指令不需要）做做2种操作之一：种操作之一：ALU结果写寄存器、结果写寄存器、LOAD结果写寄存器结果写寄存器。总周期数总周期数=n CPI（ALU和分支指令的和分支指令的CPI=4，其它指令的其它指令的CPI=5）3.4.1 3.4.1 用顺序方式实现用顺序方式实现RISCRISC详解详解4计算机系统结构按流水方式运行需要解决的问题：按流水方式运行需要解决的问题：存储周期存储周期每个时钟周期都至少访问一次存储器，所以存储器件的每个时钟周期都至少访问一次存储器，所以存储器件的访问周期必须缩短为顺序方式的访问周期必须缩短为顺序方式的1/5（流水线必须配用高速存储系统）。（流水线必须配用高速存储系统）。冲突冲突前面指令在前面指令在MEM修改修改PC与后面指令在与后面指令在IF做做PC+4发生发生PC冲冲突；突；前面指令在前面指令在MEM访存与后面指令在访存与后面指令在IF取指发生存储器冲突；取指发生存储器冲突；前面前面指令在指令在WB写寄存器与后面指令在写寄存器与后面指令在ID读寄存器发生寄存器冲突。读寄存器发生寄存器冲突。（下页图）（下页图）对策对策用多路器选择用多路器选择PC+4送送PC，还是还是ALUout送送PC；IF改成访改成访问指令存储器问指令存储器IM，MEM改成访问数据存储器改成访问数据存储器DM，以避免存储器冲突；或者以避免存储器冲突；或者虽共用一个存储器，但是分别连到指令虽共用一个存储器，但是分别连到指令Cache、数据数据Cache；寄存器冲突留寄存器冲突留待下文解决。待下文解决。寄存器文件寄存器文件每条指令启动后就被分配一组暂存器，称为每条指令启动后就被分配一组暂存器，称为“寄存器文寄存器文件件”，用以保存自己的临时数据，如，用以保存自己的临时数据，如NPC、IR等，它们伴随指令逐段推进，等，它们伴随指令逐段推进，直至指令结束。在没有操作的段，寄存器文件被直接拷贝到下一段。直至指令结束。在没有操作的段，寄存器文件被直接拷贝到下一段。（P119）总周期数总周期数=n+m 1+stall总数（无相关、无冲突情况下）总数（无相关、无冲突情况下）3.5 3.5 基本的基本的MIPSMIPS流水线（流水线（P87P87）5计算机系统结构(1)3(1)3种冲突种冲突流水方式运行带来的结构冲突流水方式运行带来的结构冲突IFIFIDIDEXEXMemMemWBWBIFIFIDIDEXEXMemMemWBWB指令指令K K指令指令K+1K+1译码译码取数取数访存访存送送PCPC写回写回(2)(2)存储器哈佛结构、分离存储器哈佛结构、分离CacheCache结构结构CPUCPU指令指令K+3K+3指令指令K KIFIFIDIDEXEXMemMemWBWB指令指令K+2K+2IFIFIDIDEXEXMemMemWBWB指令指令K+3K+3取指取指PC+4PC+4指令存储器指令存储器数据存储器数据存储器CPUCPU指令指令CacheCache数据数据CacheCache内存内存6计算机系统结构3.5.1 MIPS3.5.1 MIPS的一种简单实现的一种简单实现7计算机系统结构3.4.2 相关与冲突相关与冲突(P72)相关相关dependence：一条指令依赖另一条指令的结果：一条指令依赖另一条指令的结果。冲突冲突hazard：由于相关或其它原因，一条指令暂时停下来等待另一条指：由于相关或其它原因，一条指令暂时停下来等待另一条指令执行，不然就会产生错误的结果（与程序员预期的不一致）。令执行，不然就会产生错误的结果（与程序员预期的不一致）。相关的分类相关的分类1.数据相关：前面指令的结果作为后面指令的操作数（真数据相关）数据相关：前面指令的结果作为后面指令的操作数（真数据相关）2.名相关：两条指令使用了同一个寄存器或存储单元，并非要传送数据名相关：两条指令使用了同一个寄存器或存储单元，并非要传送数据3.控制相关：分支指令等改变控制相关：分支指令等改变PC值的情况值的情况 反相关反相关 名相关名相关 输出相关输出相关 冲突的分类冲突的分类1.结构冲突：即资源争用结构冲突：即资源争用 写后读：写后读：RAW2.数据冲突：由数据相关、或者名相关造成数据冲突：由数据相关、或者名相关造成 写后写：写后写：WAW3.控制冲突：由控制相关造成控制冲突：由控制相关造成 读后写：读后写：WAR实例：实例：P73P83；多种相关、冲突演示程序多种相关、冲突演示程序Lesson-5.s8计算机系统结构3种相关与种相关与3种冲突的关系种冲突的关系?数据相关数据相关名相关名相关控制相关控制相关3 3种相关种相关结构冲突结构冲突数据冲突数据冲突控制冲突控制冲突3 3种冲突种冲突原因原因结果结果9计算机系统结构冲突的通用处理方法冲突的通用处理方法暂停暂停 冲突的通用处理方法：为了不出现错误结果，相关检测硬件会自动插入冲突的通用处理方法：为了不出现错误结果，相关检测硬件会自动插入所需个数的暂停周期所需个数的暂停周期stall（又称为又称为“流水线气泡流水线气泡”），图），图3.21和图和图3.22是是等效的表示法，后者比较紧凑；等效的表示法，后者比较紧凑；MIPS流水线的暂停：在流水线的暂停：在ID段之后分支，在段之后分支，在MEM段之前汇合。段之前汇合。如果一条指令在非分支的如果一条指令在非分支的IF、ID、MEM、WB段暂停，它后面的指令只段暂停，它后面的指令只能顺序流动；如果一条指令在任一分支内暂停，它后面的其它种类指令能顺序流动；如果一条指令在任一分支内暂停，它后面的其它种类指令可以乱序流动（绕过它先流向出口）。可以乱序流动（绕过它先流向出口）。MIPS暂停演示程序暂停演示程序Lesson-5.s：dmul r1,r2,r3 dmul r4,r5,r1 sub.d f1,f2,f310计算机系统结构1.结构冲突结构冲突特异处理方法（特异处理方法（P75）“设备重复设备重复”方法，又称方法，又称“完全流水化功能单元完全流水化功能单元”方法：即为不同方法：即为不同指令的同一操作分别设置独立的设备。比如指令的同一操作分别设置独立的设备。比如 IF 段访问指令存储器，段访问指令存储器，MEM 段访问数据存储器（见课件段访问数据存储器（见课件P108）。）。这种方法需要显著增加成本，对经常发生的冲突类型值得采用。而这种方法需要显著增加成本，对经常发生的冲突类型值得采用。而不常发生的结构相关，因为导致的程序平均执行时间增加并不多，可以不常发生的结构相关，因为导致的程序平均执行时间增加并不多，可以放任不管放任不管，见下页例子见下页例子。11计算机系统结构例例3.5（不用（不用“完全流水化功能单元完全流水化功能单元”的例子，的例子，2版教材）版教材）已知已知DLX处理机（处理机（MIPS的前身）中其它指令的的前身）中其它指令的 CPI=1，浮点乘法浮点乘法指令的指令的 CPI=7，因为非流水的浮点乘法部件用时因为非流水的浮点乘法部件用时 7 拍。如果下一条指令拍。如果下一条指令也要使用浮点乘法部件，则必须比上一条指令推迟也要使用浮点乘法部件，则必须比上一条指令推迟7 拍启动，除非增加一拍启动，除非增加一个浮点乘法部件。在个浮点乘法部件。在mdljdp2基准测试程序中，浮点乘法指令出现的概率基准测试程序中，浮点乘法指令出现的概率为为14%，试分析不采用，试分析不采用“完全流水化功能单元完全流水化功能单元”方法带来的方法带来的 CPI 增量。增量。分析：分析：不采用不采用“完全流水化功能单元完全流水化功能单元”方法，即系统中只有一个浮点乘法方法，即系统中只有一个浮点乘法部件，那么当浮点乘法指令的下一条指令不是浮点乘法指令时部件，那么当浮点乘法指令的下一条指令不是浮点乘法指令时 CPI 仍为仍为 1（应为（应为2，林老师注），当下一条指令是浮点乘法指令时，林老师注），当下一条指令是浮点乘法指令时 CPI 增大到增大到 7。最坏情况是这最坏情况是这14%的浮点乘法指令连续出现，那么整个程序的平均的浮点乘法指令连续出现，那么整个程序的平均 CPI 将增加将增加 14%6=0.84拍。拍。该教材说当浮点乘法指令服从均匀分布时，采用该教材说当浮点乘法指令服从均匀分布时，采用“完全流水化功能完全流水化功能单元单元”获得的好处可能很少，原因是实际获得的好处可能很少，原因是实际 CPI 的增量比的增量比0.84小得多（见小得多（见下页例下页例3.5 的进一步推导的进一步推导”）。）。12计算机系统结构例例3.5 的进一步推导的进一步推导记：记：浮点乘法指令的出现概率，浮点乘法指令的出现概率，=14%；由于浮点乘法由于浮点乘法指令指令出现导致的出现导致的平均平均 CPI 增量增量（节拍数）；（节拍数）；n n 指令总数。指令总数。分析：分析：1 1条单独出现的概率为条单独出现的概率为1 1（1-1-），），对应的对应的=0=0；2 2条连续出现的条连续出现的概率为概率为2 2（1-1-），），对应的对应的=4=4；k k条连续出现的概率为条连续出现的概率为k k（1-1-），），对应的对应的=4=4（k-1k-1）；）；n+1n+1条连续出现的概率为条连续出现的概率为0 0。的期望值：的期望值：/=2 2（1-1-）4 41+1+3 3（1-1-）4 422+nn（1-1-）4 4（n-1n-1）=4=4（1-1-）112 2+2+23 3+（n-1n-1）nn=442 2（1-1-n-1n-1）/（1-1-）-（n-1n-1）n+1n+1 当当n时，时，/4 42 2/（1-1-）0.090.09拍拍13计算机系统结构2.数据冲突数据冲突特异处理方法（特异处理方法（P76）(1)实例见图实例见图3.23(2)相关指令彼此间隔大于一定距离就不会出错（相关指令彼此间隔大于一定距离就不会出错（P77第第1段，段，XOR）(3)把时钟分成前、后半段的方法可以解决寄存器相关（把时钟分成前、后半段的方法可以解决寄存器相关（P77第第1段，段，OR）(4)定向技术（定向技术（forwarding）可以达到提前可以达到提前1.5拍写、推迟拍写、推迟0.5拍读的效果，拍读的效果，消除消除2拍以内的相关出错（实际有效范围因指令而异，见下图）拍以内的相关出错（实际有效范围因指令而异，见下图）(5)通过编译软件的指令调度处理，可以达到通过编译软件的指令调度处理，可以达到(2)的目的，而不用增加的目的，而不用增加“空操作空操作”指令或者硬件指令或者硬件“气泡气泡”（P79第第5行实例分析）。行实例分析）。前半拍完成写寄存器前半拍完成写寄存器后半拍完成读寄存器后半拍完成读寄存器ALUALU出口出口定向路径定向路径定向路径定向路径ALUALU入口入口14计算机系统结构定向路径（相关专用通路定向路径（相关专用通路）寄存器文件寄存器文件寄存器文件寄存器文件寄存器文件寄存器文件寄存器文件寄存器文件通过定向路径复制寄存器文件通过定向路径复制寄存器文件15计算机系统结构采用定向技术后消除停顿的情形采用定向技术后消除停顿的情形16计算机系统结构采用定向技术后减少停顿的情形采用定向技术后减少停顿的情形17计算机系统结构数据冲突的分类（数据冲突的分类（P76）(1)写写-读冲突，当后一条指令读冲突，当后一条指令ID先于前一条指令先于前一条指令WB时发生，最常见；时发生，最常见；(2)写写-写冲突，当后一条指令写冲突，当后一条指令WB先于前一条指令先于前一条指令WB时发生，乱序流动时发生，乱序流动下会出现；下会出现；(3)读读-写冲突，当后一条指令写冲突，当后一条指令WB先于前一条指令先于前一条指令ID时发生。时发生。RISC机器机器不会出现，因为流水线在不会出现，因为流水线在ID之前没有分支。之前没有分支。数据冲突的自动检测与气泡的自动生成：数据冲突的自动检测与气泡的自动生成：通过通过“流水线互锁流水线互锁”（pipeline interlock）机构来实现，阅读机构来实现，阅读P79第第1段，段，P89第第2段，详见段，详见2版版P96；可以检测到的各种数据冲突列表，见可以检测到的各种数据冲突列表，见2版版P96表表3.3。18计算机系统结构3.控制冲突控制冲突特异处理方法（特异处理方法（P79）重要性（重要性（P80）：）：每个条件分支指令带来每个条件分支指令带来3个暂停周期，个暂停周期，30%时减速时减速一半。一半。方法：方法：(1)“冻结冻结”（freeze）或或“排空排空”（flush）：）：消极暂停消极暂停(2)提早完成分支操作，把提早完成分支操作，把3个暂停周期缩短为个暂停周期缩短为1个。需要做两件事：个。需要做两件事：尽早判断是否成功（将测试操作提早到尽早判断是否成功（将测试操作提早到ID段）；段）；尽早算出目标地址（将地址计算提早到尽早算出目标地址（将地址计算提早到ID段）。段）。改进前改进前改进后改进后19计算机系统结构3.控制冲突控制冲突特异处理方法（特异处理方法（P79）续续(3)通过预测提前启动分支后面的指令通过预测提前启动分支后面的指令“预测分支失败预测分支失败”：猜失败，提前取指令：猜失败，提前取指令i+1；“预测分支成功预测分支成功”：猜成功，需要计算目标地址，而：猜成功，需要计算目标地址，而RISC流水线的流水线的地址计算与判跳操作是同时完成的，故此举无益；地址计算与判跳操作是同时完成的，故此举无益；(4)“延迟分支延迟分支”（delayed branch）：）：调若干指令在若干调若干指令在若干“延迟槽延迟槽”中中执行，执行，调分支前的指令（最佳方案）；调分支前的指令（最佳方案）；调跳转目标处指令（猜成功，猜错需作废）；调跳转目标处指令（猜成功，猜错需作废）；调后续指令（猜失败，猜错需作废）。调后续指令（猜失败，猜错需作废）。(5)“取消取消”（canceling）或或“作废作废”（nullifying）分支：对分支：对“分支延迟分支延迟槽槽”的处理技术。的处理技术。20计算机系统结构改进后的改进后的MIPSMIPS流水线（流水线（P90P90）21计算机系统结构改进流水线上使用定向技术的延迟时间改进流水线上使用定向技术的延迟时间22计算机系统结构各种处理控制冲突方法的性能公式（各种处理控制冲突方法的性能公式（2版版P104）(1)控制冲突（即分支）导致的最大加速比控制冲突（即分支）导致的最大加速比Smax下降下降 在定义流水线在定义流水线“效率效率”指标时推导过一个公式：指标时推导过一个公式：Smax=Em，意思是意思是说当效率达到说当效率达到100%时，流水方式（每个时，流水方式（每个t完成一个任务完成一个任务）吞吐率吞吐率为顺为顺序方式（每序方式（每m m个个tt完成完成一个任务一个任务）的的m倍。此处把倍。此处把m改写为改写为D。考虑分支损失的流水线最大加速比公式：考虑分支损失的流水线最大加速比公式：Smax=Em/(1+f P分支分支)，其中，其中f是分支指令的出现概率，是分支指令的出现概率，P分支分支是平均分支损失（暂停周期数）。是平均分支损失（暂停周期数）。其实这个公式可以用来计算任何一种冲突对应的最大加速比其实这个公式可以用来计算任何一种冲突对应的最大加速比Smax。对对MIPS来说，无任何冲突情况下来说，无任何冲突情况下“效率效率”E=100%。(2)采用每种处理方法减少分支损失的效果采用每种处理方法减少分支损失的效果 假定没有分支损失情况下，理想假定没有分支损失情况下，理想CPI=1。可以算出存在分支损失情况下，不处理或单一处理方法对应的平均可以算出存在分支损失情况下，不处理或单一处理方法对应的平均分支损失值、延长的分支损失值、延长的CPI值。值。23计算机系统结构各种冲突处理方法小结（同学们自己做）各种冲突处理方法小结（同学们自己做）结构冲突：结构冲突：数据冲突：数据冲突：(1)(1)(2)(2)(3)(3)控制冲突：控制冲突：(1)(1)(2)(2)(3)(3)作业作业3.113.11题修改：题修改：开头添加：开头添加：在图在图3.333.33所示所示MIPSMIPS流水线上流水线上24计算机系统结构实验实验2MIPS流水线部件与指令周期流水线部件与指令周期实验要求：实验要求：在人工完成习题在人工完成习题3.113.11之后，在之后，在WinMIPS64WinMIPS64模拟器上运行对应的程序，分模拟器上运行对应的程序，分别按别按(1)(2)(3)(1)(2)(3)小问的条件设置模拟器的运行模式，记录相应的时钟周期数。小问的条件设置模拟器的运行模式，记录相应的时钟周期数。实验报告：实验报告：(1)(1)程序清单；程序清单；(2)(2)程序时间对比程序时间对比(3)(3)人工计算值与实测值的差异原因分析，如果有差异的话；人工计算值与实测值的差异原因分析，如果有差异的话；(4)(4)至少至少1 1段自己认为有价值的段自己认为有价值的“时钟周期图时钟周期图”片段抄录或者打印，加注释。片段抄录或者打印，加注释。25计算机系统结构各次作业应交的内容各次作业应交的内容作业作业5 5（第（第5 5次课）次课）3.11(3.11(改改)，实验，实验2 226计算机系统结构