COMP 206: Computer Architecture and ImplementationOutlineHow About Control Signals?Pipeline ControlA More Extensive Pipelining ExamplePipelining Example: End of Cycle 4CPU Designs: SummarySingle Cycle vs. Multiple Cycle vs. PipelinedPipelining: Notation, Terminology etc.Notations for Describing PipelinesBasic TermsSpeedup & Throughput of a PipelinePipeline Hazards: Structural HazardExample: Unified I- and D-MemoryResolving Structural HazardsExample: Cost of Structural HazardData Hazard: SetupData Hazard: DefinitionWhy Data Hazards OccurData Dependence and HazardsMore on HazardsThe Precedence RelationExample of Precedence RelationData Hazard: Effect on PipeliningValue Forwarding/BypassingForwarding: Example 2Forwarding & Stalling: Example 3Forwarding & Stalling: Example 4Load Data Forwarding1COMP 206:COMP 206:Computer Architecture and Computer Architecture and ImplementationImplementationMontek SinghMontek SinghMon, Sep 19, 2005Mon, Sep 19, 2005Topic: Topic: Pipelining (Intermediate Concepts)Pipelining (Intermediate Concepts)2OutlineOutlinePipelining basics (contd.)Pipelining basics (contd.)Pipelining examplePipelining examplePipelining notation and terminologyPipelining notation and terminologyHazardsHazardsStructural hazardsStructural hazardsData hazardsData hazardsHazard resolutionHazard resolutionReading: Appendix A (HP3)3MemWrIF/ID:ID/Ex RegisterEx/Mem: Load’s AddressMem/Wr RegisterPCDataMemWADiRADoIUnitAIRFileDiRaRbRwRegWrExtOp=1ExecUnitbusAbusBImm16ALUOp=AddALUSrc=1Mux10MemtoReg10RegDst=0RtRdImm16PC+4PC+4RsRtPC+4ZeroBranch10Ifetch Reg/Dec Exec MemWrHow About Control Signals?How About Control Signals?Key Observation: Key Observation: Control Signals at Stage N = Control Signals at Stage N = Func (Instr. at Stage N) for N = Exec, Mem, or Func (Instr. at Stage N) for N = Exec, Mem, or WrB.WrB. Control Signals at Exec Stage = Func(Load’s Exec) Control Signals at Exec Stage = Func(Load’s Exec) What about Ifetch and Reg/Dec?What about Ifetch and Reg/Dec?4IF/ID RegisterID/Ex RegisterEx/Mem RegisterMem/Wr RegisterReg/Dec Exec MemExtOpALUOpRegDstALUSrcBranchMemWrMemtoRegRegWrMainControlExtOpALUOpRegDstALUSrcMemtoRegRegWrMemtoRegRegWrMemtoRegRegWrBranchMemWrBranchMemWrWrBClk Clk Clk ClkPipeline ControlPipeline Control““Main Control”: generates control signals during Main Control”: generates control signals during Reg/DecReg/DecControl signals for Exec (ExtOp, ALUSrc, ...) are used 1 Control signals for Exec (ExtOp, ALUSrc, ...) are used 1 cycle latercycle laterControl signals for Mem (MemWr, Branch) are used 2 cycles Control signals for Mem (MemWr, Branch) are used 2 cycles laterlaterControl signals for WrB (MemtoReg,MemWr) are used 3 Control signals for WrB (MemtoReg,MemWr) are used 3 cycles latercycles later5A More Extensive Pipelining A More Extensive Pipelining ExampleExampleEnd of Cycle 4: End of Cycle 4: Load’s Mem, R-type’s Exec, Store’s Reg, Beq’s Load’s Mem, R-type’s Exec, Store’s Reg, Beq’s IfetchIfetchEnd of Cycle 5: End of Cycle 5: Load’s WrB, R-type’s Mem, Store’s Exec, Beq’s Load’s WrB, R-type’s Mem, Store’s Exec, Beq’s RegRegEnd of Cycle 6: End of Cycle 6: R-type’s WrB, Store’s Mem, Beq’s ExecR-type’s WrB, Store’s Mem, Beq’s ExecEnd of Cycle 7: End of Cycle 7: Store’s WrB, Beq’s MemStore’s WrB, Beq’s MemClockCycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8Ifetch Reg/Dec Exec Mem WrB0: LoadIfetch Reg/Dec Exec Mem WrB4: R-typeIfetch Reg/Dec Exec Mem WrB8: StoreIfetch Reg/Dec Exec Mem WrB12: Beq (target is 1000)End ofCycle 4End ofCycle 5End ofCycle 6End ofCycle 76IF/ID: Beq InstructionID/Ex: Store’s busA & BEx/Mem: R-type’s ResultMem/Wr: Load’s DoutPC = 16DataMemWADiRA DoIUnitAIRFileDiRaRbRwRegWr=0ExtOp=xExecUnitbusAbusBImm16ALUOp=R-typeALUSrc=0Mux10MemtoReg=x10RegDst=1RtRdImm16PC+4PC+4RsRtPC+4ZeroBranch=01012: Beq’s Ifet8: Store’s Reg 4: R-type’s Exec 0: Load’s MemClkMemWr=0ClkPipelining Example: End of Cycle Pipelining Example: End of Cycle 440: Load’s Mem 4: R-type’s Exec 8: Store’s Reg 12: Beq’s Ifetch0: Load’s Mem 4: R-type’s Exec 8: Store’s Reg 12: Beq’s Ifetch10CPU Designs: SummaryCPU Designs: SummaryDisadvantages of the Single Cycle ProcessorDisadvantages of the Single Cycle ProcessorLong cycle timeLong cycle timeCycle time wasted for the faster instructionsCycle time wasted for the faster instructionsMultiple Clock Cycle ProcessorMultiple Clock Cycle ProcessorDivide the instructions into smaller stepsDivide the instructions into smaller stepsExecute each step (instead of the entire instruction) in 1 Execute each step (instead of the entire instruction) in 1 cyclecyclePipelined ProcessorPipelined ProcessorNatural enhancement of the multiple clock cycle processorNatural enhancement of the multiple clock cycle processorEach functional unit used only once per instructionEach functional unit used only once per instructionIf an instruction is going to use a functional unit:If an instruction is going to use a functional unit:it must use it at the same stage as all other instructionsit must use it at the same stage as all other instructionsPipeline Control:Pipeline Control:each stage’s control signal depends ONLY on the instruction that each stage’s control signal depends ONLY on the instruction that is currently in that stageis currently in that stage11WrClkCycle 1Multiple Cycle Implementation:Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10Load Ifetch Reg Exec Mem WrIfetch Reg Exec MemLoad StorePipelined Implementation:Ifetch Reg Exec Mem WrStoreClkSingle Cycle Implementation:Load Store WasteIfetchR-typeIfetch Reg Exec Mem WrR-typeCycle 1 Cycle 2Ifetch Reg Exec MemSingle Cycle vs. Multiple Cycle vs. Single Cycle vs. Multiple Cycle vs. PipelinedPipelined12Pipelining: Notation, Terminology Pipelining: Notation, Terminology etc.etc.TimeTimeDiscrete time stepsDiscrete time stepsRepresented as 1, 2, 3, …Represented as 1, 2, 3, …SpaceSpacePipe stages or segments (things that do processing)Pipe stages or segments (things that do processing)Represented as P, Q, R, S (or F, D, X, M, W for the MIPS Represented as P, Q, R, S (or F, D, X, M, W for the MIPS pipeline)pipeline)OperandsOperandsInstructions or data itemsInstructions or data itemsThings that flow through, and are processed by, the