计算机体系结构第三章-2.

3.4流水线的相关与冲突一、一个经典的5段流水线(RISC流水线)一条指令的执行过程分为5个周期：取指令周期（IF）、指令译码/读寄存器周期（ID）、执行/有效地址计算周期（EX）、存储器访问／分支完成周期（MEM）、写回周期（WB）。3.4流水线的相关与冲突三类指令对5级流水线的占用情况:ALU指令LOAD/STORE分支指令S1IF取指取指取指S2ID译码,读通用寄存器译码,读通用寄存器译码,读通用寄存器S3EX运算（R-R,R-立即数）计算有效地址计算转移目标地址,设置条件码S4MEM--访存(读或写)（store完成）若条件成立,将转移目标地址送PC（分支完成）S5WB结果写回通用寄存器（ALU完成）读出数据写入通用寄存器--3.4流水线的相关与冲突3.4流水线的相关与冲突流水设计中的一些问题及解决：IF(取指令)，MEM(读/写数据)，访存冲突。通用寄存器访存冲突---分半拍。专门的加法器：PCPC+4。5段流水线的两种描述方式第一种描述（类似于时空图）3.4流水线的相关与冲突第二种描述（按时间错开的数据通路序列）3.4流水线的相关与冲突二、相关相关是指两条指令之间存在某种依赖关系。如果两条指令相关，则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。主要是三种类型的相关:数据相关名相关控制相关3.4流水线的相关与冲突1、数据相关（真数据相关）对于两条指令i（在前）和j（在后），如果下述条件之一成立，则称指令j与指令i数据相关。指令j使用指令i产生的结果；指令j与指令k数据相关，而指令k又与指令i数据相关。数据相关具有传递性。数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者。3.4流水线的相关与冲突例如：下面这一段代码存在数据相关Loop：L.DF0，0(R1)//F0为数组元素ADD.DF4，F0，F2//加上F2中的值S.DF4，0(R1)//保存结果DADDIUR1，R1，－8//数组指针递减8个字节BNER1，R2，Loop//如果R1≠R2，则分支3.4流水线的相关与冲突当数据的流动是经过寄存器时，相关的检测比较直观和容易。当数据的流动是经过存储器时，检测比较复杂。•相同形式的地址其有效地址未必相同。•形式不同的地址其有效地址却可能相同。3.4流水线的相关与冲突2、名相关名：指令所访问的寄存器或存储器单元的名称。如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。3.4流水线的相关与冲突指令j（在后）与指令i（在前）之间的名相关有两种：（1）反相关：如果指令j写的名与指令i读的名相同，则称指令i和j发生了反相关。指令i读的名＝指令j写的名例如：DIV.DF2，F6，F4（先读）ADD.DF6，F0，F12（后写）（2）输出相关：如果指令j和指令i写相同的名，则称指令i和j发生了输出相关。指令i写的名＝指令j写的名3.4流水线的相关与冲突名相关小结：名相关的两条指令之间并没有数据的传送。但名相关的两条指令之间的执行顺序必须严格遵守。如果一条指令中的名改变了，并不影响另外一条指令的执行。针对名相关：可采用换名技术，消除名相关。3.4流水线的相关与冲突换名技术：通过改变指令中操作数的名来消除名相关。例如：考虑下述代码：DIV.DF2，F6，F4ADD.DF6，F0，F12SUB.DF8，F6，F14进行寄存器换名（F6换成S）后，变成：DIV.DF2，F6，F4ADD.DS，F0，F12SUB.DF8，S，F143.4流水线的相关与冲突反相关3、控制相关控制相关是指由分支指令引起的相关。典型的程序结构是“if-then”结构。3.4流水线的相关与冲突ifp1{S1；}；S；ifp2{S2；}；控制相关带来了以下两个限制：与一条分支指令控制相关的指令不能被移到该分支之前，否则这些指令就不受该分支控制了。如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。三、流水线冲突流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。流水线冲突有3种类型：结构冲突数据冲突控制冲突3.4流水线的相关与冲突（一）结构冲突指多条指令进入流水线后，在同一时间争用同一功能部件，从而发生冲突。例如：存储器访问冲突12345678指令LOADIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB指令i+4IFIDEXMEM访存冲突3.4流水线的相关与冲突3.4流水线的相关与冲突解决办法Ⅰ：暂停一拍（也称为流水线气泡，简称气泡）。123456789指令LOADIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3停顿IFIDEXMEMWB指令i+4IFIDEXMEM3.4流水线的相关与冲突时间（时钟周期）123456MRegALUMRegMRegALUMRegMRegALUMReg78load指令i+1指令i+2暂停MRegALUM指令i+3气泡气泡气泡气泡气泡3.4流水线的相关与冲突解决方法Ⅱ：设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。3.4流水线的相关与冲突说明：有时流水线设计者允许结构冲突的存在主要原因：减少硬件成本（二）数据冲突1、数据冲突指由于流水线中各指令重叠执行，使得原来对操作数的访问顺序发生变化，从而引起的一种数据冲突。例如：DADDR1，R2，R3（写R1）DSUBR4，R1，R5（读R1）123456DADDIFIDEXMEMWBDSUBIFIDEXMEMWB写R1读R13.4流水线的相关与冲突根据指令读访问和写访问的顺序，假设两条指令i和j，且i在j之前进入流水线，可能发生的数据冲突有3种类型：（1）写后读冲突（RAW）i写入j读出如果在i写入之前，j先去读，j读出的内容是错误的。-对应真数据相关。3.4流水线的相关与冲突（2）写后写冲突（WAW）i写入j写入如果在i写入之前，j先写，最后写入的结果是的错误！-对应输出相关。写后写冲突发生的情况：流水线中不只一个段可以进行写操作。（介绍的5段流水线不会发生）当先前某条指令停顿时，允许其后续指令继续前进。3.4流水线的相关与冲突（3）读后写冲突（WAR）i读出j写入如果在i读之前，j先写。i读出的内容是错误的！-对应反相关。读后写冲突发生的情况：有些指令的写结果操作提前了，而且有些指令的读操作滞后了。指令被重新排序了。读后写冲突在前述5段流水线中不会发生。（读操作（在ID段）在写结果操作（在WB段）之前）3.4流水线的相关与冲突2、解决办法：-针对“写后读冲突”解决办法1：采用定向传送技术（旁路技术或相关专用通路技术）。3.4流水线的相关与冲突例：DADDR1，R2，R3DSUBR4，R1，R5XORR6，R1，R7ANDR8，R1，R9ORR10，R1，R11时间（时钟周期）123456IMRegALUDMRegIMRegALUDMRegIMRegALUDMIMRegALUDADDR1，R2，R3DSUBR4，R1，R5XORR6，R1，R7ANDR8，R1，R9IMRegORR10，R1，R11写R1读R1流水线的数据冲突举例产生数据ALU目标R旁路传送寄存器时间（时钟周期）123456IMRegALUDMRegIMRegALUDMRegIMRegALUDMIMRegALUDADDR1，R2，R3DSUBR4，R1，R5XORR6，R1，R7ANDR8，R1，R9IMRegORR10，R1，R113.4流水线的相关与冲突采用定向技术后的流水线数据通路定向技术关键思想：在某条指令产生计算结果之前，其他指令并不真正立即需要该计算结果，如果能够将该计算结果从其产生的地方直接送到其他指令需要它的地方，那么就可以避免停顿。推广一般的情况：结果数据不仅可以从某一功能部件的输出定向到其自身的输入，而且还可以定向到其他功能部件的输入。3.4流水线的相关与冲突时间（时钟周期）123456IMRegALUDMRegIMRegALUDMRegIMRegALUDMDSUBR1,R2,R3LDR5，0(R1)SDR5，12(R1)3.4流水线的相关与冲突DSUBR1，R2，R3LDR5，0（R1）SDR5，12（R1）但是，定向技术并不能解决所有RAW冲突。例如：LDR1，0（R2）DADDR4，R1，R5ANDR6，R1，R7XORR8，R1，R9时间（时钟周期）123456IMRegALUDMRegIMRegALUDMRegIMRegALUDMIMRegALULDR1，0(R2)DADDR4，R1，R5ANDR6，R1，R7XORR8，R1，R9无法将LD指令的结果定向到DADD指令解决方法2：增加流水线互锁硬件，插入“暂停”。作用：检测发现数据冲突，并使流水线停顿，直至冲突消失。时间（时钟周期）123456IMRegALUDMRegIMRegALUDMIMRegALUIMRegLDR1，0(R2)DADDR4，R1，R5ANDR6，R1，R7XORR8，R1，R9气泡气泡气泡解决方法3：指令调度技术（流水线调度）前提：在非按序流动方式（乱步流动）的流水线中。实现：通过编译器重新组织指令顺序来消除冲突。指允许输出结果的次序与输入指令的次序不同。例如：表达式A=B+C，采用典型的代码生成方法：LDRb，BIFIDEXMEMWBLDRc，CIFIDEXMEMWBDADDRa，Rb，RcIFIDstallEXMEMWBSDRa，AIFstallIDEXMEMWB3.4流水线的相关与冲突调度前的代码调度后的代码LDRb，BLDRc，CDADDRa，Rb，RcSDRa，ALDRe，ELDRf，FDSUBRd，Re，RfSDRd，DLDRb，BLDRc，CLDRe，EDADDRa，Rb，RcLDRf，FSDRa，ADSUBRd，Re，RfSDRd，D例：请为下列表达式生成没有暂停的指令序列:A＝B＋C；D＝E－F；假设载入延迟为1个时钟周期。（三）控制冲突1、控制冲突流水线遇到分支指令（条件转移）和其他会改变PC值的指令所引起的冲突。分支指令的简单处理：“冻结”，或“排空”流水线12345678分支指令IFIDEXMEMWB分支目标指令iIF停顿停顿IFIDEXMEM分支目标指令i+1停顿停顿停顿IFIDEX分支目标指令i+3停顿停顿停顿IFID更新PC值3.4流水线的相关与冲突检测到分支分支延迟:3个周期3.4流水线的相关与冲突转移指令对流水线的影响假设：在某一程序中，分支指令在程序中所占的比例为25%，其中转移成功的概率为2/3。按分支延迟为3个时钟周期的情况，试计算该流水线指令的平均时钟周期数。（流水线理想的CPI=1）75.1%751%25)13()(1ICICCPICPIinii2、有关措施为了减小分支延迟造成的损失，可采用以下措施：1）在流水线中尽早判断出分支转移是否成功。2）尽早计算出分支目标地址。两种措施同时采用，缺一不可。假设该两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。3.4流水线的相关与冲突减少分支延迟的方法有多种，下面介绍3种常见的方法。减少分支延迟的方法：通过软件（编译器）来减少分支延迟（静态方法）（1）预测分支失败允许分支指令后的指令继续在流水线中流动，就好象什么都没发生似的。若确定分支失败，将分支指令看作是一条普通指令，流水线正常流动。若确定分支成功，流水线就把在分支指令之后取出的所有指令转化为空操作，并按分支目地重新取指令执行。3.4流水线的相关与冲突预测分支失败的情况：分支失败分支成功3.4流水线的相关与冲突例如：在某一程序中，分支指令在程序中所占的比例为25%，其中转移成功的概率为2/3。试计