inst eecs berkeley edu cs61c su05 CS61C Machine Structures Lecture 18 Pipelining 1 2005 07 20 Andy Carle CS 61C L18 Pipelining I 1 A Carle Summer 2005 UCB An Abstract View of the Critical Path Critical Path Load Operation Delay clock through PC FFs This affects how much you Instruction Memory s Access Time can overclock Register File s Access Time your PC ALU to Perform a 32 bit Add Data Memory Access Time Ideal Instruction InstructionStable Time for Register File Write Memory Rd Rs Rt 5 5 5 PC Clk A 32 Clk CS 61C L18 Pipelining I 2 32 Rw Ra Rb 32 32 bit 32 Registers B ALU Next Address Instruction Address Imm 16 32 Data Address Data In Ideal Data Memory Clk A Carle Summer 2005 UCB Improve Critical Path Improve Clock Clk Critical path longest path through logic determines length of clock period To reduce clock period decrease path through CL by inserting State CS 61C L18 Pipelining I 3 A Carle Summer 2005 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 L18 Pipelining I 4 A Carle Summer 2005 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 L18 Pipelining I 5 A Carle Summer 2005 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 L18 Pipelining I 6 A Carle Summer 2005 UCB 4 1 Instruction Fetch CS 61C L18 Pipelining I 7 rs rt ALU Data memory rd registers PC instruction memory Review Datapath 3 3 imm 2 Decode Register Read 3 Execute 4 Memory 5 Write Back A Carle Summer 2005 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 L18 Pipelining I 8 A Carle Summer 2005 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 r D d e r Sequential laundry takes 8 hours for 4 loads CS 61C L18 Pipelining I 9 A Carle Summer 2005 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 laundry takes 3 5 hours for 4 loads CS 61C L18 Pipelining I 10 A Carle Summer 2005 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 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 time CS 61C L18 Pipelining I 11 A Carle Summer 2005 UCB Pipelining Lessons 0 2 Terminology 6 PM T a s k 7 9 Time 30 30 30 30 30 30 30 A B O r d e r 8 C Issue When instruction goes into first stage of pipe Commit when instruction finishes last stage D CS 61C L18 Pipelining I 12 A Carle Summer 2005 UCB Pipelining Lessons 1 2 6 PM T a s k 7 9 Time 30 30 30 30 30 30 30 A B O r d e r 8 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 L18 Pipelining I 13 A Carle Summer 2005 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 L18 Pipelining I 14 A Carle Summer 2005 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 L18 Pipelining I 15 A Carle Summer 2005 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 L18 Pipelining I 16 A Carle Summer 2005 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 CS 61C L18 Pipelining I 17 Reg ALU I D Reg A Carle Summer 2005 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 CS 61C L18 Pipelining I 18 Reg ALU I ALU I n s Load t Add r Store O Sub r d Or e r D Reg A Carle Summer 2005 UCB Example 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 ns CS 61C L18 Pipelining I 19 A Carle Summer 2005 UCB Example Suppose 2 ns for memory access 2 ns for ALU operation and 1 ns for register file read or write compute …
View Full Document
Unlocking...