CS 61C L18 Pipelining I (1)A Carle, Summer 2005 © UCBinst.eecs.berkeley.edu/~cs61c/su05CS61C : Machine StructuresLecture #18: Pipelining 12005-07-20Andy CarleCS 61C L18 Pipelining I (2)A Carle, Summer 2005 © UCBAn Abstract View of the Critical PathCritical Path (Load Operation) = Delay clock through PC (FFs) +Instruction Memory’s Access Time +Register File’s Access Time +ALU to Perform a 32-bit Add +Data Memory Access Time +Stable Time for Register File WriteClk5Rw Ra Rb32 32-bitRegistersRdALUClkData InDataAddressIdealDataMemoryInstructionInstructionAddressIdealInstructionMemoryClkPC5Rs5Rt16Imm32323232ABNext Address• This affects how much you can overclockyour PC!CS 61C L18 Pipelining I (3)A Carle, Summer 2005 © UCBImprove Critical Path Î Improve Clock•“Critical path” (longest path through logic) determines length of clock period•To reduce clock period Î decrease path through CL by inserting StateClk............CS 61C L18 Pipelining I (4)A Carle, Summer 2005 © UCB°5 steps to design a processor• 1. Analyze instruction set => datapath requirements• 2. Select set of datapath components & establish clock methodology• 3. Assemble datapath meeting the requirements• 4. Analyze implementation of each instruction to determine setting of control points that effects the register transfer.• 5. Assemble the control logic°Control is the hard part°MIPS makes that easier• Instructions same size• Source registers always in same place• Immediates same size, location• Operations always on registers/immediatesReview: Single cycle datapathControlDatapathMemoryProcessorInputOutputCS 61C L18 Pipelining I (5)A Carle, Summer 2005 © UCBReview Datapath (1/3)•Datapath is the hardware that performs operations necessary to execute programs.•Control instructs datapath on what to do next.•Datapath needs:• access to storage (general purpose registers and memory)• computational ability (ALU)• helper hardware (local registers and PC)CS 61C L18 Pipelining I (6)A Carle, Summer 2005 © UCBReview Datapath (2/3)•Five stages of datapath (executing an instruction):1. Instruction Fetch (Increment PC)2. Instruction Decode (Read Registers)3. ALU (Computation)4. Memory Access5. Write to Registers•ALL instructions must go through ALL five stages.CS 61C L18 Pipelining I (7)A Carle, Summer 2005 © UCBReview Datapath (3/3)PCinstructionmemory+4rtrsrdregistersALUDatamemoryimm1. InstructionFetch2. Decode/RegisterRead3. Execute 4. Memory5. WriteBackCS 61C L18 Pipelining I (8)A Carle, Summer 2005 © UCBGotta Do Laundry° Ann, Brian, Cathy, Dave each have one load of clothes to wash, dry, fold, and put awayA B C D° Dryer takes 30 minutes° “Folder” takes 30 minutes° “Stasher” takes 30 minutes to put clothes into drawers° Washer takes 30 minutesCS 61C L18 Pipelining I (9)A Carle, Summer 2005 © UCBSequential Laundry•Sequential laundry takes 8 hours for 4 loadsTaskOrderBCDA30Time3030 3030 30 3030 3030 3030 3030 30306 PM78910111212 AMCS 61C L18 Pipelining I (10)A Carle, Summer 2005 © UCBPipelined Laundry•Pipelined laundry takes 3.5 hours for 4 loads!TaskOrderBCDA122 AM6 PM78910111Time303030 303030 30CS 61C L18 Pipelining I (11)A Carle, Summer 2005 © UCBGeneral Definitions•Latency: time to completely execute a certain task• for example, time to read a sector from disk is disk access time or disk latency• Instruction latency is time from when instruction starts to time when it finishes.•Throughput: amount of work that can be done over a period of timeCS 61C L18 Pipelining I (12)A Carle, Summer 2005 © UCBPipelining Lessons (0/2)•Terminology:• Issue: When instruction goes into first stage of pipe.• Commit: when instruction finishes last stage6 PM789TimeBCDA3030 30 303030 30TaskOrderCS 61C L18 Pipelining I (13)A Carle, Summer 2005 © UCBPipelining Lessons (1/2)• Pipelining doesn’t help latencyof single task, it helps throughputof entire workload• Multipletasks operating simultaneously using different resources• Potential speedup = Number pipe stages• Time to “fill” pipeline and time to “drain” it reduces speedup:2.3X v. 4X in this example6 PM789TimeBCDA3030 30 303030 30TaskOrderCS 61C L18 Pipelining I (14)A Carle, Summer 2005 © UCBPipelining Lessons (2/2)•Suppose new Washer takes 20 minutes, new Stasher takes 20 minutes. How much faster is pipeline?•Pipeline rate limited by slowestpipeline stage•Unbalanced lengths of pipe stages also reduces speedup6 PM789TimeBCDA3030 30 303030 30TaskOrderCS 61C L18 Pipelining I (15)A Carle, Summer 2005 © UCBSteps in Executing MIPS1) IFetch: Fetch Instruction, Increment PC2) DecodeInstruction, Read Registers3) Execute:Mem-ref: Calculate AddressArith-log: Perform Operation4) Memory: Load: Read Data from MemoryStore: Write Data to Memory5) Write Back: Write Data to RegisterCS 61C L18 Pipelining I (16)A Carle, Summer 2005 © UCBPipelined Execution Representation•Every instruction must take same number of steps, also called pipeline “stages”, so some will go idle sometimesIFtch Dcd Exec Mem WBIFtch Dcd Exec Mem WBIFtch Dcd Exec Mem WBIFtch Dcd Exec Mem WBIFtch Dcd Exec Mem WBIFtch Dcd Exec Mem WBTimeCS 61C L18 Pipelining I (17)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 L18 Pipelining I (18)A Carle, Summer 2005 © UCBGraphical Pipeline RepresentationInstr.OrderLoadAddStoreSubOrI$Time (clock cycles)I$ALURegRegI$D$ALUALURegD$RegI$D$RegALURegRegRegD$RegD$ALU(In Reg, right half highlight read, left half write)RegI$CS 61C L18 Pipelining I (19)A Carle, Summer 2005 © UCBExample•Suppose 2 ns for memory access, 2 ns for ALU operation, and 1 ns for register file read or write; compute instruction throughput•Nonpipelined Execution:• lw : IF + Read Reg + ALU + Memory + Write Reg = 2 + 1 + 2 + 2 + 1 = 8 ns• add: IF + Read Reg + ALU + Write Reg= 2 + 1 + 2 + 1 = 6 ns•Pipelined Execution:• Max(IF,Read Reg,ALU,Memory,Write Reg) = 2 nsCS 61C L18 Pipelining I (20)A Carle, Summer 2005 © UCBExample•Suppose 2 ns for memory access, 2 ns for ALU operation, and 1 ns for register file read or write; compute instruction latency•Nonpipelined Execution:• lw : IF + Read Reg + ALU + Memory + Write Reg = 2 + 1 + 2 + 2 + 1 = 8 ns• add: IF + Read Reg + ALU + Write Reg= 2 + 1 + 2 + 1 =
View Full Document
Unlocking...