inst eecs berkeley edu cs61c su05 CS61C Machine Structures An Abstract View of the Critical Path Critical 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 InstructionStable Time for Register File Write This affects how much you can overclock your PC Lecture 18 Pipelining 1 PC Next Address Clk 2005 07 20 Clk ALU Ideal Instruction Memory Rd Rs Rt Imm 5 5 5 16 Instruction Address A 32 Rw Ra Rb 32 32 32 bit Registers B Data 32 Address Data In Ideal Data Memory Clk 32 Andy Carle A Carle Summer 2005 UCB CS 61C L18 Pipelining I 1 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 A Carle Summer 2005 UCB CS 61C L18 Pipelining I 2 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 Review Datapath 2 3 Datapath is the hardware that performs operations necessary to execute programs Five stages of datapath executing an instruction 1 Instruction Fetch Increment PC Control instructs datapath on what to do next 2 Instruction Decode Read Registers Datapath needs 4 Memory Access access to storage general purpose registers and memory computational ability ALU 3 ALU Computation 5 Write to Registers ALL instructions must go through ALL five stages helper hardware local registers and PC CS 61C L18 Pipelining I 5 A Carle Summer 2005 UCB CS 61C L18 Pipelining I 6 A Carle Summer 2005 UCB Gotta Do Laundry rs rt Data memory rd Ann Brian Cathy Dave each have one load of clothes to wash dry fold and put away registers PC instruction memory Review Datapath 3 3 ALU Washer takes 30 minutes imm 4 1 Instruction Fetch Dryer takes 30 minutes 2 Decode Register Read 3 Execute 4 Memory Folder takes 30 minutes 5 Write Back Stasher takes 30 minutes to put clothes into drawers A Carle Summer 2005 UCB CS 61C L18 Pipelining I 7 T a s k O r d e r A 7 8 9 Pipelined Laundry 10 11 12 1 2 AM 6 PM 7 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 Time T a s k B C 9 3030 30 30 30 30 30 10 11 12 1 2 AM Time A B laundry takes 3 5 hours for 4 loads Sequential laundry takes 8 hours for 4 loads A Carle Summer 2005 UCB A Carle Summer 2005 UCB CS 61C L18 Pipelining I 10 General Definitions Pipelining Lessons 0 2 Terminology 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 8 C O D r d e Pipelined r D CS 61C L18 Pipelining I 9 A Carle Summer 2005 UCB CS 61C L18 Pipelining I 8 Sequential Laundry 6 PM A B C D A Carle Summer 2005 UCB 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 8 9 Time 30 30 30 30 30 30 30 A B O r d e r C 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 D Time to fill pipeline and time to drain it reduces speedup 2 3X v 4X in this example A Carle Summer 2005 UCB CS 61C L18 Pipelining I 13 Steps in Executing MIPS 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 Pipeline rate limited by slowest pipeline stage C D Unbalanced lengths of pipe stages also reduces speedup A Carle Summer 2005 UCB CS 61C L18 Pipelining I 14 Pipelined Execution Representation 1 IFetch Fetch Instruction Increment PC 2 Decode Instruction Read Registers Time IFtch Dcd Exec Mem WB IFtch Dcd Exec Mem WB 3 Execute Mem ref Calculate Address Arith log Perform Operation IFtch Dcd Exec Mem WB IFtch Dcd Exec Mem WB IFtch Dcd Exec Mem WB 4 Memory Load Read Data from Memory Store Write Data to Memory 5 Write Back Write Data to Register A Carle Summer 2005 UCB CS 61C L18 Pipelining I 15 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 I n Load s t Add r Store O Sub r d Or e r I CS 61C L18 Pipelining I 18 Reg I D Reg Reg D Reg I Reg D Reg I Reg D Reg I Reg ALU imm In Reg right half highlight read left half write Time clock cycles ALU Data memory registers PC ALU Graphical Pipeline Representation ALU 1 Instruction Fetch rs rt A Carle Summer 2005 UCB CS 61C L18 Pipelining I 16 ALU 4 rd Every instruction must take same number of steps also called pipeline stages so some will go idle sometimes ALU instruction memory Review Datapath for MIPS IFtch Dcd Exec Mem WB D Reg A Carle Summer 2005 UCB Example Example Suppose 2 ns for memory access 2 ns for ALU operation and 1 ns for register file read or write compute instruction throughput 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 Nonpipelined Execution lw IF Read Reg ALU Memory Write Reg 2 1 2 2 1 8 ns 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 add IF Read Reg …
View Full Document
Unlocking...