G22.2233 L06 Containing Control Hazards. 1 Banikazemi, NYU, 2007CS G22.2233 Computer Systems Design Spring 2007Lecture 05: Overcoming Data HazardsMohammad Banikazemi[Slides from Prof. Mary Jane Irwin, PSU Adapted fromComputer Organization and Design, Patterson & Hennessy, © 2005, UCB]G22.2233 L06 Containing Control Hazards. 2 Banikazemi, NYU, 2007Review: Why Pipeline? For Performance!Instr.OrderTime (clock cycles)Inst 0Inst 1Inst 2Inst 4Inst 3ALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegOnce the pipeline is full, one instruction is completed every cycle, so CPI = 1Time to fill the pipelineG22.2233 L06 Containing Control Hazards. 3 Banikazemi, NYU, 2007Review: Can Pipelining Get Us Into Trouble? Yes: Pipeline HazardsO structural hazards: attempt to use the same resource by two different instructions at the same timeO data hazards: attempt to use data before it is ready- An instruction’s source operand(s) are produced by a prior instruction still in the pipelineO control hazards: attempt to make a decision about program control flow before the condition has been evaluated and the new PC target address calculated- branch instructionsCan always resolve hazards by waitingO pipeline control must detect the hazardO and take action to resolve hazardsG22.2233 L06 Containing Control Hazards. 4 Banikazemi, NYU, 2007Instr.OrderTime (clock cycles)lwInst 1Inst 2Inst 4Inst 3ALUMemRegMem RegALUMemRegMem RegALUMemRegMem RegALUMemRegMem RegALUMemRegMem RegA Single Memory Would Be a Structural HazardReading data from memoryReading instruction from memory Fix with separate instr and data memories (I$ and D$)G22.2233 L06 Containing Control Hazards. 5 Banikazemi, NYU, 2007How About Register File Access?Instr.OrderTime (clock cycles)add $1,Inst 1Inst 2add $2,$1,ALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegG22.2233 L06 Containing Control Hazards. 6 Banikazemi, NYU, 2007How About Register File Access?Instr.OrderTime (clock cycles)Inst 1Inst 2ALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegFix register file access hazard by doing reads in the second half of the cycle and writes in the first halfadd $1,add $2,$1,clock edge that controls register writingclock edge that controls loading of pipeline state registersG22.2233 L06 Containing Control Hazards. 7 Banikazemi, NYU, 2007Register Usage Can Cause Data HazardsInstr.Orderadd $1,sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9ALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM Reg Dependencies backward in time cause hazards Read before write data hazardG22.2233 L06 Containing Control Hazards. 8 Banikazemi, NYU, 2007Register Usage Can Cause Data HazardsALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM Reg Dependencies backward in time cause hazardsadd $1,sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9 Read After Write (RAW) data hazardG22.2233 L06 Containing Control Hazards. 9 Banikazemi, NYU, 2007Loads Can Cause Data HazardsInstr.Orderlw $1,4($2)sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9ALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM Reg Dependencies backward in time cause hazards Load-use (RAW) data hazardG22.2233 L06 Containing Control Hazards. 10 Banikazemi, NYU, 2007stallstallOne Way to “Fix” a Data HazardInstr.Orderadd $1,ALUIMRegDM Regsub $4,$1,$5and $6,$1,$7ALUIMRegDM RegALUIMRegDM RegCan fix data hazard by waiting – stall –but impacts CPIG22.2233 L06 Containing Control Hazards. 11 Banikazemi, NYU, 2007Another Way to “Fix” a Data HazardInstr.Orderadd $1,ALUIMRegDM Regsub $4,$1,$5and $6,$1,$7ALUIMRegDM RegALUIMRegDM RegFix data hazards by forwardingresults as soon as they are availableto where they are neededxor $4,$1,$5or $8,$1,$9ALUIMRegDM RegALUIMRegDM RegG22.2233 L06 Containing Control Hazards. 12 Banikazemi, NYU, 2007Another Way to “Fix” a Data HazardALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegFix data hazards by forwardingresults as soon as they are availableto where they are neededALUIMRegDM RegALUIMRegDM RegInstr.Orderadd $1,sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9G22.2233 L06 Containing Control Hazards. 13 Banikazemi, NYU, 2007Forwarding with Load-use Data HazardsInstr.Orderlw $1,4($2)sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9ALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegG22.2233 L06 Containing Control Hazards. 14 Banikazemi, NYU, 2007Forwarding with Load-use Data HazardsALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM Reg Will still need one stall cycle even with forwardingInstr.Orderlw $1,4($2)sub $4,$1,$5and $6,$1,$7xor $4,$1,$5or $8,$1,$9G22.2233 L06 Containing Control Hazards. 15 Banikazemi, NYU, 2007Branch Instructions Cause Control HazardsInstr.OrderlwInst 4Inst 3beqALUIMRegDM RegALUIMRegDM RegALUIMRegDM RegALUIMRegDM Reg Dependencies backward in time cause hazardsG22.2233 L06 Containing Control Hazards. 16 Banikazemi, NYU, 2007stallstallstallOne Way to “Fix” a Control HazardInstr.OrderbeqALUIMRegDM ReglwALUIMRegDM RegALUInst 3IMRegDMFix branch hazard by waiting –stall –but affects CPIG22.2233 L06 Containing Control Hazards. 17 Banikazemi, NYU, 2007Other Pipeline Structures Are Possible What about the (slow) multiply operation?O Make the clock twice as slow or …O let it take two cycles (since it doesn’t use the DM stage)ALUIMRegDM RegMULALUIMRegDM1 RegDM2 What if the data memory access is twice as slow as the instruction memory?O make the clock twice as slow or …O let data memory access take two cycles (and keep the same clock rate)G22.2233 L06 Containing Control Hazards. 18 Banikazemi, NYU, 2007Sample Pipeline Alternatives ARM7 StrongARM-1 XScaleALUIM1IM2DM1RegDM2IMRegEXPC updateIM accessdecoderegaccessALU opDM accessshift/rotatecommit result(write back)ALUIMRegDM RegRegSHFTPC updateBTB accessstart IM accessIM accessdecodereg 1 accessshift/rotatereg 2 accessALU opstart DM accessexceptionDM writereg writeG22.2233 L06 Containing Control Hazards. 19 Banikazemi, NYU, 2007Corrected Datapath to Save RegWrite Addr Need to preserve the destination register address in the pipeline state registersReadAddressInstructionMemoryAddPC4Write DataRead Addr 1Read Addr 2Write AddrRegisterFileReadData 1ReadData 216 32ALUShiftleft 2AddDataMemoryAddressWrite DataReadDataIF/IDSignExtendID/EX EX/MEMMEM/WBG22.2233 L06 Containing Control Hazards. 20 Banikazemi, NYU, 2007Corrected Datapath to Save RegWrite Addr Need