1CS 365 1PipeliningCS 365 Lecture 12Prof. Yih HuangCS 365 2Traditional Execution1 2 3 4 1 2 3 4 5 1 2 3addldbeq2CS 365 3Pipelined Execution1 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 5CS 365 4Basic Ideas Do not wait for an instruction to complete to start the next.– Start the Cycle 0 of the next instruction when the previous one enters Cycle 1. Instruction executions are overlapped. Pipelining increases instruction throughput, as opposed to decreasing the execution time of individual instructions.3CS 365 5Easier Said Than Done? In every cycle, activities of all five stages take place. Many problems arises with overlapped executions.– Structural hazards– Control hazards– Data hazardsCS 365 6Pipeline Hazards I Structural Hazards– The data path cannot support the combination of instructions that we want to execute in the same cycle Consider what happens when an R-type instruction is followed by a BEQ?addbeqIF RR + RWIF RR−4CS 365 7Summary of MIPS LiteInstruction ExecutionsStep nameAction for R-type instructionsAction for memory-reference instructionsAction for branchesAction for jumpsInstruction fetch IR = Memory[PC]PC = PC + 4Instruction A = Reg [IR[25-21]]decode/register fetch B = Reg [IR[20-16]]ALUOut = PC + (sign-extend (IR[15-0]) << 2)Execution, address ALUOut = A op B ALUOut = A + sign-extend if (A ==B) then PC = PC [31-28] IIcomputation, branch/ (IR[15-0]) PC = ALUOut (IR[25-0]<<2)jump completionMemory access or R-type Reg [IR[15-11]] = Load: MDR = Memory[ALUOut]completion ALUOut orStore: Memory [ALUOut] = BMemory read completionLoad: Reg[IR[20-16]] = MDRCS 365 8Resource Conflicts on the Multicycle DatapathS h iftle ft 2M e m to R e gIo rD M e m R e a d M e m W r iteP CM e m o ryM e m D a taW rited at aMux01R e g is te rsW ritere gi ste rW rited at aR e a dda t a 1R e add ata 2R e adre gi ste r 1R e adre gi ste r 2In s tr uc tio n[1 5 – 1 1 ]Mux01Mux014A L U O pA L U S rc BR e g D st R e gW r iteIn st r u c t io n[1 5 – 0 ]In s tru c tio n [5 – 0 ]S ig nex t en d3 216In s tru ctio n[2 5 – 2 1 ]In s tru ctio n[2 0 – 1 6 ]In s tru ctio n[1 5 – 0 ]In s tru c tio nre g is ter1Mux032A L Uc o ntro lMux01A L Ur e s ul tA L UA L US rc AZ e roABA L U O u tIR W r iteA d d r e ssM e m o ryd a tare g is ter5CS 365 9Pipeline Hazards II Control Hazards: When we decide to branch, other instructions are in the pipeline!beqaddsubTarget: ldIF RR−IF RR + RWIF RR + RWIF RR + MR RWWhich one is the next?CS 365 10Pipeline Hazards III Data Hazards: (data dependencies) an instruction depends on the result of a previous instruction still in the pipeline.Add r1, r2, r3Sub r4,r1, r10IF RR + RWIF RR−Reading new value of r1, not available yetWriting new value of r16CS 365 11Lessons To achieve pipelining and avoid hazards, we need to redesign – the datapath and – instruction execution steps, CS 365 12Pipeline StagesWrite to RtWrite to RdStage 5:RW/WBSet PC accordinglyWritememoryRead memoryStage 4:DMSet PC to ImmdCalculate PC + ImmdCompare RS and RTCalculateRS+ImmdCalculateRS+ImmdRS op RTStage 3:EX(use ALU)Read Reg[rs] and Reg[rt]Stage 2: RRIR ← Mem[PC]PC ← PC + 4Stage 1:IFJBEQSTLDR-Type7CS 365 13Graphically Representing PipelinesI M R e g D M R e gI M R e g D M R e gC C 1 C C 2 C C 3 C C 4 C C 5 C C 6T im e ( in c lo c k c y c le s )lw $ 1 0 , 2 0 ( $ 1 )P r o g r a me x e c u t io no r d e r( i n i n s t r u c t i o n s )s u b $ 1 1 , $ 2 , $ 3A L UA L UCS 365 14Solving Structural Hazards: Pipelined DatapathIn s tr u ct io nm e m o ryA d d r e s s43 20A d dA d dre s u ltS h if tle ft 2I n s t ru c t ionIF /I D E X / M E M M E M /W BMux01A d dP C0W r ited a taMux1R e g i ste r sR e a dd a t a 1R e a dd a t a 2R e a dre g is t er 1R e a dre g is t er 21 6S ig ne x te n dW r itere g is t erW r ited a taR e a dd a t a1A L Ure s u ltMuxA L UZ e r oID /E XD a tam e m o ryA d d re s s8CS 365 15Discussions Make sure you understand why two extra adders are added. Is the assumption of using separate instruction and data memory reasonable?CS 365 16Consider Control HazardIF RR EX DM RWbeqIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWTarget: When is thedecisionmade?9CS 365 17Solution 1: Stalling The PipelineIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWORDecision is inCS 365 18Solution 2: Branch Prediction Make a guess about the branch decision and start execute the guessed path before the decision is in (aka speculative execution). If guess was wrong, abandon those in the pipeline and jump to the right target. Branch Prediction Strategies– Predict branch fails– Predict branch succeeds– Look into history10CS 365 19Predict Branch Fails We guess the branch will fail. That is, the next IF will fetch the next sequential execution. If guess is right, just proceed. If guess is wrong, abandon sequential instructions and fetch the instruction from the target address. CS 365 20Predict branch fails: Guess Is RightIF RR EX DM RWbeqIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWDecision is in;Do not branchFollowinginstructionsIF RR EX DM RW11CS 365 21Predict branch fails: Guess Is WrongIF RR EX DM RWbeqIF RR EXIF RRIFIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWDecision is in: Do branchFollowinginstructionsTargetinstructionsCS 365 22Discussion Notice that programmers are not aware of branch predictions; right or wrong guesses affect only performance. Delayed Branches: Make it official that CPU always executes the instr following a branch. The branch determines the next nextinstruction.– Notice the programmer awareness12CS 365 23ExampleBEQ r1, r2, targetadd r10, r11, r12add r20, r21, r22sub r30, r10, r20sub r30, r10, r20Target: Delay slot,executed regardless ofthe branch decisionCS 365 24Delayed Branch with Wrong GuessIF RR EX DM RWbeqIF RR EXIF RRIFIF RR EX DM RWIF RR EX DM RWIF RR EX DM RWDecision is in: Do branchFollowinginstructionsTargetinstructionsDM …