高级计算机体系结构-3-1.

1AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering高级流水线与指令级并1流水线技术基础2指令级并行概念与技术3流水线动态调度与预测4高级流水线技术2AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering3.1流水线技术基础3.1.1什么是流水线（pipeline)流水线是实现多条指令重叠执行的技术，是加快CPU执行速度的关键技术。流水线技术是将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行术语：流水级（pipestage):流水线由多个流水级组成，通常一条指令由n级流水级完成。每个流水级完成指令的部分任务。吞吐量（throughput):单位时间内流出流水线的指令数。3AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering什么是流水线(2)机器周期（machinecycle):完成一个基本操作所需要的时间，CPU周期。不同流水线完成指令功能不等，所需时间有长有短，因此设计流水线的关键是合理划分指令功能，使每一流水级完成指令功能的时间大致相等。机器周期由最长流水级的时间决定，通常等于时钟周期。4AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering什么是流水线(3)理想流水线的加速因子（Speedup)非流水线机器指令的平均执行时间=--------------------------------流水线机器指令的平均执行时间非流水线机器指令的平均执行时间=----------------------------------非流水线机器指令的平均执行时间/流水级数=流水级数5AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering3.1.2DLX指令的非流水线实现(1)DLX,是一RISC体系结构计算机。DLX指令的非流水线实现分五步（即5个时钟周期）完成：DLX简单流水线的实现示意图6AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering1、取指令周期（IF）IRMem[PC]NPCPC+42、译码/读寄存器周期（ID）AReg[IR6..10]BReg[IR11..15]Imm((IR16)16##IR16..31)7AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineeringDLX指令的非流水线实现(2)3、执行/有效地址计算（EX）Load/StoreALUoutputA+ImmR-RALUALUoutputAfuncBR-IALUALUoutputAopImmBranchALUoutputNPC+Imm;CondAop08AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineeringDLX指令的非流水线实现(3)4、存储器访问/转移完成（MEM）Load/Store：LMDMem[ALUoutput]Mem[ALUoutput]BBranchif(Cond)thenPCALUoutputelsePCNPC9AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineeringDLX指令的非流水线实现(4)5、写回周期（WB）R-RALURegs[IR16..20]ALUoutputR-IALURegs[IR11..15]ALUoutputLoadRegs[IR11..15]LMD10AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering11AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering3.1.3DLX的基本流水线(1)流水时钟数指令序列123456789指令iIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB指令i+4IFIDEXMEMWBDLX简单流水线的流水过程12AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineeringDLX流水线节拍与CPU相关硬件的时间关系图时钟周期IMRegRegALUDMIMALUDMIMALUDMIMALUDMIMALUDMRegRegRegRegRegRegRegRegCC1CC2CC4CC3CC5CC6CC7CC8CC9程序执行序列13AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering实现流水线后,对硬件的要求更高了,并需作相应的改变,主要有以下2点:IM,DM必须分开,或由一双端口存储器代替IM和DM;IM,DM的带宽要提高5倍,(对DLX的5级流水线而言)另外,可以发现Branch指令将要推迟三个节拍.14AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineeringDLX流水化CPU中数据通路的实现图数据存储器MUXSignextendMUXMUX0?ALU寄存器3216PC数据存储器ADDMUXIF/ID转移发生ID/EXEX/MEMMEM/WBIR6..10IR11..15MEM/WB.IR4IR15AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering图中注意:在两个相邻节拍间增加一暂存器,用来保留指令的状态(及数据),共有IF/ID,ID/EX,EX/MEM,MEM/WB四个.16AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineeringDlX流水线的形式化描述流水时钟数指令序列123456789指令iIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3IFIDEXMEMWB指令i+4IFIDEXMEMWB17AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering3.1.4流水线的主要障碍--流水线竞争(pipelinehazards)定义:流水线竞争是流水线中造成下一条指令不能在指令时钟周期被执行的情况.18AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering流水线竞争(2)流水线竞争分三类:结构竞争(structurehazards)----试图同时以两种不同的方式使用同一资源；原因：硬件无法支持同时重叠执行的所有可能的指令组合数据竞争(datahazard)----在产生数据之前,就试图使用它们原因：流水线中的重叠执行的指令依赖于前面指令的结果控制竞争(controlhazard)----在判定转移条件之前，就试图决策转移方向原因：可能改变PC的指令的流水19AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering3.1.5流水线竞争举例及其解决方法1.结构竞争单口存储器造成存储器访问冲突,造成流水线停顿实例.20AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering结构竞争流水时钟数指令序列12345678910Load指令IFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3stallIFIDEXMEMWB指令i+4IFIDEXMEMWB指令i+5IFIDEXMEM21AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineeringMemM时钟周期RegRegALUMemMemMemALUMemALUALUMemMemRegRegMemRegRegRegCC1CC2CC4CC3CC5CC6CC7CC8Load指令1指令2Stall指令3气泡气泡气泡气泡气泡22AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering结构竞争造成停顿改进方法:增加硬件的拷贝数使硬件流水化23AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering2.数据竞争[例]ADDR1,R2,R3SUBR4,R5,R1ANDR6,R1,R7ORR8,R1,R9XORR10,R1,R11后四条指令都用ADD的结果R1作为源操作数.24AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering数据相关性引起数据竞争时钟周期IMALUDMRegRegIMALUDMALUIMDMIMALUIMCC1CC2CC4CC3CC5CC6RegRegRegRegRegADDR1,R2,R3SUBR4,R1,R5ANDR6,R1,R7ORR8,R1,R9XORR10,R1,R11程序执行序列25AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering数据竞争解决说明:SUB和ADD必须分别停顿2个和1个Cycle才能得到所需的R1的值,Or由于Reg.是在Cycle前沿写入,在Cycle中间读出,正好解决.26AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering数据竞争的分类:RAW(Readafterwrite)WAW(Writeafterwrite)LWR1,0(R2)ADDR1,R2,R3若先写,则造成WAW.WAR(Writeafterread)SW0(R1),R2ADDR2,R3,R4若先写,则造成WAR.DLX不会发生此WAW,WARWb在最后一拍Read(ID)总是早于WB27AdvancedComputerArchitectureTheSchoolofInformationScienceandEngineering解决数据竞争的方法2Forwarding技术,可由硬件实现在发生上述数据相关时，后面的指令并不是马上就要用到前一条指令的计算结果。如果能够将计算结果从其产生的地方直接送到需要它的地方，就可以避免暂停；进入流水线的指令一旦检测到与前面的指令有RAW相关，就stall流水线，等待竞争消除，然后再继续执行。----极大地降低流水线的效率1.RAW竞争最简单的解决方法