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 24, 2003Wed., Sep 24, 2003Topic: Topic: Pipelining -- Intermediate ConceptsPipelining -- Intermediate Concepts(Multicycle Operations; Exceptions)(Multicycle Operations; Exceptions)2OutlineOutlineMulti-cycle operationsMulti-cycle operationsFloating-point operationsFloating-point operationsStructural and data hazardsStructural and data hazardsInterrupts, Faults and ExceptionsInterrupts, Faults and ExceptionsPrecise exceptionsPrecise exceptionsComplications in pipelinesComplications in pipelinesREADING: Appendix AREADING: Appendix A3Pipelining Multicycle OperationsPipelining Multicycle OperationsAssume five-stage pipelineAssume five-stage pipelineThird stage (execution) has two functional Third stage (execution) has two functional units E1 and E2units E1 and E2Instruction goes through either E1 or E2, but not bothInstruction goes through either E1 or E2, but not bothE1 and E2 are not pipelinedE1 and E2 are not pipelinedStage delay of E1 = 2 cyclesStage delay of E1 = 2 cyclesStage delay of E2 = 4 cyclesStage delay of E2 = 4 cyclesNo buffering on inputs of E1 and E2No buffering on inputs of E1 and E2Stage delay of other stages = 1 cycleStage delay of other stages = 1 cycleConsider an instruction sequence of five Consider an instruction sequence of five instructionsinstructionsInstructions 1, 3, 5 need E1Instructions 1, 3, 5 need E1Instructions 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 4Out-of-order completionOut-of-order completion3 finishes before 2, and 5 finishes before 43 finishes before 2, and 5 finishes before 4Instructions may be delayed after entering the pipeline Instructions may be delayed after entering the pipeline because of because of structural hazardsstructural hazardsInstructions 2 and 4 both want to use E2 unit at same timeInstructions 2 and 4 both want to use E2 unit at same timeInstruction 4 Instruction 4 stallsstalls in ID unit in ID unitThis 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 BThis 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 1Don’t replicate resources; detect and serialize access as neededDon’t replicate resources; detect and serialize access as neededEarly resolutionEarly resolutionTrack use of WB in ID stage (using shift register), stall instructions thereTrack use of WB in ID stage (using shift register), stall instructions therereservation registerreservation registerSimplifies pipeline control; all stalls occur in IDSimplifies pipeline control; all stalls occur in IDadds shift register and write-conflict logicadds shift register and write-conflict logicLate resolutionLate resolutionStall instructions at entry to MEM or WB stageStall instructions at entry to MEM or WB stageComplicates pipeline control (two stall locations)Complicates pipeline control (two stall locations)71 2 3 4 5 6 7 8 9 10 11 12 13DIV.D (issued a t t = -16) D D D D D D D D DMEMW BMULT.D F0, F4, F6 IF ID s M1 M2 M3 M4 M5 M6 M7MEMW Binteger instruction IF s ID EXMEMW Binteger instruction IF ID EXMEMW BADD.D F2, F4, F6 IF ID s A1 A2 A3 A4MEMW BL.D F2, 0(R2)IF ID EXMEMW BWAW HazardsWAW HazardsWAW 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.DAdding 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 hazardCan 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 correctlyHazard resolutionHazard resolutionDelay the issue of L.D until ADD.D enters MEMDelay the issue of L.D until ADD.D enters MEMCancel 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 HazardsLonger 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
View Full Document