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

1、n3.4 流水线的相关与冲突一、一个经典的5段流水线 (RISC(RISC流水线流水线) ) 一条指令的执行过程分为5个周期：取指令周期（取指令周期（IF）、指令）、指令译码译码/读寄存器周期（读寄存器周期（ID）、执行）、执行/有效地址计算周期（有效地址计算周期（EX）、）、存储器访问分支完成周期（存储器访问分支完成周期（MEM）、）、写回周期（写回周期（WBWB）。）。3.4 流水线的相关与冲突流水线的相关与冲突n三类指令对三类指令对5 5级流水线的占用情况级流水线的占用情况: :ALU指令指令LOAD/STORE分支指令分支指令S1IF 取指取指取指取指取指取指S2ID 译码译码,读通用

2、读通用寄存器寄存器译码译码,读通用寄存器读通用寄存器译码译码,读通用寄存读通用寄存器器S3EX 运算（运算（R-R,R-立即数）立即数）计算有效地址计算有效地址计算转移目标地计算转移目标地址址,设置条件码设置条件码S4MEM-访存访存(读或写读或写)（store完成）完成）若条件成立若条件成立,将转将转移目标地址送移目标地址送PC（分支完成）（分支完成）S5WB 结果写回通用结果写回通用寄存器寄存器（ALU完成）完成）读出数据写入通用寄读出数据写入通用寄存器存器-3.4 流水线的相关与冲突流水线的相关与冲突3.4 流水线的相关与冲突流水线的相关与冲突n流水设计中流水设计中的一些的一些问题及解决

3、：问题及解决：IF(取指令取指令)，MEM(读读/写写数据数据)，访存冲突。访存冲突。通用寄存器访存通用寄存器访存冲突冲突-分分半拍。半拍。专门的加法器：专门的加法器：PCPC+4。n5段流水线的两种描述方式n第一种描述（类似于时空图）3.4 流水线的相关与冲突流水线的相关与冲突n第二种描述（按时间错开的数据通路序列）3.4 流水线的相关与冲突流水线的相关与冲突二、相关二、相关n相关是指两条指令之间存在某种依赖关系。n 如果两条指令相关，则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。n主要是三种类型的相关: 数据数据相关相关 名名相关相关 控制控制相关相关3.4 流水线的相关与冲突

4、流水线的相关与冲突1、数据相关（真数据相关）、数据相关（真数据相关）n对于两条指令i（在前）和j（在后），如果下述条件之一成立，则称指令j与指令i数据相关。 u指令j使用指令i产生的结果；u指令j与指令k数据相关，而指令k又与指令i数据相关。n数据相关具有传递性。传递性。n数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者。3.4 流水线的相关与冲突流水线的相关与冲突例如：下面这一段代码存在数据相关 Loop： L. D F0，0(R1) / F0为数组元素 ADD.D F4，F0，F2 / 加上F2中的值 S. D F4 ，0(R1) / 保存结果 DADDIU R1，R1，8 /

5、 数组指针递减8个字节 BNE R1，R2，Loop / 如果R1R2，则分支3.4 流水线的相关与冲突流水线的相关与冲突当数据的流动是经过寄存器时，相关的检测比较直观当数据的流动是经过寄存器时，相关的检测比较直观和容易。和容易。当数据的流动是经过存储器时，检测比较复杂。当数据的流动是经过存储器时，检测比较复杂。 相同形式的地址其有效地址未必相同。相同形式的地址其有效地址未必相同。 形式不同的地址其有效地址却可能相同。形式不同的地址其有效地址却可能相同。3.4 流水线的相关与冲突流水线的相关与冲突2、名相关、名相关名：名：指令所访问的寄存器或存储器单元的名称。如果两条指令使用相同的名，但是它们

6、之间并没有数据流动，则称这两条指令存在名相关。3.4 流水线的相关与冲突流水线的相关与冲突指令j（在后）与指令i（在前）之间的名相关有两种： （1）反相关：）反相关：如果指令如果指令j写的名与指令写的名与指令i读的名相同，则读的名相同，则称指令称指令i和和j发生了反相关。发生了反相关。 指令i读的名 指令j写的名 例如： DIV.D F2，F6，F4 （先读）（先读） ADD.D F6，F0，F12 （后写（后写）（2） 输出相关：输出相关：如果指令如果指令j和指令和指令i写相同的名，则称写相同的名，则称指令指令i和和j发生了输出相关。发生了输出相关。 指令i写的名 指令j写的名3.4 流水线

