CS 61C L30 Introduction to Pipelined Execution (1)Garcia, Fall 2004 © UCBLecturer PSOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61cCS61C : Machine Structures Lecture 29 – Introduction to Pipelined ExecutionBionic Eyes let blind see! ⇒news.bbc.co.uk/1/hi/health/4411591.stmJohns Hopkins researchers haveannounced they have invented a “bionic eye”with a computer chip on the back of the eyeand a small wireless video camera in a pair ofglasses. Face recognition? Not yet, but soon!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 clockmethodology• 3. Assemble datapath meeting the requirements• 4. Analyze implementation of each instruction todetermine setting of control points that effects theregister 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 thatperforms operations necessary toexecute programs.• Control instructs datapath on what todo next.• Datapath needs:• access to storage (general purposeregisters 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 aninstruction):1. Instruction Fetch (Increment PC)2. Instruction Decode (Read Registers)3. ALU (Computation)4. Memory Access5. Write to Registers• ALL instructions must go throughALL 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, Daveeach have one load ofclothes to wash, dry,fold, and put awayA B C D° Dryer takes 30 minutes° “Folder” takes 30 minutes° “Stasher” takes 30 minutesto put clothes into drawers° Washer takes 30 minutesCS 61C L30 Introduction to Pipelined Execution (7)Garcia, Fall 2004 © UCBSequential Laundry• Sequential laundry takes8 hours for 4 loadsTaskOrderBCDA30Time30 30 3030 30 3030 30 30 3030 30 30 30306 PM78910111212 AMCS 61C L30 Introduction to Pipelined Execution (8)Garcia, Fall 2004 © UCBPipelined Laundry• Pipelined laundry takes3.5 hours for 4 loads!TaskOrderBCDA122 AM6 PM78910111Time303030 303030 30CS 61C L30 Introduction to Pipelined Execution (9)Garcia, Fall 2004 © UCBGeneral Definitions• Latency: time to completely execute acertain task• for example, time to read a sector fromdisk is disk access time or disk latency• Throughput: amount of work that canbe done over a period of timeCS 61C L30 Introduction to Pipelined Execution (10)Garcia, Fall 2004 © UCBPipelining Lessons (1/2)• Pipelining doesn’t helplatency of single task,it helps throughput ofentire workload• Multiple tasksoperatingsimultaneously usingdifferent resources• Potential speedup =Number pipe stages• Time to “fill” pipelineand time to “drain” itreduces speedup:2.3X v. 4X in thisexample6 PM7 8 9TimeBCDA3030 30 303030 30TaskOrderCS 61C L30 Introduction to Pipelined Execution (11)Garcia, Fall 2004 © UCBPipelining Lessons (2/2)• Suppose newWasher takes 20minutes, newStasher takes 20minutes. Howmuch faster ispipeline?• Pipeline ratelimited by slowestpipeline stage• Unbalancedlengths of pipestages alsoreduces speedup6 PM7 8 9TimeBCDA3030 30 303030 30TaskOrderCS 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 numberof steps, also called pipeline “stages”, sosome 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 nsfor ALU operation, and 1 ns for registerfile read or write; compute instr rate• Nonpipelined Execution:• lw : IF + Read Reg + ALU + Memory + WriteReg = 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 303030 30CS 61C L30 Introduction to Pipelined Execution (18)Garcia, Fall 2004 © UCBAdministrivia• Any administration?CS 61C L30 Introduction to Pipelined Execution (19)Garcia, Fall 2004 © UCBProblems for Computers• Limits to pipelining: Hazards preventnext instruction from executing duringits designated clock cycle• Structural hazards: HW cannot supportthis combination of instructions (singleperson to fold and put clothes away)• Control hazards: Pipelining of branches& other instructions stall the pipelineuntil the hazard; “bubbles” in the pipeline• Data
View Full Document
Unlocking...