inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 29 Introduction to Pipelined Execution Lecturer PSOE Dan Garcia www cs berkeley edu ddgarcia Bionic Eyes let blind see Johns Hopkins researchers have announced they have invented a bionic eye with a computer chip on the back of the eye and a small wireless video camera in a pair of glasses Face recognition Not yet but soon news bbc co uk 1 hi health 4411591 stm CS 61C L30 Introduction to Pipelined Execution 1 Garcia Fall 2004 UCB Review Single cycle datapath 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 Processor Input 5 Assemble the control logic Control Control is the hard part MIPS makes that easier Memory Datapath Output Instructions same size Source registers always in same place Immediates same size location Operations always on registers immediates CS 61C L30 Introduction to Pipelined Execution 2 Garcia Fall 2004 UCB Review 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 3 Garcia Fall 2004 UCB Review 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 Access 5 Write to Registers ALL instructions must go through ALL five stages CS 61C L30 Introduction to Pipelined Execution 4 Garcia Fall 2004 UCB 4 1 Instruction Fetch rs rt ALU Data memory rd registers PC instruction memory Review Datapath 3 3 imm 2 Decode Register Read CS 61C L30 Introduction to Pipelined Execution 5 3 Execute 4 Memory 5 Write Back Garcia Fall 2004 UCB Gotta Do Laundry Ann Brian Cathy Dave each have one load of clothes to wash dry fold and put away A B C D Washer takes 30 minutes Dryer takes 30 minutes Folder takes 30 minutes Stasher takes 30 minutes to put clothes into drawers CS 61C L30 Introduction to Pipelined Execution 6 Garcia Fall 2004 UCB Sequential Laundry 6 PM 7 T a s k A 8 9 10 11 12 1 2 AM 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 Time B C O D r d e r Sequential laundry takes 8 hours for 4 loads CS 61C L30 Introduction to Pipelined Execution 7 Garcia Fall 2004 UCB Pipelined Laundry 6 PM 7 T a s k 8 9 3030 30 30 30 30 30 10 11 12 1 2 AM Time A B C O D r d e Pipelined r 3 5 hours laundry takes for 4 loads CS 61C L30 Introduction to Pipelined Execution 8 Garcia Fall 2004 UCB General 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 time CS 61C L30 Introduction to Pipelined Execution 9 Garcia Fall 2004 UCB Pipelining Lessons 1 2 6 PM T a s k O r d e r 7 8 9 Time 30 30 30 30 30 30 30 A B C D 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 example CS 61C L30 Introduction to Pipelined Execution 10 Garcia Fall 2004 UCB Pipelining Lessons 2 2 Suppose new Washer takes 20 6 PM 7 8 9 minutes new Time T Stasher takes 20 a 30 30 30 30 30 30 30 minutes How s A much faster is k pipeline B O r d e r C D Pipeline rate limited by slowest pipeline stage Unbalanced lengths of pipe stages also reduces speedup CS 61C L30 Introduction to Pipelined Execution 11 Garcia Fall 2004 UCB Steps in Executing MIPS 1 IFetch Fetch Instruction Increment PC 2 Decode Instruction Read Registers 3 Execute Mem ref Calculate Address Arith log Perform Operation 4 Memory Load Read Data from Memory Store Write Data to Memory 5 Write Back Write Data to Register CS 61C L30 Introduction to Pipelined Execution 12 Garcia Fall 2004 UCB Pipelined Execution Representation Time IFtch Dcd Exec Mem WB IFtch Dcd Exec Mem WB IFtch Dcd Exec Mem WB IFtch Dcd Exec Mem WB IFtch Dcd Exec Mem WB IFtch Dcd Exec Mem WB Every instruction must take same number of steps also called pipeline stages so some will go idle sometimes CS 61C L30 Introduction to Pipelined Execution 13 Garcia Fall 2004 UCB 4 1 Instruction Fetch rs rt ALU Data memory rd registers PC instruction memory Review Datapath for MIPS imm 5 Write 2 Decode 3 Execute 4 Memory Back Register Read Use datapath figure to represent pipeline IFtch Dcd Exec Mem WB Reg CS 61C L30 Introduction to Pipelined Execution 14 ALU I D Reg Garcia Fall 2004 UCB Graphical Pipeline Representation In Reg right half highlight read left half write Time clock cycles Reg Reg D Reg I Reg D Reg I Reg ALU D Reg I Reg ALU I D ALU Reg ALU I ALU I n s Load t Add r Store O Sub r d Or e r D CS 61C L30 Introduction to Pipelined Execution 15 Reg Garcia Fall 2004 UCB Example 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 ns CS 61C L30 Introduction to Pipelined Execution 16 Garcia Fall 2004 UCB Pipeline Hazard Matching socks in later load 6 PM 7 T a s k 8 9 3030 30 30 30 30 30 A 10 11 12 1 2 AM Time bubble B C O D r d E e F r A depends on D stall since folder tied up CS 61C L30 Introduction to Pipelined Execution 17 Garcia Fall 2004 UCB Administrivia Any administration CS 61C L30 Introduction to Pipelined Execution 18 Garcia Fall 2004 UCB Problems for Computers Limits to pipelining Hazards prevent next instruction from executing during its designated clock cycle Structural hazards HW cannot support this combination of instructions single person to fold and put clothes away Control hazards Pipelining of branches other instructions stall the pipeline until the hazard bubbles in the pipeline Data hazards Instruction depends on result of prior instruction still in the pipeline missing sock CS 61C L30 Introduction to Pipelined Execution 19 Garcia Fall 2004 UCB Structural Hazard 1 Single Memory 1 …
View Full Document
Unlocking...