Slide 1Last time in Lecture 3An Ideal PipelinePipelined MIPSLecture 3: Unpipelined Datapath for MIPSLecture 3: Hardwired Control TablePipelined Datapath“Iron Law” of Processor PerformanceCPI ExamplesTechnology Assumptions5-Stage Pipelined Execution5-Stage Pipelined Execution Resource Usage DiagramPipelined Execution: ALU InstructionsPipelined MIPS Datapath without jumpsInstructions interact with each other in pipelineResolving Structural HazardsData HazardsCS152 AdministriviaResolving Data Hazards (1)Feedback to Resolve HazardsInterlocks to resolve Data HazardsStalled Stages and Pipeline BubblesInterlock Control LogicInterlock Control Logic ignoring jumps & branchesSource & Destination RegistersDeriving the Stall SignalHazards due to Loads & StoresLoad & Store HazardsResolving Data Hazards (2)BypassingAdding a BypassThe Bypass Signal Deriving it from the Stall SignalBypass and Stall SignalsFully Bypassed DatapathResolving Data Hazards (3)Next Time: Control HazardsAcknowledgementsJanuary 28, 2010 CS152, Spring 2010CS 152 Computer Architecture and Engineering Lecture 4 - PipeliningKrste AsanovicElectrical Engineering and Computer SciencesUniversity of California at Berkeleyhttp://www.eecs.berkeley.edu/~krstehttp://inst.eecs.berkeley.edu/~cs152January 28, 2010 CS152, Spring 20102Last time in Lecture 3•Microcoding became less attractive as gap between RAM and ROM speeds reduced•Complex instruction sets difficult to pipeline, so difficult to increase performance as gate count grew•Iron-law explains architecture design space–Trade instructions/program, cycles/instruction, and time/cycle•Load-Store RISC ISAs designed for efficient pipelined implementations–Very similar to vertical microcode–Inspired by earlier Cray machines (more on these later)January 28, 2010 CS152, Spring 20103An Ideal Pipeline • All objects go through the same stages• No sharing of resources between any two stages• Propagation delay through all pipeline stages is equal• The scheduling of an object entering the pipeline is not affected by the objects in other stagesstage1stage2stage3stage4These conditions generally hold for industrial assembly lines, but instructions depend on each other!January 28, 2010 CS152, Spring 20104Pipelined MIPSTo pipeline MIPS:•First build MIPS without pipelining with CPI=1 •Next, add pipeline registers to reduce cycle time while maintaining CPI=1January 28, 2010 CS152, Spring 20105Lecture 3: Unpipelined Datapath for MIPS0x4RegWriteAddAddclkWBSrcMemWriteaddrwdatardataData MemoryweRegDstBSrcExtSelOpCodezOpSelclkzero?clkaddrinstInst.MemoryPCrd1GPRsrs1rs2wswdrd2weImmExtALUALUControl31PCSrcbrrindjabspc+4January 28, 2010 CS152, Spring 20106Opcode ExtSel BSrc OpSel MemW RegW WBSrc RegDst PCSrcALUALUiALUiuLWSWBEQZz=0BEQZz=1JJALJRJALRLecture 3: Hardwired Control TableBSrc = Reg / Imm WBSrc = ALU / Mem / PC RegDst = rt / rd / R31 PCSrc = pc+4 / br / rind / jabs* * * no yes rindPCR31rind* * * no no * *jabs* **noyes PC R31jabs***no no * *pc+4sExt16* 0? no no * *brsExt16* 0? no no * *pc+4sExt16Imm + yes no * *pc+4Imm Op no yes ALU rtpc+4* Reg Func no yes ALU rdsExt16Imm Op pc+4no yes ALU rtpc+4sExt16Imm + no yes Mem rtuExt16January 28, 2010 CS152, Spring 20107Pipelined DatapathClock period can be reduced by dividing the execution of an instruction into multiple cyclestC > max {tIM, tRF, tALU, tDM, tRW} ( = tDM probably) However, CPI will increase unless instructions are pipelinedwrite-backphasefetchphaseexecutephasedecode & Reg-fetchphasememoryphaseaddrwdatardataDataMemoryweALUImmExt0x4AddaddrrdataInst.Memoryrd1GPRsrs1rs2wswdrd2weIRPCJanuary 28, 2010 CS152, Spring 20108“Iron Law” of Processor Performance Time = Instructions Cycles Time Program Program * Instruction * Cycle–Instructions per program depends on source code, compiler technology, and ISA–Cycles per instructions (CPI) depends upon the ISA and the microarchitecture–Time per cycle depends upon the microarchitecture and the base technologyMicroarchitecture CPI cycle timeMicrocoded >1 shortSingle-cycle unpipelined 1 longPipelined 1 shortLecture 2Lecture 3Lecture 4January 28, 2010 CS152, Spring 2010CPI Examples9TimeInst 37 cyclesInst 1 Inst 25 cycles 10 cyclesMicrocoded machine3 instructions, 22 cycles, CPI=7.33Unpipelined machine3 instructions, 3 cycles, CPI=1Inst 1 Inst 2 Inst 3Pipelined machine3 instructions, 3 cycles, CPI=1Inst 1Inst 2Inst 3January 28, 2010 CS152, Spring 201010Technology AssumptionsThus, the following timing assumption is reasonable• A small amount of very fast memory (caches) backed up by a large, slower memory • Fast ALU (at least for integers) • Multiported Register files (slower!)tIM tRF tALU tDM tRWA 5-stage pipeline will be the focus of our detailed design- some commercial designs have over 30 pipeline stages to do an integer add!January 28, 2010 CS152, Spring 2010115-Stage Pipelined Executiontime t0 t1 t2 t3 t4 t5 t6 t7 . . . .instruction1IF1ID1EX1MA1WB1instruction2 IF2ID2EX2MA2WB2instruction3 IF3ID3EX3MA3WB3instruction4 IF4ID4EX4MA4WB4instruction5 IF5ID5EX5MA5WB5Write-Back (WB)I-Fetch (IF)Execute (EX)Decode, Reg. Fetch (ID)Memory (MA)addrwdatardataDataMemoryweALUImmExt0x4AddaddrrdataInst.Memoryrd1GPRsrs1rs2wswdrd2weIRPCJanuary 28, 2010 CS152, Spring 2010125-Stage Pipelined ExecutionResource Usage Diagramtime t0 t1 t2 t3 t4 t5 t6 t7 . . . .IF I1I2I3I4I5ID I1I2I3I4I5EX I1I2I3I4I5MA I1I2I3I4I5WB I1I2I3I4I5ResourcesWrite-Back (WB)I-Fetch (IF)Execute (EX)Decode, Reg. Fetch (ID)Memory (MA)addrwdatardataDataMemoryweALUImmExt0x4AddaddrrdataInst.Memoryrd1GPRsrs1rs2wswdrd2weIRPCJanuary 28, 2010 CS152, Spring 201013Pipelined Execution:ALU InstructionsIRIRIR31PCABYRMD1MD2addrinstInstMemory0x4AddIRImmExtALUrd1GPRsrs1rs2wswdrd2wewdataaddrwdatardataData MemoryweNot quite correct!We need an Instruction Reg (IR) for each stageJanuary 28, 2010 CS152, Spring 201014Pipelined MIPS Datapathwithout jumpsIRIRIR31PCABYRMD1MD2addrinstInstMemory0x4AddIRImmExtALUrd1GPRsrs1rs2wswdrd2weData MemorywdataaddrwdatardataweOpSelExtSel BSrcWBSrcMemWriteRegDstRegWriteF D E M WControl Points Need to Be ConnectedJanuary 28, 2010 CS152, Spring 201015Instructions interact with each other in pipeline•An instruction in the pipeline may need a resource being used by another instruction in the pipeline structural hazard•An instruction may depend on something produced by an earlier instruction–Dependence may be for a data value
View Full Document