CS 61C L19 Pipelining II (1)A Carle, Summer 2005 © UCBinst.eecs.berkeley.edu/~cs61c/su05CS61C : Machine StructuresLecture #19: Pipelining II2005-07-21Andy CarleCS 61C L19 Pipelining II (2)A Carle, Summer 2005 © UCBReview: Datapath for MIPS•Use datapath figure to represent pipelineIFtch Dcd Exec Mem WBALUI$RegD$ RegPCinstructionmemory+4rtrsrdregistersALUDatamemoryimm1. InstructionFetch2. Decode/Register Read3. Execute 4. Memory5. WriteBackCS 61C L19 Pipelining II (3)A Carle, Summer 2005 © UCBReview: Problems for Computers•Limits to pipelining: Hazardsprevent next instruction from executing during its designated clock cycle• Structural hazards: HW cannot support this combination of instructions (single person to fold and put clothes away)• Control hazards: Pipelining of branches & other instructions stallthe pipeline until the hazard; “bubbles” in the pipeline• Data hazards: Instruction depends on result of prior instruction still in the pipeline (missing sock)CS 61C L19 Pipelining II (4)A Carle, Summer 2005 © UCBReview: C.f. Branch Delay vs. Load Delay•Load Delay occurs only if necessary (dependent instructions).•Branch Delay always happens (part of the ISA).•Why not have Branch Delay interlocked?• Answer: Interlocks only work if you can detect hazard ahead of time. By the time we detect a branch, we already need its value … hence no interlock is possible!CS 61C L19 Pipelining II (5)A Carle, Summer 2005 © UCBFYI: Historical Trivia•First MIPS design did not interlock and stall on load-use data hazard•Real reason for name behind MIPS: Microprocessor without Interlocked Pipeline Stages• Word Play on acronym for Millions of Instructions Per Second, also called MIPS• Load/Use Î Wrong Answer!CS 61C L19 Pipelining II (6)A Carle, Summer 2005 © UCBOutline•Pipeline Control•Forwarding Control•Hazard ControlCS 61C L19 Pipelining II (7)A Carle, Summer 2005 © UCBPiped Proc So Far …CS 61C L19 Pipelining II (8)A Carle, Summer 2005 © UCBNew Representation: Regs more explicitExecReg. FileDataMemABSRegFilePCNext PCIRInst. MemDMSIF/DEDE/EXEX/MEME/WBIF/DE.Ir = InstructionDE/EX.A = BusA out of RegEX/ME.S = AluOutEX/ME.D = Bus B pass-through for swME/WB.S = ALuOut pass-throughME/WB.M = Mem Result from lwCS 61C L19 Pipelining II (9)A Carle, Summer 2005 © UCBNew Representation: Regs more explicitExecReg. FileDataMemABSRegFilePCNext PCIRInst. MemDMSIF/DEDE/EXEX/MEME/WB/ What’s Missing???CS 61C L19 Pipelining II (10)A Carle, Summer 2005 © UCBPipelined Processor (almost) for slidesExecReg. FileMemAccessDataMemABSMRegFileEqualPCNext PCIRInst. MemValidIRexDcd CtrlIRmemEx CtrlIRwbMem CtrlWB CtrlDIdea: Parallel Piped Control …CS 61C L19 Pipelining II (11)A Carle, Summer 2005 © UCBPipelined ControlIR <- Mem[PC]; PC <– PC+4;A <- R[rs]; B<– R[rt]S <– A + B;R[rd] <– S;S <– A + SX;M <– Mem[S]R[rd] <– M;S <– A or ZX;R[rt] <– S;S <– A + SX;Mem[S] <- BIf CondPC < PC+SX;ExecReg. FileMemAccessDataMemABSRegFileEqualPCNext PCIRInst. MemDMCS 61C L19 Pipelining II (12)A Carle, Summer 2005 © UCBData Stationary Control• The Main Control generates the control signals during Reg/Dec• Control signals for Exec (ExtOp, ALUSrc, ...) are used 1 cycle later• Control signals for Mem (MemWr Branch) are used 2 cycles later• Control signals for Wr (MemtoReg MemWr) are used 3 cycles laterIF/ID RegisterID/Ex RegisterEx/Mem RegisterMem/Wr RegisterReg/Dec Exec MemExtOpALUOpRegDstALUSrcBranchMemWrMemtoRegRegWrMainControlExtOpALUOpRegDstALUSrcMemtoRegRegWrMemtoRegRegWrMemtoRegRegWrBranchMemWrBranchMemWrWrCS 61C L19 Pipelining II (13)A Carle, Summer 2005 © UCBLet’s Try it Out10 lw r1, 36(r2)14 addI r2, r2, 320 sub r3, r4, r524 beq r6, r7, 10028 ori r8, r9, 1732 add r10, r11, r12100 and r13, r14, 15CS 61C L19 Pipelining II (14)A Carle, Summer 2005 © UCBStart: Fetch 10ExecReg. FileMemAccessDataMemABSRegFileIRInst. MemDDecodeMemCtrlWB CtrlMrs rtim10 lw r1, 36(r2)14 addI r2, r2, 320 sub r3, r4, r524 beq r6, r7, 10030 ori r8, r9, 1734 add r10, r11, r12100 and r13, r14, 15IFPCNext PC10=n n n nCS 61C L19 Pipelining II (15)A Carle, Summer 2005 © UCBFetch 14, Decode 10ExecReg. FileMemAccessDataMemABSRegFileIRInst. MemDDecodeMemCtrlWB CtrlM2 rtim10 lw r1, 36(r2)14 addI r2, r2, 320 sub r3, r4, r524 beq r6, r7, 10030 ori r8, r9, 1734 add r10, r11, r12100 and r13, r14, 15lw r1, 36(r2)IDIFPCNext PC14=n n nCS 61C L19 Pipelining II (16)A Carle, Summer 2005 © UCBFetch 20, Decode 14, Exec 10ExecReg. FileMemAccessDataMemr2BSRegFileIRInst. MemDDecodeMemCtrlWB CtrlM2 rt3610 lw r1, 36(r2)14 addI r2, r2, 320 sub r3, r4, r524 beq r6, r7, 10030 ori r8, r9, 1734 add r10, r11, r12100 and r13, r14, 15lw r1addI r2, r2, 3IDIFEXPCNext PC20=nnCS 61C L19 Pipelining II (17)A Carle, Summer 2005 © UCBFetch 24, Decode 20, Exec 14, Mem 10ExecReg. FileMemAccessDataMemr2Br2+36RegFileIRInst. MemDDecodeMemCtrlWB CtrlM45310 lw r1, 36(r2)14 addI r2, r2, 320 sub r3, r4, r524 beq r6, r7, 10030 ori r8, r9, 1734 add r10, r11, r12100 and r13, r14, 15lw r1sub r3, r4, r5addI r2, r2, 3IDIFEXM PCNext PC24=nCS 61C L19 Pipelining II (18)A Carle, Summer 2005 © UCBFetch 30, Dcd 24, Ex 20, Mem 14, WB 10ExecReg. FileMemAccessDataMemr4r5r2+3RegFileIRInst. MemDDecodeMemCtrlWB CtrlM[r2+36]6710 lw r1, 36(r2)14 addI r2, r2, 320 sub r3, r4, r524 beq r6, r7, 10030 ori r8, r9, 1734 add r10, r11, r12100 and r13, r14, 15lw r1beq r6, r7 100addI r2sub r3IDIFEXM WB PCNext PC30=Note Delayed Branch: always execute ori after beqCS 61C L19 Pipelining II (19)A Carle, Summer 2005 © UCBFetch 100, Dcd 30, Ex 24, Mem 20, WB 14ExecReg. FileMemAccessDataMemr6r7r2+3RegFileIRInst. MemDDecodeMemCtrlWB Ctrlr1=M[r2+35]9xx10 lw r1, 36(r2)14 addI r2, r2, 320 sub r3, r4, r524 beq r6, r7, 10030 ori r8, r9, 1734 add r10, r11, r12100 and r13, r14, 15beqaddI r2sub r3r4-r5100ori r8, r9 17IDIFEXM WB PCNext PC100=CS 61C L19 Pipelining II (20)A Carle, Summer 2005 © UCB? ? ? ? ExecReg. FileMemAccessDataMemABSMRegFileEqualPCNext PCIRInst. MemValidIRexDcd CtrlIRmemEx CtrlIRwbMem CtrlWB CtrlD• Remember: means triggered on edge.• What is wrong here?CS 61C L19 Pipelining II (21)A Carle, Summer 2005 © UCBDouble-Clocked SignalsExecReg. FileMemAccessDataMemABSMRegFileEqualPCNext PCIRInst. MemValidIRexDcd CtrlIRmemEx CtrlIRwbMem CtrlWB CtrlD• Some signals are double clocked!• In general: Inputs to edge components are their own pipeline regs• Watch out for stalls and such!CS 61C L19 Pipelining II (22)A Carle, Summer 2005 ©
View Full Document
Unlocking...