COMP 206: Computer Architecture and ImplementationControl HazardControl Hazard: ExampleMore on Control HazardsReducing Branch DelaysDealing with Branch DelaysStall Strategy: 12-Stage PipelinePNT Strategy: 12-Stage PipelinePTA Strategy: 12-Stage PipelinePTB Strategy: 12-Stage PipelineEffect of Control Hazards on PipelinesSolution for 12-Stage PipelineDelayed Branches on MIPSDetails of Various Branch FlavorsInstruction Sequence Alteration StrategiesExample: Branch PenaltiesSolution: Branch Penalties1COMP 206:COMP 206:Computer Architecture and Computer Architecture and ImplementationImplementationMontek SinghMontek SinghMon., Sep 22, 2003Mon., Sep 22, 2003Topic: Topic: Pipelining -- Intermediate ConceptsPipelining -- Intermediate Concepts(Control Hazards)(Control Hazards)2Control HazardControl HazardA peculiar kind of RAW hazard involving the A peculiar kind of RAW hazard involving the program counterprogram counterPC written by branch instructionPC written by branch instructionPC read by instruction fetch unit (not another PC read by instruction fetch unit (not another instruction)instruction)Possible misbehavior is that instructions Possible misbehavior is that instructions fetched and executed after the branch fetched and executed after the branch instruction are not the ones specified by the instruction are not the ones specified by the branch instructionbranch instruction3Control Hazard: ExampleControl Hazard: ExampleBr-1BrBr+1Br+2Br+3…TBr-1BrBr+1Br+2Br+3…T1 2 3 4 5 6 7 8 9 10 11 12 13 14 15F Read PC Read PC Read PCFetch Br-1 Fetch Br Fetch TPC += 4 PC += 4 PC += 4D Br-1 Br TX Br-1 Br TM Br-1 Br TPC = BTAW Br-1 Br TUnpipelined implementation1 2 3 4 5 6F Read PC Read PC Read PC Read PC Read PC Read PCFetch Br-1 Fetch Br Fetch Br+1 Fetch Br+2 Fetch Br+3 Fetch TPC += 4 PC += 4 PC += 4 PC += 4 PC += 4 PC += 4D Br-1 Br Br+1 Br+2 annulX Br-1 Br Br+1 annulM Br-1 Br annulPC = BTAW Br-1 BrPipelined with PNT strategy4More on Control HazardsMore on Control HazardsBranch delay:Branch delay: the length of the control hazard the length of the control hazardWhat determines branch delay?What determines branch delay?We need to know that we have a branch instructionWe need to know that we have a branch instructionWe need to have the BTAWe need to have the BTAWe need to know the branch outcomeWe need to know the branch outcomeSo, we have to wait until we know all of these So, we have to wait until we know all of these quantitiesquantitiesAn older pipeline (DLX, HP2): An older pipeline (DLX, HP2): ……computes BTA in EXcomputes BTA in EX……computes branch outcome in EXcomputes branch outcome in EX……changes PC in MEMchanges PC in MEMTo reduce branch delay, these steps are moved To reduce branch delay, these steps are moved to earlier pipeline stages in MIPS (HP3):to earlier pipeline stages in MIPS (HP3):Can’t move up beyond ID (need to know it’s a branch Can’t move up beyond ID (need to know it’s a branch instruction)instruction)5IF/IDID/EX4sign Extend+<<2=Bus ABus BPCInstruction MemoryRegistersRtRdImmRtRsControl & Hazards+Reducing Branch DelaysReducing Branch DelaysExample:sub $10, $4, $8beq $10, $3, goadd $12, $2, $5...go: lw $4, 16($12)6Dealing with Branch DelaysDealing with Branch DelaysFour strategiesFour strategiesStallStallPredict Taken, variation A (PTA)Predict Taken, variation A (PTA)Predict Taken, variation B (PTB)Predict Taken, variation B (PTB)Predict Not Taken (PNT)Predict Not Taken (PNT)Consider a hypothetical 12-stage pipelineConsider a hypothetical 12-stage pipelineInstruction is fetched in stage 1 (IF)Instruction is fetched in stage 1 (IF)Opcode becomes known in stage 2 (ID)Opcode becomes known in stage 2 (ID)BTA becomes known in stage 4BTA becomes known in stage 4Branch outcome becomes known in stage 6Branch outcome becomes known in stage 6ParametersParametersPU, PT, PNT: penalties of unconditional branch, taken PU, PT, PNT: penalties of unconditional branch, taken branch, untaken branchbranch, untaken branchT: probability of branch being takenT: probability of branch being taken7Stall Strategy: 12-Stage PipelineStall Strategy: 12-Stage PipelineClock 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29Stage 1 1 2 2 2 2 2 3 4 5 6 7 8 9 9 9 9 9 uOpcode Stage 2 1 2 3 4 5 6 7 8 uStage 3 1 2 3 4 5 6 7 8 uBTA Stage 4 1 2 3 4 5 6 7 8 uStage 5 1 2 3 4 5 6 7 8 uBranch outcome Stage 6 1 2 3 4 5 6 7 8 uStage 7 1 2 3 4 5 6 7 8 uStage 8 1 2 3 4 5 6 7 8 uStage 9 1 2 3 4 5 6 7 8 uStage 10 1 2 3 4 5 6 7 8 uStage 11 1 2 3 4 5 6 7 8 uStage 12 1 2 3 4 5 6 7 8 uPipeline stalls on all branchesPipeline stalls on all branchesInstructions 1 and 8 are branchesInstructions 1 and 8 are branches1 is not taken, 8 is taken1 is not taken, 8 is takenOpcode determination in stage 2 stalls pipelineOpcode determination in stage 2 stalls pipelineBranch outcome determination in stage 6 restarts pipeline from IF or Branch outcome determination in stage 6 restarts pipeline from IF or IDIDBTA determination in stage 4 would restart pipeline from IF for jumpsBTA determination in stage 4 would restart pipeline from IF for jumpsPU = 3, PT = 5, PNT = 4PU = 3, PT = 5, PNT = 48Clock 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29Stage 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 uOpcode Stage 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 uStage 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 uBTA Stage 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 uStage 5 1 2 3 4 5 6 7 8 9 10 11 12 13 uBranch outcome Stage 6 1 2 3 4 5 6 7 8 9 10 11 12 uStage 7 1 2 3 4 5 6 7 8 9 10 11 12 uStage 8 1 2 3 4 5 6 7 8 9 10 11 12 uStage 9 1 2 3 4 5 6 7 8 9 10 11 12 uStage 10 1 2 3 4 5 6 7 8 9 10 11 12 uStage 11 1 2 3 4 5 6 7 8 9 10 11 12 uStage 12 1 2 3 4 5 6 7 8 9 10 11 12 uPipeline continues execution assuming that the branch will fall throughPipeline continues execution assuming that the branch will fall throughInstructions 1 and 12 are branchesInstructions 1 and 12 are branches1 is not taken, 12 is taken1 is not taken, 12 is takenBranch outcome determination in stage 6 Branch outcome determination in stage 6 restartsrestarts pipeline from IF for pipeline from IF for taken branches (taken branches (cancellingcancelling instructions already in pipeline) instructions already in pipeline)BTA determination in stage 4 would restart pipeline from IF for jumpsBTA determination in