7、的相关与冲突流水线的相关与冲突名相关小结：l名相关的两条指令之间并没有数据的传送。l但名相关的两条指令之间的执行顺序必须严格遵守。l如果一条指令中的名改变了，并不影响另外一条指令的执行。针对名相关：可采用换名技术，消除名相关。3.4 流水线的相关与冲突流水线的相关与冲突换名技术：换名技术：通过改变指令中操作数的名来消除名相关。 例如：考虑下述代码： DIV.DF2，F6，F4 ADD.DF6，F0，F12 SUB.DF8，F6，F14w进行寄存器换名（进行寄存器换名（F6 F6 换成换成 S S）后，变成：）后，变成： DIV.DF2，F6，F4 ADD.DS S，F0，F12 SUB.DF8

8、，S S，F14 3.4 流水线的相关与冲突流水线的相关与冲突反相关反相关3、控制相关、控制相关n控制相关控制相关是指由分支指令引起的相关。n典型的程序结构是“if-then”结构。3.4 流水线的相关与冲突流水线的相关与冲突if p1 if p1 S1 S1； ；S S；if p2 if p2 S2 S2； ； 控制相关带来了以下两个限制：两个限制：l 与一条分支指令控制相关的指令不能被移到该分支之前，否则这些指令就不受该分支控制了。l 如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。三、流水线冲突三、流水线冲突流水线冲突流水线冲突是指对于具体的流水线来说，由于相关的存

9、在，使得指令流中的下一条指令不能在指定的时钟周期执行。n 流水线冲突有3种类型：结构冲突结构冲突数据冲突数据冲突控制冲突控制冲突3.4 流水线的相关与冲突流水线的相关与冲突（一）（一）结构冲突结构冲突 指多条指令进入流水线后，在同一时间争用同一功能部件，从而发生冲突。n例如：存储器访问冲突1 2 3 4 5 6 7 8指令指令LOADIF ID EX MEM WB指令指令i+1 IF ID EX MEM WB指令指令i+2 IF ID EX MEM WB指令指令i+3 IF ID EX MEM WB指令指令i+4 IF ID EX MEM访存冲突访存冲突3.4 流水线的相关与冲突流水线的相关与

10、冲突3.4 流水线的相关与冲突流水线的相关与冲突n解决办法解决办法：暂停一拍（也称为流水线气泡，简称气泡）。暂停一拍（也称为流水线气泡，简称气泡）。1 2 3 4 5 6 7 8 9指令指令LOADIF ID EX MEM WB指令指令i+1 IF ID EX MEM WB指令指令i+2 IF ID EX MEM WB指令指令i+3 停顿停顿 IF ID EX MEM WB指令指令i+4 IF ID EX MEM3.4 流水线的相关与冲突流水线的相关与冲突 时时间间（时时钟钟周周期期） 1 2 3 4 5 6 M Reg ALU M Reg M Reg ALU M Reg M Reg ALU

11、M Reg 7 8 load 指指令令i+1 指指令令i+2 暂暂 停停 M Reg ALU M 指指令令i+3 气气泡泡 气气泡泡 气气泡泡 气气泡泡 气气泡泡 3.4 流水线的相关与冲突流水线的相关与冲突n解决方法解决方法： 设置相互独立的指令存储器和数据存储器或设置相互独设置相互独立的指令存储器和数据存储器或设置相互独立的指令立的指令CacheCache和数据和数据CacheCache。3.4 流水线的相关与冲突流水线的相关与冲突u 说明：有时流水线设计者允许结构冲突的存在 主要原因：主要原因：减少硬件成本减少硬件成本（二）（二）数据冲突数据冲突 1、数据冲突、数据冲突指由于流水线中各指

12、令重叠执行，使得原来对操作数的访问顺序发生变化，从而引起的一种数据冲突。 例如：DADD R1，R2，R3 （写R1） DSUB R4，R1，R5 （读R1）1 2 3 4 5 6DADDIF ID EX MEM WBDSUB IF ID EX MEM WB写写R1读读R13.4 流水线的相关与冲突流水线的相关与冲突n根据指令读访问和写访问的顺序，根据指令读访问和写访问的顺序，假设两条指令假设两条指令i i和和j j，且且i i在在j j之前进入流水线，可能发生的数据冲突有之前进入流水线，可能发生的数据冲突有3 3种类种类型型：（1 1）写后读冲突（）写后读冲突（RAWRAW） i i 写入写

