PowerPoint PresentationReview: Single cycle datapathReview Datapath (1/3)Review Datapath (2/3)Review Datapath (3/3)Gotta Do LaundrySequential LaundryPipelined LaundryGeneral DefinitionsPipelining Lessons (1/2)Pipelining Lessons (2/2)Steps in Executing MIPSPipelined Execution RepresentationReview: Datapath for MIPSGraphical Pipeline RepresentationExamplePipeline Hazard: Matching socks in later loadAdministriviaProblems for ComputersStructural Hazard #1: Single Memory (1/2)Structural Hazard #1: Single Memory (2/2)Structural Hazard #2: Registers (1/2)Structural Hazard #2: Registers (2/2)Things to RememberCS 61C L30 Introduction to Pipelined Execution (1)Garcia, Fall 2004 © UCBLecturer PSOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61c CS61C : Machine Structures Lecture 30 – Introduction to Pipelined Execution 2004-11-08The Incredibles!theincredibles.comPixar does it again! Our neighbors have a hit with The Incredibles!CS 61C L30 Introduction to Pipelined Execution (2)Garcia, Fall 2004 © 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 L30 Introduction to Pipelined Execution (3)Garcia, Fall 2004 © 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 L30 Introduction to Pipelined Execution (4)Garcia, Fall 2004 © 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 L30 Introduction to Pipelined Execution (5)Garcia, Fall 2004 © UCBReview Datapath (3/3)PCinstructionmemory+4rtrsrdregistersALUDatamemoryimm1. InstructionFetch2. Decode/ RegisterRead3. Execute 4. Memory5. WriteBackCS 61C L30 Introduction to Pipelined Execution (6)Garcia, Fall 2004 © 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 L30 Introduction to Pipelined Execution (7)Garcia, Fall 2004 © UCBSequential Laundry•Sequential laundry takes 8 hours for 4 loadsTaskOrderBCDA30Time3030 3030 30 3030 3030 3030 3030 30306 PM78910111212 AMCS 61C L30 Introduction to Pipelined Execution (8)Garcia, Fall 2004 © UCBPipelined Laundry•Pipelined laundry takes 3.5 hours for 4 loads! TaskOrderBCDA122 AM6 PM78910111Time303030 30303030CS 61C L30 Introduction to Pipelined Execution (9)Garcia, Fall 2004 © 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•Throughput: amount of work that can be done over a period of timeCS 61C L30 Introduction to Pipelined Execution (10)Garcia, Fall 2004 © UCBPipelining Lessons (1/2)•Pipelining doesn’t help latency of single task, it helps throughput of entire workload•Multiple tasks 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 PM7 8 9TimeBCDA303030 30303030TaskOrderCS 61C L30 Introduction to Pipelined Execution (11)Garcia, Fall 2004 © UCBPipelining Lessons (2/2)•Suppose new Washer takes 20 minutes, new Stasher takes 20 minutes. How much faster is pipeline?•Pipeline rate limited by slowest pipeline stage•Unbalanced lengths of pipe stages also reduces speedup6 PM7 8 9TimeBCDA303030 30303030TaskOrderCS 61C L30 Introduction to Pipelined Execution (12)Garcia, Fall 2004 © UCBSteps in Executing MIPS1) IFetch: Fetch Instruction, Increment PC2) Decode Instruction, Read Registers3) Execute: Mem-ref: Calculate Address Arith-log: Perform Operation4) Memory: Load: Read Data from Memory Store: Write Data to Memory5) Write Back: Write Data to RegisterCS 61C L30 Introduction to Pipelined Execution (13)Garcia, Fall 2004 © 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 L30 Introduction to Pipelined Execution (14)Garcia, Fall 2004 © UCBReview: Datapath for MIPS•Use datapath figure to represent pipelineIFtch Dcd Exec Mem WBALU I$Reg D$ RegPCinstructionmemory+4rtrsrdregistersALUDatamemoryimm1. InstructionFetch2. Decode/ Register Read3. Execute 4. Memory5. WriteBackCS 61C L30 Introduction to Pipelined Execution (15)Garcia, Fall 2004 © UCBGraphical Pipeline RepresentationInstr.OrderLoadAddStoreSubOr I$Time (clock cycles) I$ALURegReg I$ D$ALUALUReg D$Reg I$ D$RegALURegRegReg D$Reg D$ALU(In Reg, right half highlight read, left half write)Reg I$CS 61C L30 Introduction to Pipelined Execution (16)Garcia, Fall 2004 © UCBExample•Suppose 2 ns for memory access, 2 ns for ALU operation, and 1 ns for register file read or write; compute instr rate•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 L30 Introduction to Pipelined Execution (17)Garcia, Fall 2004 © UCBPipeline Hazard: Matching socks in later loadA depends on D; stall since folder tied upTaskOrderBCDAEFbubble122 AM6 PM78910111Time303030 30303030CS 61C L30 Introduction to Pipelined Execution (18)Garcia, Fall 2004 © UCBAdministrivia•Final Exam will be in 230 Hearst
View Full Document
Unlocking...