Slide 1AnnouncementsAnnouncementsGoals for TodayBroken ExampleWhat Can Go Wrong?Detecting Data HazardsResolving Data HazardsStallingForwarding DatapathStallingForwardingForwardingForwardingForwarding Path 1WB to EX BypassForwarding Path 2MEM to EX BypassForwarding DatapathTricky ExampleMore Data HazardsRegister File BypassQuizMemory Load Data HazardResolving Memory Load HazardQuiz 2Data Hazard RecapMore HazardsMore HazardsControl HazardsDelay SlotControl Hazards: Speculative ExecutionLoopsBranch PredictionPipelining: What Could Possibly Go Wrong?Pipeline HazardsHakim WeatherspoonCS 3410, Spring 2011Computer ScienceCornell UniversitySee P&H Appendix 4.72AnnouncementsPA1 available: mini-MIPS processorPA1 due next FridayWork in pairsUse your resources•FAQ, class notes, book, Sections, office hours, newsgroup, CSUGLabHW1 graded•Max: 10; Median: 9; Mean: 8.3; Stddev: 1.8•Great job!•Regrade policy–Submit written request to lead TA, lead TA will pick a different grader –Submit another written request, lead TA will regrade directly –Submit yet another written request for professor to regrade.3AnnouncementsPrelims: •Thursday, March 10th in class•Thursday, April 28th EveningLate Policy1) Each person has a total of four “slip days”2) For projects, slip days are deducted from all partners 3) 10% deducted per day late after slip days are exhausted4Goals for TodayData Hazards•Data dependencies•Problem, detection, and solutions–(delaying, stalling, forwarding, bypass, etc)•Forwarding unit•Hazard detection unitNext time•Control HazardsWhat is the next instruction to execute ifa branch is taken? Not taken?5Broken ExampleIFIDMEMWBIFIDMEM WBIFIDMEM WBIFIDMEM WBIFIDMEMWBClock cycle1 2 3 4 5 6 7 8 9sub r5, r3, r4lw r6, 4(r3)or r5, r3, r5sw r6, 12(r3)add r3, r1, r26What Can Go Wrong?Data Hazards•register file reads occur in stage 2 (ID) •register file writes occur in stage 5 (WB)•next instructions may read values about to be writtenHow to detect? Logic in ID stage:stall = (ID.rA != 0 && (ID.rA == EX.rD || ID.rA == M.rD || ID.rA == WB.rD)) || (same for rB)7IF/ID+4ID/EX EX/MEM MEM/WBmemdindoutaddrinstPC+4OP B ARdB DM DPC+4 immOP RdOP RdPCinstmemRdRa RbDBAdetecthazardDetecting Data Hazardsadd r3, r1, r2sub r5, r3, r5or r6, r3, r4 add r6, r3, r88Resolving Data HazardsWhat to do if data hazard detected?9StallingClock cycle1 2 3 4 5 6 7 8add r3, r1, r2sub r5, r3, r5or r6, r3, r4 add r6, r3, r810Forwarding DatapathdatamemBABDMDinstmemDrDBARdRdRdWEWEOpWEOprA rBPC+4Opnopinst/stall11StallingHow to stall an instruction in ID stage•prevent IF/ID pipeline register update–stalls the ID stage instruction•convert ID stage instr into nop for later stages–innocuous “bubble” passes through pipeline•prevent PC update–stalls the next (IF stage) instruction12ForwardingClock cycle1 2 3 4 5 6 7 8add r3, r1, r2sub r5, r3, r5or r6, r3, r4 add r6, r3, r813ForwardingClock cycle1 2 3 4 5 6 7 8add r3, r1, r2sub r5, r3, r4lw r6, 4(r3)or r5, r3, r5sw r6, 12(r3)14ForwardingForward correct value from?1. ALU output: too late in cycle?2. EX/MEM.D pipeline register (output from ALU)3. WB data value (output from ALU or memory)4. MEM output: too late in cycle,on critical pathto?a) ID (just after register file)–maybe pointless?b) EX, just after ID/EX.A and ID/EX.B are readc) MEM, just after EX/MEM.B is read: on critical pathdatamemBABDMDinstmemDBA15Forwarding Path 1add r4, r1, r2nopsub r6, r4, r1datameminstmemDBA16WB to EX BypassWB to EX Bypass•EX needs value being written by WBResolve:Add bypass from WB final value to start of EX Detect:17Forwarding Path 2add r4, r1, r2sub r6, r4, r1datameminstmemDBA18MEM to EX BypassMEM to EX Bypass•EX needs ALU result that is still in MEM stageResolve:Add a bypass from EX/MEM.D to start of EXDetect:19Forwarding DatapathdatamemBABDMDinstmemDBARdRdRbWEWEMCRaMC20Tricky ExampledatameminstmemDBAadd r1, r1, r2SUB r1, r1, r3OR r1, r4, r121More Data Hazardsadd r4, r1, r2nopnopsub r6, r4, r1datameminstmemDBA22Register File BypassRegister File Bypass•Reading a value that is currently being writtenDetect:((Ra == MEM/WB.Rd) or (Rb == MEM/WB.Rd))and (WB is writing a register)Resolve:Add a bypass around register file (WB to ID)Better: (Hack) just negate register file clock–writes happen at end of first half of each clock cycle–reads happen during second half of each clock cycle23QuizFind all hazards, and say how they are resolved:add r3, r1, r2sub r3, r2, r1nand r4, r3, r1or r0, r3, r4xor r1, r4, r3sb r4, 1(r0)24Memory Load Data Hazardlw r4, 20(r8)sub r6, r4, r1datameminstmemDBA25Resolving Memory Load HazardLoad Data Hazard•Value not available until WB stage •So: next instruction can’t proceed if hazard detectedResolution:•MIPS 2000/3000: one delay slot –ISA says results of loads are not available until one cycle later–Assembler inserts nop, or reorders to fill delay slot•MIPS 4000 onwards: stall–But really, programmer/compiler reorders to avoid stalling in the load delay slot26Quiz 2add r3, r1, r2nand r5, r3, r4add r2, r6, r3lw r6, 24(r3)sw r6, 12(r2)27Data Hazard RecapDelay Slot(s)•Modify ISA to match implementationStall•Pause current and all subsequent instructionsForward/Bypass•Try to steal correct value from elsewhere in pipeline•Otherwise, fall back to stalling or require a delay slotTradeoffs?28More Hazardsbeq r1, r2, Ladd r3, r0, r3sub r5, r4, r6L: or r3, r2, r4datameminstmemDBAPC+429More Hazardsbeq r1, r2, Ladd r3, r0, r3sub r5, r4, r6L: or r3, r2, r4datameminstmemDBAPC+430Control HazardsControl Hazards•instructions are fetched in stage 1 (IF)•branch and jump decisions occur in stage 3 (EX) •i.e. next PC is not known until 2 cycles after branch/jumpDelay Slot•ISA says N instructions after branch/jump always executed–MIPS has 1 branch delay slotStall (+ Zap)•prevent PC update•clear IF/ID pipeline register–instruction just fetched might be wrong one, so convert to nop•allow branch to continue into EX stage31Delay Slotbeq r1, r2, Lori r2, r0, 1L: or r3, r1, r4datameminstmemDBAPC+4branchcalcdecidebranch32Control Hazards: Speculative ExecutionControl Hazards•instructions are fetched in stage 1 (IF)•branch and jump decisions occur in stage 3 (EX) •i.e. next PC not known until 2 cycles after branch/jumpStallDelay SlotSpeculative Execution•Guess direction of the branch–Allow instructions to move through pipeline–Zap them later if wrong guess•Useful for long
View Full Document
Unlocking...