Chapter Six 1 2004 Morgan Kaufmann Publishers Pipelining The laundry analogy 2 2004 Morgan Kaufmann Publishers Pipelining Improve performance by increasing instruction throughput Program execution Time order in instructions 200 lw 1 100 0 Instruction fetch Reg lw 2 200 0 400 600 Data access ALU 800 1000 1200 1400 ALU Data access 1600 1800 Reg Instruction Reg fetch 800 ps lw 3 300 0 Reg Instruction fetch 800 ps Note timing assumptions changed for this example 800 ps Program execution Time order in instructions lw 1 100 0 200 Instruction fetch 400 Reg lw 2 200 0 200 ps Instruction fetch lw 3 300 0 200 ps 600 ALU Reg Instruction fetch 800 Data access ALU Reg 1000 1200 1400 Reg Data access ALU Reg Data access Reg 200 ps 200 ps 200 ps 200 ps 200 ps Ideal speedup is number of stages in the pipeline Do we achieve this 3 2004 Morgan Kaufmann Publishers Pipelining What makes it easy all instructions are the same length just a few instruction formats memory operands appear only in loads and stores What makes it hard structural hazards suppose we had only one memory control hazards need to worry about branch instructions data hazards an instruction depends on a previous instruction We ll build a simple pipeline and look at these issues We ll talk about modern processors and what really makes it hard exception handling trying to improve performance with out of order execution etc 4 2004 Morgan Kaufmann Publishers Basic Idea IF Instruction fetch ID Instruction decode register file read EX Execute address calculation MEM Memory access WB Write back Add 4 Shift left 2 P C Address Instruction Instruction memory Read Read register 1 data1 Read register 2 Registers Write Read register data2 Write data 16 ADD Add result Zero ALU ALU result Address Read data Data Memory Write data Sign 32 extend What do we need to add to actually split the datapath into stages 5 2004 Morgan Kaufmann Publishers Pipelined Datapath IF ID ID EX EX MEM MEM WB Add 4 Shift left 2 PC Address Instruction memory Add Add result Read register 1 Read data 1 Read register 2 Registers Read Write data 2 register Zero ALU ALU result Read data Address Data memory Write data Write data 16 Sign extend 32 Can you find a problem even if there are no dependencies What instructions can we execute to manifest the problem 6 2004 Morgan Kaufmann Publishers Corrected Datapath IF ID ID EX EX MEM MEM WB Add 4 Shift left 2 PC Address Instruction memory Add Add result Read register 1 Read data 1 Read register 2 Registers Read Write data 2 register Zero ALU ALU result Read data Address Data memory Write data Write data 16 Sign extend 32 7 2004 Morgan Kaufmann Publishers Inst Flow in A Pipelined Datapath IF ID Stages 8 2004 Morgan Kaufmann Publishers Inst Flow in A Pipelined Datapath EX Stage 9 2004 Morgan Kaufmann Publishers Inst Flow in A Pipelined Datapath MEM WB Stages 10 2004 Morgan Kaufmann Publishers Graphically Representing Pipelines Time in clock cycles Program execution order in instructions lw 1 100 0 lw 2 200 0 lw 3 300 0 CC 1 CC 2 IM Reg IM CC 3 ALU Reg IM CC 4 CC 5 DM Reg ALU DM Reg ALU DM Reg CC 6 CC7 Reg Can help with answering questions like how many cycles does it take to execute this code what is the ALU doing during cycle 4 use this representation to help understand datapaths 11 2004 Morgan Kaufmann Publishers Pipeline Control PCSrc IF ID ID EX EX MEM MEM WB Add Add Add result 4 Shift left 2 Branch RegWrite PC Address Instruction memory Read register 1 Read data 1 Read register 2 Registers Read Write data 2 register MemWrite ALUSrc Zero Add ALU result MemtoReg Read data Address Data memory Write data Write data Instruction 15 0 Instruction 20 16 16 Sign extend 32 6 ALU control MemRead ALUOp Instruction 15 11 RegDst 12 2004 Morgan Kaufmann Publishers Pipeline control We have 5 stages What needs to be controlled in each stage Instruction Fetch and PC Increment Instruction Decode Register Fetch Execution Memory Stage Write Back How would control be handled in an automobile plant a fancy control center telling everyone what to do should we use a finite state machine 13 2004 Morgan Kaufmann Publishers Pipeline Control Pass control signals along just like the data Instruction R format lw sw beq Execution Address Calculation Memory access stage stage control lines control lines Reg ALU ALU ALU Mem Mem Dst Op1 Op0 Src Branch Read Write 1 1 0 0 0 0 0 0 0 0 1 0 1 0 X 0 0 1 0 0 1 X 0 1 0 1 0 0 Write back stage control lines Reg Mem to write Reg 1 0 1 1 0 X 0 X WB Instruction IF ID Control M WB EX M WB ID EX EX MEM MEM WB 14 2004 Morgan Kaufmann Publishers Datapath with Control PCSrc ID EX Control IF ID WB EX MEM M WB EX M MEM WB WB Add 4 Shift left 2 PC Address Instruction memory Add Add result Branch ALUSrc Read register 1 Read data 1 Read register 2 Registers Read Write data 2 register Zero ALU ALU result Read data Address Data memory Write data Write data Instruction 15 0 Instruction 20 16 16 Sign extend 32 6 ALU control MemRead ALUOp Instruction 15 11 RegDst 15 2004 Morgan Kaufmann Publishers Dependencies Problem with starting next instruction before first is finished dependencies that go backward in time are data hazards Time in clock cycles CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9 10 10 10 10 10 20 20 20 20 20 IM Reg DM Reg Value of register 2 Program execution order in instructions sub 2 1 3 and 12 2 5 or 13 6 2 add 14 2 2 sw 15 100 2 IM Reg IM DM Reg IM Reg DM Reg IM Reg DM Reg Reg DM Reg 16 2004 Morgan Kaufmann Publishers Software Solution Have compiler guarantee no hazards by forcing the consumer instruction to wait i e inserting no ops Where do we insert the no ops sub and or add sw 2 1 3 12 2 5 13 6 2 14 2 2 15 100 2 Problem this really slows us down 17 2004 Morgan Kaufmann Publishers Forwarding Use temporary results don t wait for them to be written register file forwarding to handle read write to same register ALU forwarding Time in clock cycles CC 1 CC 2 Value of register 2 10 10 Value of EX MEM X X Value of MEM WB X X CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9 10 X X 10 20 X 10 20 X 20 20 X X 20 X X 20 X X 20 X X DM Reg Program execution order in instructions sub 2 1 3 and 12 2 5 or 13 6 2 add 14 2 …