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

计算机系统结构,1,3.4 RISC的基本流水线(P70),下面是RISC的指令流水线简化结构图（5段结构），每段1个时钟周期。,计算机系统结构,2,(1)流水运行方式,RISC流水线5段功能的初步定义（时钟周期图Cycle）,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,指令K,指令K+1,取指PC+4,译码取数,计算判断,访存送PC,写回,(2)顺序运行方式,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,指令K,指令K+1,取指,译码取数,计算判断,访存送PC,写回,计算机系统结构,3,RISC流水线5段功能的初步定义,计算机系统结构,4,为了简单，先考虑顺序处理方式下的工作过程（即不考虑并行处理多条指令）：(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 用顺序方式实现RISC详解,计算机系统结构,5,按流水方式运行需要解决的问题：存储周期每个时钟周期都至少访问一次存储器，所以存储器件的访问周期必须缩短为顺序方式的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 基本的MIPS流水线（P87）,计算机系统结构,6,(1)3种冲突,流水方式运行带来的结构冲突,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,指令K,指令K+1,译码取数,访存送PC,写回,(2)存储器哈佛结构、分离Cache结构,CPU,指令K+3,指令K,IF,ID,EX,Mem,WB,指令K+2,IF,ID,EX,Mem,WB,指令K+3,取指PC+4,指令存储器,数据存储器,CPU,指令Cache,数据Cache,内存,计算机系统结构,7,3.5.1 MIPS的一种简单实现,计算机系统结构,8,3.4.2 相关与冲突(P72),相关dependence：一条指令依赖另一条指令的结果。冲突hazard：由于相关或其它原因，一条指令暂时停下来等待另一条指令执行，不然就会产生错误的结果（与程序员预期的不一致）。相关的分类1.数据相关：前面指令的结果作为后面指令的操作数（真数据相关）2.名相关：两条指令使用了同一个寄存器或存储单元，并非要传送数据3.控制相关：分支指令等改变PC值的情况 反相关 名相关 输出相关 冲突的分类1.结构冲突：即资源争用 写后读：RAW2.数据冲突：由数据相关、或者名相关造成 写后写：WAW3.控制冲突：由控制相关造成 读后写：WAR实例：P73P83；多种相关、冲突演示程序Lesson-5.s,计算机系统结构,9,3种相关与3种冲突的关系,?,数据相关,名相关,控制相关,3种相关,结构冲突,数据冲突,控制冲突,3种冲突,原因,结果,计算机系统结构,10,冲突的通用处理方法暂停,冲突的通用处理方法：为了不出现错误结果，相关检测硬件会自动插入所需个数的暂停周期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,f3,计算机系统结构,11,1.结构冲突特异处理方法（P75）,“设备重复”方法，又称“完全流水化功能单元”方法：即为不同指令的同一操作分别设置独立的设备。比如 IF 段访问指令存储器，MEM 段访问数据存储器（见课件P108）。这种方法需要显著增加成本，对经常发生的冲突类型值得采用。而不常发生的结构相关，因为导致的程序平均执行时间增加并不多，可以放任不管，见下页例子。,计算机系统结构,12,例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 的进一步推导”）。,计算机系统结构,13,例3.5 的进一步推导,记：浮点乘法指令的出现概率，=14%；由于浮点乘法指令出现导致的平均 CPI 增量（节拍数）；n 指令总数。分析：1条单独出现的概率为1（1-），对应的=0；2条连续出现的概率为2（1-），对应的=4；k条连续出现的概率为k（1-），对应的=4（k-1）；n+1条连续出现的概率为0。的期望值：/=2（1-）41+3（1-）42+n（1-）4（n-1）=4（1-）12+23+（n-1）n=42（1-n-1）/（1-）-（n-1）n+1当n时，/42/（1-）0.09拍,计算机系统结构,14,2.数据冲突特异处理方法（P76）,(1)实例见图3.23(2)相关指令彼此间隔大于一定距离就不会出错（P77第1段，XOR）(3)把时钟分成前、后半段的方法可以解决寄存器相关（P77第1段，OR）(4)定向技术（forwarding）可以达到提前1.5拍写、推迟0.5拍读的效果，消除2拍以内的相关出错（实际有效范围因指令而异，见下图）(5)通过编译软件的指令调度处理，可以达到(2)的目的，而不用增加“空操作”指令或者硬件“气泡”（P79第5行实例分析）。,前半拍完成写寄存器,后半拍完成读寄存器,ALU出口定向路径,定向路径ALU入口,计算机系统结构,15,定向路径（相关专用通路）,寄存器文件,寄存器文件,寄存器文件,寄存器文件,通过定向路径复制寄存器文件,计算机系统结构,16,采用定向技术后消除停顿的情形,计算机系统结构,17,采用定向技术后减少停顿的情形,计算机系统结构,18,数据冲突的分类（P76）,(1)写-读冲突，当后一条指令ID先于前一条指令WB时发生，最常见；(2)写-写冲突，当后一条指令WB先于前一条指令WB时发生，乱序流动下会出现；(3)读-写冲突，当后一条指令WB先于前一条指令ID时发生。RISC机器不会出现，因为流水线在ID之前没有分支。数据冲突的自动检测与气泡的自动生成：通过“流水线互锁”（pipeline interlock）机构来实现，阅读P79第1段，P89第2段，详见2版P96；可以检测到的各种数据冲突列表，见2版P96表3.3。,计算机系统结构,19,3.控制冲突特异处理方法（P79）,重要性（P80）：每个条件分支指令带来3个暂停周期，30%时减速一半。方法：(1)“冻结”（freeze）或“排空”（flush）：消极暂停(2)提早完成分支操作，把3个暂停周期缩短为1个。需要做两件事：尽早判断是否成功（将测试操作提早到ID段）；尽早算出目标地址（将地址计算提早到ID段）。改进前改进后,计算机系统结构,20,3.控制冲突特异处理方法（P79）续,(3)通过预测提前启动分支后面的指令“预测分支失败”：猜失败，提前取指令i+1；“预测分支成功”：猜成功，需要计算目标地址，而RISC流水线的地址计算与判跳操作是同时完成的，故此举无益；(4)“延迟分支”（delayed branch）：调若干指令在若干“延迟槽”中执行，调分支前的指令（最佳方案）；调跳转目标处指令（猜成功，猜错需作废）；调后续指令（猜失败，猜错需作废）。(5)“取消”（canceling）或“作废”（nullifying）分支：对“分支延迟槽”的处理技术。,计算机系统结构,21,改进后的MIPS流水线（P90）,计算机系统结构,22,改进流水线上使用定向技术的延迟时间,计算机系统结构,23,各种处理控制冲突方法的性能公式（2版P104）,(1)控制冲突（即分支）导致的最大加速比Smax下降 在定义流水线“效率”指标时推导过一个公式：Smax=Em，意思是说当效率达到100%时，流水方式（每个t完成一个任务）吞吐率为顺序方式（每m个t完成一个任务）的m倍。此处把m改写为D。考虑分支损失的流水线最大加速比公式：Smax=Em/(1+f P分支)，其中f是分支指令的出现概率，P分支是平均分支损失（暂停周期数）。其实这个公式可以用来计算任何一种冲突对应的最大加速比Smax。对MIPS来说，无任何冲突情况下“效率”E=100%。(2)采用每种处理方法减少分支损失的效果 假定没有分支损失情况下，理想CPI=1。可以算出存在分支损失情况下，不处理或单一处理方法对应的平均分支损失值、延长的CPI值。,计算机系统结构,24,各种冲突处理方法小结（同学们自己做）,结构冲突：数据冲突：(1)(2)(3)控制冲突：(1)(2)(3)作业3.11题修改：开头添加：在图3.33所示MIPS流水线上,计算机系统结构,25,实验2MIPS流水线部件与指令周期,实验要求：在人工完成习题3.11之后，在WinMIPS64模拟器上运行对应的程序，分别按(1)(2)(3)小问的条件设置模拟器的运行模式，记录相应的时钟周期数。实验报告：(1)程序清单；(2)程序时间对比(3)人工计算值与实测值的差异原因分析，如果有差异的话；(4)至少1段自己认为有价值的“时钟周期图”片段抄录或者打印，加注释。,计算机系统结构,26,各次作业应交的内容,作业5（第5次课）,3.11(改)，实验2,