CS61C Machine Structures Lecture 28 CPU Design Pipelining to Improve Performance 4 5 2006 John Wawrzynek www cs berkeley edu johnw www inst eecs berkeley edu cs61c CS 61C L29 CPU Pipelining 1 Wawrzynek Spring 2006 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 Instructions same size Source registers always in same place Immediates same size location Operations always on registers immediates CS 61C L29 CPU Pipelining 2 Output Wawrzynek Spring 2006 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 L29 CPU Pipelining 3 Wawrzynek Spring 2006 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 L29 CPU Pipelining 4 Wawrzynek Spring 2006 UCB rs rt ALU Data memory rd registers PC instruction memory Review Datapath 3 3 imm 4 1 Instruction Fetch 2 Decode Register Read 3 Execute 4 Memory CS 61C L29 CPU Pipelining 5 5 Write Back Wawrzynek Spring 2006 UCB Processor Performance Can we estimate the clock rate frequency of our single cycle processor We know 1 cycle per instruction LW is the most demanding instruction Assume approximate delays for major pieces of the datapath Instr Mem ALU Data Mem 2ns each regfile 1ns Instruction execution requires 2 1 2 2 1 8ns 125 MHz What can we do to improve clock rate Will this improve performance as well We would like that any increases in clock rate will result in programs executing quicker CS 61C L29 CPU Pipelining 6 Wawrzynek Spring 2006 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 L29 CPU Pipelining 7 Wawrzynek Spring 2006 UCB Sequential Laundry 6 PM 7 T a s k O r d e r 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 D Sequential laundry takes 8 hours for 4 loads CS 61C L29 CPU Pipelining 8 Wawrzynek Spring 2006 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 L29 CPU Pipelining 9 Wawrzynek Spring 2006 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 L29 CPU Pipelining 10 Wawrzynek Spring 2006 UCB Pipelining Lessons 1 2 6 PM T a s k O r d e r 7 8 9 Time Pipelining doesn t help latency of single task it helps throughput of entire workload A Multiple tasks operating simultaneously using different resources B Potential speedup Number pipe stages 30 30 30 30 30 30 30 C D CS 61C L29 CPU Pipelining 11 Time to fill pipeline and time to drain it reduces speedup 2 3X v 4X in this example Wawrzynek Spring 2006 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 CS 61C L29 CPU Pipelining 12 Pipeline rate limited by slowest pipeline stage Unbalanced lengths of pipe stages reduces speedup Wawrzynek Spring 2006 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 L29 CPU Pipelining 13 Wawrzynek Spring 2006 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 L29 CPU Pipelining 14 Wawrzynek Spring 2006 UCB rd rs rt Data memory registers PC instruction memory Review Datapath for MIPS ALU imm 4 1 Instruction Fetch 5 Write 2 Decode 3 Execute 4 Memory Back Register Read Use datapath figure to represent pipeline IFtch Dcd Exec Mem WB Reg ALU I D Reg CS 61C L29 CPU Pipelining 15 Wawrzynek Spring 2006 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 CS 61C L29 CPU Pipelining 16 I ALU I n s Load t Add r Store O Sub r d Or e r D Reg Wawrzynek Spring 2006 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 8ns for single cycle processor Pipelined Execution Max IF Read Reg ALU Memory Write Reg 2 ns CS 61C L29 CPU Pipelining 17 Wawrzynek Spring 2006 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 r F A depends on D stall since folder tied up CS 61C L29 CPU Pipelining 18 Wawrzynek Spring 2006 UCB Administrivia Adam is the TA in charge of project 4 He says You should probably have your software gate CPU working by today and if not that you probably need to be putting more time in on this It s not a deadline just a checkpoint to help you maintain your own sanity He will have extra office hours this week to help people and answer questions Wednesday 6 00p 8 00p in Soda 283H Thursday 6 00p 8 00p in Soda 271 …
View Full Document
Unlocking...