3.3-流水线相关冲突及解决办法-v3.0

©1北京信息科技大学计算机体系结构3流水线技术张伟计算机学院计算机体系结构北京信息科技大学3.4流水线的相关相关：两条指令之间存在某种依赖关系。如果两条指令相关，则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。相关有3种类型数据相关（也称真数据相关）名相关控制相关计算机体系结构北京信息科技大学3.4流水线的相关数据相关对于两条指令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流水线的相关当数据的流动是经过寄存器时，相关的检测比较直观和容易。当数据的流动是经过存储器时，检测比较复杂。相同形式的地址其有效地址未必相同。形式不同的地址其有效地址却可能相同。2.名相关名：指令所访问的寄存器或存储器单元的名称。如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。计算机体系结构北京信息科技大学3.4流水线的相关指令j与指令i之间的名相关有两种：反相关：如果指令j写的名与指令i读的名相同，则称指令i和j发生了反相关。指令j写的名＝指令i读的名输出相关：如果指令j和指令i写相同的名，则称指令i和j发生了输出相关。指令j写的名＝指令i写的名计算机体系结构北京信息科技大学3.4流水线的相关名相关的两条指令之间并没有数据的传送。如果一条指令中的名改变了，并不影响另外一条指令的执行。换名技术换名技术：通过改变指令中操作数的名来消除名相关。对于寄存器操作数进行换名称为寄存器换名。既可以用编译器静态实现，也可以用硬件动态完成。计算机体系结构北京信息科技大学3.4流水线的相关例如：考虑下述代码：DIV.DF2，F6，F4ADD.DF6，F0，F12SUB.DF8，F6，F14DIV.D和ADD.D存在反相关。进行寄存器换名（F6换成S）后，变成：DIV.DF2，F6，F4ADD.DS，F0，F12SUB.DF8，S，F14计算机体系结构北京信息科技大学3.4流水线的相关3.控制相关控制相关是指由分支指令引起的相关。为了保证程序应有的执行顺序，必须严格按控制相关确定的顺序执行。典型的程序结构是“if-then”结构。请看一个示例：ifp1{S1；}；S；ifp2{S2；}；计算机体系结构北京信息科技大学3.4流水线的相关控制相关带来了以下两个限制：与一条分支指令控制相关的指令不能被移到该分支之前，否则这些指令就不受该分支控制了。对于上述的例子，then部分中的指令不能移到if语句之前。如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。对于上述的例子，不能把S移到if语句的then部分中。计算机体系结构北京信息科技大学3.4流水线的冲突流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。流水线冲突有3种类型：结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。控制冲突：流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。计算机体系结构北京信息科技大学3.4流水线的冲突带来的几个问题：导致错误的执行结果。流水线可能会出现停顿，从而降低流水线的效率和实际的加速比。我们约定当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行（否则就永远无法消除冲突）。计算机体系结构北京信息科技大学3.4流水线的冲突结构冲突在流水线处理机中，为了能够使各种组合的指令都能顺利地重叠执行，需要对功能部件进行流水或重复设置资源。如果某种指令组合因为资源冲突而不能正常执行，则称该处理机有结构冲突。常见的导致结构相关的原因：功能部件不是完全流水资源份数不够计算机体系结构北京信息科技大学3.4流水线的冲突结构冲突举例：访存冲突有些流水线处理机只有一个存储器，将数据和指令放在一起，访存指令会导致访存冲突。解决办法Ⅰ：插入暂停周期（“流水线气泡”或“气泡”）引入暂停后的时空图解决方法Ⅱ：设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。计算机体系结构北京信息科技大学3.4流水线的冲突由于访问同一个存储器而引起的结构冲突计算机体系结构北京信息科技大学3.4流水线的冲突为消除结构冲突而插入的流水线气泡计算机体系结构北京信息科技大学3.4流水线的冲突引入暂停后的时空图指令编号时钟周期12345678910指令iIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWBWB指令i+3stallIFIDEXMEMWB指令i+4IFIDEXMEMWB指令i+5IFIDEXMEM计算机体系结构北京信息科技大学3.4流水线的冲突有时流水线设计者允许结构冲突的存在主要原因：减少硬件成本如果把流水线中的所有功能单元完全流水化，或者重复设置足够份数，那么所花费的成本将相当高。2.数据冲突当相关的指令靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们非流水实现时的顺序，则发生了数据冲突。计算机体系结构北京信息科技大学3.4流水线的冲突举例：DADDR1，R2，R3DSUBR4，R1，R5XORR6，R1，R7ANDR8，R1，R9ORR10，R1，R11计算机体系结构北京信息科技大学3.4流水线的冲突流水线的数据冲突举例计算机体系结构北京信息科技大学3.4流水线的冲突根据指令读访问和写访问的顺序，可以将数据冲突分为3种类型。考虑两条指令i和j，且i在j之前进入流水线，可能发生的数据冲突有：写后读冲突（RAW）在i写入之前，j先去读。j读出的内容是错误的。这是最常见的一种数据冲突，它对应于真数据相关。计算机体系结构北京信息科技大学3.4流水线的冲突写后写冲突（WAW）在i写入之前，j先写。最后写入的结果是i的。错误！这种冲突对应于输出相关。写后写冲突仅发生在这样的流水线中：流水线中不只一个段可以进行写操作。当先前某条指令停顿时，允许其后续指令继续前进。前面介绍的5段流水线不会发生写后写冲突。（只在WB段写寄存器）计算机体系结构北京信息科技大学3.4流水线的冲突读后写冲突（WAR）在i读之前，j先写。i读出的内容是错误的！由反相关引起。这种冲突仅发生在这样的情况下：有些指令的写结果操作提前了，而且有些指令的读操作滞后了。指令被重新排序了。读后写冲突在前述5段流水线中不会发生。（读操作（在ID段）在写结果操作（在WB段）之前）计算机体系结构北京信息科技大学3.4流水线的冲突通过定向技术减少数据冲突引起的停顿（定向技术也称为旁路或短路）关键思想：在某条指令产生计算结果之前，其他指令并不真正立即需要该计算结果，如果能够将该计算结果从其产生的地方直接送到其他指令需要它的地方，那么就可以避免停顿。采用定向技术消除上例中的相关工作过程演示计算机体系结构北京信息科技大学3.4流水线的冲突采用定向技术后的流水线数据通路计算机体系结构北京信息科技大学3.4流水线的冲突当定向硬件检测到前面某条指令的结果寄存器就是当前指令的源寄存器时，控制逻辑会将前面那条指令的结果直接从其产生的地方定向到当前指令所需的位置。结果数据不仅可以从某一功能部件的输出定向到其自身的输入，而且还可以定向到其他功能部件的输入。举例:DSUBR1，R2，R3LDR5，0（R1）SDR5，12（R1）计算机体系结构北京信息科技大学3.4流水线的冲突更多的定向路径计算机体系结构北京信息科技大学3.4流水线的冲突需要停顿的数据冲突并不是所有的数据冲突都可以用定向技术来解决。举例:LDR1，0（R2）DADDR4，R1，R5ANDR6，R1，R7XORR8，R1，R9增加流水线互锁硬件，插入“暂停”。作用：检测发现数据冲突，并使流水线停顿，直至冲突消失。举例：演示A演示B计算机体系结构北京信息科技大学3.4流水线的冲突无法将LD指令的结果定向到DADD指令计算机体系结构北京信息科技大学3.4流水线的冲突流水线互锁机制插入气泡后的执行过程计算机体系结构北京信息科技大学3.4流水线的冲突流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。流水线冲突有3种类型：结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。控制冲突：流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。计算机体系结构北京信息科技大学3.4流水线的冲突流水线的数据冲突举例计算机体系结构北京信息科技大学3.4流水线的冲突采用定向技术后的流水线数据通路计算机体系结构北京信息科技大学3.4流水线的冲突更多的定向路径计算机体系结构北京信息科技大学3.4流水线的冲突无法将LD指令的结果定向到DADD指令计算机体系结构北京信息科技大学3.4流水线的冲突流水线互锁机制插入气泡后的执行过程计算机体系结构北京信息科技大学3.4控制冲突执行分支指令的结果有两种分支成功：PC值改变为分支转移的目标地址。在条件判定和转移地址计算都完成后，才改变PC值。不成功或者失败：PC的值保持正常递增，指向顺序的下一条指令。处理分支指令最简单的方法：“冻结”或者“排空”流水线。优点：简单。前述5段流水线中，改变PC值是在MEM段进行的。图示给流水线带来了3个时钟周期的延迟。计算机体系结构北京信息科技大学MEM/WB数据存储器通用寄存器组符号位扩展ALUPC=0?ADD16324存储器分之结果MUX1MUX2MUX3MUX4IRABImmIR[rs]IR[rt]MEM/WB.IRNPCNPCIRcondALUoBIRLMDALUoIREX/MEMID/EXIF/ID指令流水实现的数据通路计算机体系结构北京信息科技大学分支指令IFIDEXMEMWB分支目标指令IFstallstallIFIDEXMEMWB分支目标指令+1IFIDEXMEMWB分支目标指令+2IFIDEXMEM分支目标指令+3IFIDEX分支指令IFIDEXMEMWB分支后继指令IFstallstallIFIDEXMEMWB分支后继指令+1IFIDEXMEMWB分支后继指令+2IFIDEXMEM分支后继指令+3IFIDEX简单处理分支指令：分支成功的情况简单处理分支指令：分支失败的情况计算机体系结构北京信息科技大学3.4控制冲突把由分支指令引起的延迟称为分支延迟。分支指令在目标代码中出现的频度每3～4条指令就有一条是分支指令。假设：分支指令出现的频度是30％，流水线理想CPI＝1，那么：流水线的实际CPI＝1.9。可采取两种措施来减少分支延迟。在流水线中尽早判断出分支转移是否成功；尽早计算出分支目标地址。计算机体系结构北京信息科技大学3.4控制冲突下面的讨论中，我们假设：这两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。计算机体系结构北京信息科技大学3.4控制冲突3种通过软件（编译器）来减少分支延迟的方法共同点：对分支的处理方法在程序的执行过程中始终是不变的，是静态的。要么总是预测分支成功，要么总是预测分支失败。预测分支失败允许分支指令后的指令