13、入 j j 读出读出如果在如果在 i i 写入之前，写入之前，j j 先去读，先去读，j j 读出的内容是错误的。读出的内容是错误的。n- -对应对应真数据相关真数据相关。 3.4 流水线的相关与冲突流水线的相关与冲突（2 2）写后写冲突（）写后写冲突（WAWWAW） i i 写入写入 j j 写入写入 如果在如果在 i i 写入之前，写入之前，j j 先写，最后写入的结果是的错误！先写，最后写入的结果是的错误！n - -对应对应输出相关输出相关。n 写后写冲突发生的情况：写后写冲突发生的情况：n流水线中不只一个段可以进行写操作。（流水线中不只一个段可以进行写操作。（介绍的介绍的5 5段流水线

14、段流水线不会发生不会发生）n当先前某条指令停顿时，允许其后续指令继续前进。当先前某条指令停顿时，允许其后续指令继续前进。3.4 流水线的相关与冲突流水线的相关与冲突（3 3）读后写冲突（）读后写冲突（WARWAR） i i 读出读出j j 写入写入 如果在如果在 i i 读之前，读之前，j j 先写。先写。i i 读出的内容是错误的！读出的内容是错误的！n-对应对应反相关反相关。 n读后写冲突发生的情况：读后写冲突发生的情况：n有些指令的写结果操作提前了，而且有些指令的读操作滞后了。有些指令的写结果操作提前了，而且有些指令的读操作滞后了。n指令被重新排序了。指令被重新排序了。 读后写冲突在前述

15、读后写冲突在前述5 5段流水线中不会发生。段流水线中不会发生。（读操作（在（读操作（在IDID段）在写结果操作（在段）在写结果操作（在WBWB段）之前）段）之前）3.4 流水线的相关与冲突流水线的相关与冲突2、解决办法：、解决办法：- 针对针对“写后读冲突写后读冲突” 解决办法1：采用定向传送技术定向传送技术（旁路技术或相关专用通路技术）。3.4 流水线的相关与冲突流水线的相关与冲突例： DADD R1，R2，R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 OR R10，R1，R11 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM R

16、eg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU DADD R1， R2， R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 IM Reg OR R10，R1，R11 写写R1读读R1流水线的数据冲突举例 产生数产生数据据ALU目标目标R旁路传送旁路传送寄存器寄存器 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU DADD R1，R2，R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND

17、R8，R1，R9 IM Reg OR R10，R1，R11 3.4 流水线的相关与冲突流水线的相关与冲突采用定向技术后的流水线数据通路 n定向技术定向技术关键思想：关键思想： 在某条指令产生计算结果之前，其他指令并不真正立在某条指令产生计算结果之前，其他指令并不真正立即需要该计算结果，如果能够将该计算结果即需要该计算结果，如果能够将该计算结果从其产生的地从其产生的地方方直接送到其他指令直接送到其他指令需要它的地方需要它的地方，那么就可以避免停顿。，那么就可以避免停顿。n推广一般的情况：推广一般的情况： 结果数据不仅可以从某一功能部件的输出定向到其自身的输入，而且还可以定向到其他功能部件的输入。

18、3.4 流水线的相关与冲突流水线的相关与冲突 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM DSUB R1, R2, R3 LD R5，0(R1) SD R5，12(R1) 3.4 流水线的相关与冲突流水线的相关与冲突DSUB DSUB R1R1，R2R2，R3R3LD LD R5R5，0 0（R1R1）SD SD R5R5，1212（R1R1）但是，定向技术并不能解决所有但是，定向技术并不能解决所有RAW冲突。冲突。例如： LD R1，0（R2） DADD R4，R1，R5 AND R6，R1，R

19、7 XOR R8，R1，R9 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU LD R1，0(R2) DADD R4，R1，R5 AND R6，R1，R7 XOR R8，R1，R9 无法将无法将LD指令的结果定指令的结果定向到向到DADD指令指令 解决方法解决方法2：增加流水线互锁互锁硬件，插入“暂停”。作用：检测发现数据冲突，并使流水线停顿，直至冲突消失。 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM IM Reg A

