CPE 631 Lecture 03 Review Pipelining Memory Hierarchy Electrical and Computer Engineering University of Alabama in Huntsville CPE 631 AM Outline Pipelined Execution 5 Steps in MIPS Datapath Pipeline Hazards Structural Data Control 14 01 19 UAH CPE631 2 CPE 631 AM Laundry Example Four loads of clothes A B C D A B C D Task each one to wash dry and fold Resources Washer takes 30 minutes Dryer takes 40 minutes Folder takes 20 minutes 14 01 19 UAH CPE631 3 CPE 631 AM Sequential Laundry 6 PM 7 8 9 10 11 Midnight Time 30 40 20 30 40 20 30 40 20 30 40 20 T a s k O r d e r A B C D Sequential laundry takes 6 hours for 4 loads If they learned pipelining how long would laundry take 14 01 19 UAH CPE631 4 CPE 631 AM Pipelined Laundry Pipelined laundry takes 3 5 hours for 4 loads 6 PM 7 8 9 10 11 Midnight Time T a s k O r d e r 30 40 40 40 40 20 A B C D 14 01 19 UAH CPE631 5 CPE 631 AM Pipelining Lessons 6 PM 7 8 9 Time T a s k O r d e r 30 40 40 40 40 20 A B C D 14 01 19 UAH CPE631 Pipelining doesn t help latency of single task it helps throughput of entire workload Pipeline rate limited by slowest pipeline stage Multiple tasks operating simultaneously Potential speedup Number pipe stages Unbalanced lengths of pipe stages reduces speedup Time to fill pipeline and time to drain reduce speedup 6 CPE 631 AM Computer Pipelines Execute billions of instructions so throughput is what matters What is desirable in instruction sets for pipelining Variable length instructions vs all instructions same length Memory operands part of any operation vs memory operands only in loads or stores Register operand many places in instruction format vs registers located in same place 14 01 19 UAH CPE631 7 CPE 631 AM A Typical RISC 32 bit fixed format instruction 3 formats Memory access only via load store instructions 32 32 bit GPR R0 contains zero 3 address reg reg arithmetic instruction registers in same place Single address mode for load store base displacement no indirection Simple branch conditions Delayed branch see SPARC MIPS HP PA Risc DEC Alpha IBM PowerPC CDC 6600 CDC 7600 Cray 1 Cray 2 Cray 3 14 01 19 UAH CPE631 8 CPE 631 AM Example MIPS Register Register 1110 31 2625 2120 1615 Op Rs1 Rs2 Rd Register Immediate 31 2625 2120 1615 Op Rs1 Rd Branch 31 2625 2120 1615 Op Rs1 Rs2 Opx 65 0 Opx 0 immediate 0 immediate Jump Call 31 2625 Op 14 01 19 0 target UAH CPE631 9 CPE 631 AM 5 Steps of MIPS Datapath Instruction Fetch Instr Decode Reg Fetch Adder 4 Next SEQ PC L M D MUX Data Memory ALU MUX MUX Imm Reg File Inst Memory Address RD Writ e Back Zero RS1 RS2 Memory Access MUX Next PC Execute Addr Calc Sign Extend WB Data 14 01 19 UAH CPE631 10 CPE 631 AM 5 Steps of MIPS Datapath cont d Instruction Fetch Instr Decode Reg Fetch Next SEQ PC Adder Next SEQ PC Writ e Back Zero RS1 MUX MEM WB Data Memory EX MEM ALU MUX MUX ID EX Imm Reg File IF ID Memory Address RS2 WB Data 4 Memory Access MUX Next PC Execute Addr Calc Sign Extend RD RD RD Data stationary control local 14 01 19 decode for eachUAH CPE631 instruction phase 11 CPE 631 AM Visualizing Pipeline Reg IM O r d e r Reg IM CC 4 CC 5 DM Reg Reg IM 14 01 19 DM Reg UAH CPE631 CC 6 CC 7 Reg DM ALU IM CC 3 ALU I n s t r CC 2 ALU CC 1 ALU Time clock cycles Reg DM Reg 12 CPE 631 AM Instruction Flow through Pipeline Time clock cycles CC 1 Nop Nop ALU ALU Lw R4 0 R2 Nop Add R1 R2 R3 Reg Reg Reg Reg UAH CPE631 DM DM DM DM 14 01 19 Sub R6 R5 R7 Add R1 R2 R3 Nop Nop Reg Lw R4 0 R2 ALU ALU IM Add R1 R2 R3 Xor R9 R8 R1 Reg Reg Reg Nop CC 4 IM IM IM Sub R6 R5 R7 Lw R4 0 R2 Add R1 R2 R3 CC 3 CC 2 13 CPE 631 AM DLX Pipeline Definition IF ID Stage IF IF ID IR Mem PC if EX MEM cond IF ID NPC PC EX MEM ALUOUT else IF ID NPC PC PC 4 Stage ID ID EX A Regs IF ID IR6 10 ID EX B Regs IF ID IR11 15 ID EX Imm IF ID IR16 16 IF ID IR16 31 ID EX NPC IF ID NPC ID EX IR IF ID IR 14 01 19 UAH CPE631 14 CPE 631 AM DLX Pipeline Definition IE ALU EX MEM IR ID EX IR EX MEM ALUOUT ID EX A func ID EX B or EX MEM ALUOUT ID EX A func ID EX Imm EX MEM cond 0 load store EX MEM IR ID EX IR EX MEM B ID EX B EX MEM ALUOUT ID EX A ID EX Imm EX MEM cond 0 branch EX MEM Aluout ID EX NPC ID EX Imm 2 EX MEM cond ID EX A func 0 14 01 19 UAH CPE631 15 CPE 631 AM DLX Pipeline Definition MEM WB Stage MEM ALU MEM WB IR EX MEM IR MEM WB ALUOUT EX MEM ALUOUT load store MEM WB IR EX MEM IR MEM WB LMD Mem EX MEM ALUOUT or Mem EX MEM ALUOUT EX MEM B Stage WB ALU Regs MEM WB IR16 20 MEM WB ALUOUT or Regs MEM WB IR11 15 MEM WB ALUOUT load Regs MEM WB IR11 15 MEM WB LMD 14 01 19 UAH CPE631 16 CPE 631 AM Its Not That Easy 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 Data hazards Instruction depends on result of prior instruction still in the pipeline Control hazards Caused by delay between the fetching of instructions and decisions about changes in control flow branches and jumps 14 01 19 UAH CPE631 17 CPE 631 AM One Memory Port Structural Hazards Time clock cycles Instr 2 Instr 3 Instr 4 14 01 19 Ifetch DMem Reg Ifetch Reg Ifetch Reg DMem Ifetch Reg ALU Instr 1 Reg ALU Ifetch ALU O r d e r Load ALU I n s t r ALU Cycle 1Cycle 2 Cycle 3 Cycle 4Cycle 5 Cycle 6Cycle 7 Reg DMem UAH CPE631 Reg DMem Reg Reg DMem Reg 18 CPE 631 AM One Memory Port Structural Hazards cont d Time clock cycles Instr 1 Instr 2 Stall Instr 3 14 01 19 Reg Ifetch DMem Reg Ifetch Reg Reg DMem ALU Ifetch Reg DMem Reg Bubble Bubble Bubble Bubble Bubble Ifetch UAH CPE631 Reg ALU O r d …