COMP 206: Computer Architecture and ImplementationOutlinePipelining Multicycle OperationsSpace-Time Diagram: Multicycle OperationsFloating-Point Operations in MIPSStructural Hazard on WB UnitWAW HazardsRAW HazardsResponsibilities of ID (all stalls in ID)MIPS R4000 Floating-Point PipelineInstruction Mixes in FP Pipeline: Adds OnlyFP Pipeline: Multiplies OnlyFP Pipeline: Adds and MultipliesInterrupts, Faults, or ExceptionsPrecise Interrupts (Sequential Processor)Problems on Sequential ProcessorsInterrupts in MIPS PipelineMIPS Integer Pipeline, Single InterruptComplications with Delayed BranchesComplications with Multiple ExceptionsComplications with Out-of-order ExceptionsComplications with Multicycle OperationsFP Pipeline Exceptions: Solns. 1 and 2FP Pipeline Exceptions: Solns. 3 and 41COMP 206:COMP 206:Computer Architecture and Computer Architecture and ImplementationImplementationMontek SinghMontek SinghWed., Sep 27, 2004Wed., Sep 27, 2004Topic: Topic: Pipelining -- Intermediate ConceptsPipelining -- Intermediate Concepts(Multicycle Operations; Exceptions)(Multicycle Operations; Exceptions)2OutlineOutlineMulti-cycle operationsMulti-cycle operationsFloating-point operationsFloating-point operationsStructural and data hazardsStructural and data hazardsInterrupts, Faults and ExceptionsInterrupts, Faults and ExceptionsPrecise exceptionsPrecise exceptionsComplications in pipelinesComplications in pipelinesREADING: Appendix AREADING: Appendix A3Pipelining Multicycle OperationsPipelining Multicycle OperationsAssume five-stage pipelineAssume five-stage pipelineThird stage (execution) has two functional Third stage (execution) has two functional units E1 and E2units E1 and E2Instruction goes through either E1 or E2, but not bothInstruction goes through either E1 or E2, but not bothE1 and E2 are not pipelinedE1 and E2 are not pipelinedStage delay of E1 = 2 cyclesStage delay of E1 = 2 cyclesStage delay of E2 = 4 cyclesStage delay of E2 = 4 cyclesNo buffering on inputs of E1 and E2No buffering on inputs of E1 and E2Stage delay of other stages = 1 cycleStage delay of other stages = 1 cycleConsider an instruction sequence of five Consider an instruction sequence of five instructionsinstructionsInstructions 1, 3, 5 need E1Instructions 1, 3, 5 need E1Instructions 2, 4 need E2Instructions 2, 4 need E24Space-Time Diagram: Multicycle Space-Time Diagram: Multicycle OperationsOperationsDelay 1 2 3 4 5 6 7 8 9 10 11 12 131 IF 1 2 3 4 5 5 51 ID 1 2 3 4 4 4 52 E1 1 1 3 3 5 54 E2 2 2 2 2 4 4 4 41 MEM 1 3 2 5 41 WB 1 3 2 5 4Out-of-order completionOut-of-order completion3 finishes before 2, and 5 finishes before 43 finishes before 2, and 5 finishes before 4Instructions may be delayed after entering the pipeline Instructions may be delayed after entering the pipeline because of because of structural hazardsstructural hazardsInstructions 2 and 4 both want to use E2 unit at same timeInstructions 2 and 4 both want to use E2 unit at same timeInstruction 4 Instruction 4 stallsstalls in ID unit in ID unitThis causes instruction 5 to This causes instruction 5 to stallstall in IF unit in IF unit5Floating-Point Operations in MIPSFloating-Point Operations in MIPSIFIFIDIDMEMMEMWBWBA1A1A2A2A3A3A4A4M1M1M2M2M3M3M4M4M5M5M6M6M7M7EXEXDIV (25)Structural hazard:not fully pipelinedStructural hazard:instructions havevarying runningtimesWAW hazardspossible; WARhazards notpossibleLonger operationlatency impliesmore frequentstalls for RAWhazardsOut-of-ordercompletion; hasramifications forexceptions6Structural Hazard on WB UnitStructural Hazard on WB Unit1 2 3 4 5 6 7 8 9 10 11DIV.D (issued at t = -16) D D D D D D D D DMEMW BMUL.D F0, F4, F6 IF ID M1 M2 M3 M4 M5 M6 M7MEMW Binteger instruction IF ID EXMEMW Binteger instruction IF ID EXMEMW BADD.D F2, F4, F6 IF ID A1 A2 A3 A4MEMW Binteger instruction IF ID EXMEMW Binteger instruction IF ID EXMEMW BL.D F2, 0(R2) IF ID EXMEMW BThis is worst-case scenario: max steady-state number of write ports is 1This is worst-case scenario: max steady-state number of write ports is 1Don’t replicate resources; detect and serialize access as neededDon’t replicate resources; detect and serialize access as neededEarly resolutionEarly resolutionTrack use of WB in ID stage (using shift register), stall instructions thereTrack use of WB in ID stage (using shift register), stall instructions therereservation registerreservation registerSimplifies pipeline control; all stalls occur in IDSimplifies pipeline control; all stalls occur in IDadds shift register and write-conflict logicadds shift register and write-conflict logicLate resolutionLate resolutionStall instructions at entry to MEM or WB stageStall instructions at entry to MEM or WB stageComplicates pipeline control (two stall locations)Complicates pipeline control (two stall locations)7WAW HazardsWAW HazardsWAW hazard arises only when no instruction between ADD.D and WAW hazard arises only when no instruction between ADD.D and L.D uses result computed by ADD.DL.D uses result computed by ADD.DAdding an instruction like “ADD.D F8,F2,F4” before L.D would stall Adding an instruction like “ADD.D F8,F2,F4” before L.D would stall pipeline enough for RAW hazard to avoid WAW hazardpipeline enough for RAW hazard to avoid WAW hazardCan happen through a branch/trap (example in HP3, Section A.9)Can happen through a branch/trap (example in HP3, Section A.9)Rare situation, but must still handle correctlyRare situation, but must still handle correctlyHazard resolutionHazard resolutionDelay the issue of L.D until ADD.D enters MEMDelay the issue of L.D until ADD.D enters MEMCancel write of ADD.DCancel write of ADD.D81 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19L: L.D F4, 0(R2) IF L M A A S S S S S S S DM:MUL.D F0, F4, F6 ID L M M A A A A A A A S DA:ADD.D F2, F0, F8 EX L S S S SS:S.D 0(R2), F2 Mult M M M M M M MD:DIV.D F12, F4, F8 Add A A A ADiv D D D D D DMEM L M A SW B L M A SRAW HazardsRAW HazardsLonger delays of FP operations increases number of stalls in Longer delays of FP operations increases number of stalls in response to RAW hazardsresponse to RAW hazardsTwo methods for reducing stallsTwo methods for reducing stallsCompiler could have moved instruction D between instructions M Compiler could have moved instruction D between instructions M and A, which would allow D to complete earlier; or hardware could and