20、LU IM Reg LD R1，0(R2) DADD R4，R1，R5 AND R6，R1，R7 XOR R8，R1，R9 气泡 气泡 气泡 解决方法解决方法3：指令调度技术（流水线调度）n前提：在非按序流动方式（乱步流动）的流水线中。n实现：通过编译器重新组织指令顺序来消除冲突。指允许输出结果的次序指允许输出结果的次序与输入指令的次序不同。与输入指令的次序不同。例如：例如：表达式表达式 A=B+C，采用典型的代码生成方法：，采用典型的代码生成方法：LD RbLD Rb，B B IF ID EX MEM WB LD RcLD Rc，C C IF ID EX MEMWB DADD RaDADD

21、Ra，RbRb，Rc Rc IF ID stallstall EX MEM WB SD Ra SD Ra ，A A IF stallstall ID EX MEM WB 3.4 流水线的相关与冲突流水线的相关与冲突调度前的代码 调度后的代码 LD Rb，BLD Rc，CDADD Ra，Rb，Rc SD Ra，ALD Re，ELD Rf，FDSUB Rd，Re，RfSD Rd，D LD Rb，BLD Rc，CLD Re，E DADD Ra，Rb，RcLD Rf，FSD Ra，A DSUB Rd，Re，RfSD Rd，D 例：例：请为下列表达式生成没有暂停的指令序列请为下列表达式生成没有暂停的指令

22、序列: : A AB BC C ； D DE EF F ； 假设载入延迟为假设载入延迟为1 1个个时钟周期。时钟周期。 （三）控制（三）控制冲突冲突1 1、控制冲突、控制冲突流水线流水线遇到分支指令（条件转移）和其他会改变遇到分支指令（条件转移）和其他会改变PC值值的指令所引起的冲突。的指令所引起的冲突。n分支指令的简单处理：“冻结”，或“排空”流水线1 2 3 4 5 6 7 8分支指令IF ID EX MEM WB分支目标指令i IF 停顿 停顿 IF ID EX MEM分支目标指令i+1 停顿 停顿 停顿 IF ID EX分支目标指令i+3 停顿 停顿 停顿 IF ID更新更新PC值值3

23、.4 流水线的相关与冲突流水线的相关与冲突检测到分支检测到分支分支延迟分支延迟:3个周期个周期3.4 流水线的相关与冲突流水线的相关与冲突n转移指令对流水线的影响转移指令对流水线的影响 假设：在某一程序中， 分支指令在程序中所占的比例为25%，其中转移成功的概率为2/3。按分支延迟为3个时钟周期的情况，试计算该流水线指令的平均时钟周期数。（流水线理想的CPI=1）75. 1%751%25) 13()(1ICICCPICPIinii2 2、有关措施、有关措施 为了减小分支延迟造成的损失，可采用以下措施：1）在流水线中尽早判断出分支转移是否成功。）在流水线中尽早判断出分支转移是否成功。2）尽早计算

24、出分支目标地址。）尽早计算出分支目标地址。n两种措施同时采用，缺一不可。n假设该两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期分支延迟为一个时钟周期。3.4 流水线的相关与冲突流水线的相关与冲突减少分支延迟的方法有多种，下面介绍减少分支延迟的方法有多种，下面介绍3种常见的方法。种常见的方法。n减少分支延迟的方法：通过软件（编译器）来减少分支延迟（静态方法）（1）预测分支失败）预测分支失败n允许分支指令后的指令继续在流水线中流动，就好象什么都没发生似的。n若确定分支失败，将分支指令看作是一条普通指令，流水线正常流动。n若确定分支成功，流水线就把在分支指令之后取出的所有指令转化为空操作，并按分支目地重新取指令执行。3.4 流水线的相关与冲突流水线的相关与冲突n预测分支失败的情况：预测分支失败的情况：分分支支失失败败分分支支成成功功3.4 流水线的相关与冲突流水线的相关与冲突n例如：在某一程序中， 分支指令在程序中所占的比例为25%，其中转移成功的概率为2/3。试计算该流水线指令的平均时钟周期数。（流水线理想的CPI=1） 解：假设采用预测分支失败的方法 则，执行一条指令的平均时钟周期数为CPI为： CPI = (1