WIXLIB

Pipelining and HazardsInstructor: Steven Ho

Great Idea #4: ParallelismSoftware Parallel RequestsAssigned to computere.g. search erLeverage Parallel Threads Parallelism&Assigned to coree.g. lookup, adsAchieve HighPerformanceComputer Parallel Instructions 1 instruction @ one timee.g. 5 pipelined instructions Parallel Data 1 data item @ one timee.g. add of 4 pairs of n Unit(s) Hardware descriptionsAll gates functioning inparallel at same time CoreFunctionalUnit(s)A0 B0 A1 B1 A2 B2 A3 B3Cache MemoryCS61C Su18 - Lecture 13Logic Gates2

Review of Last Lecture Implementing controller for your datapath– Take decoded signals from instruction andgenerate control signals Pipelining improves performance by exploitingInstruction Level Parallelism––––7/12/20175-stage pipeline for RISC-V: IF, ID, EX, MEM, WBExecutes multiple instructions in parallelEach instruction has the same latencyWhat can go wrong?CS61C Su18 - Lecture 133

Agenda RISC-V Pipeline Hazards– Structural– Data R-type instructions Load– Control Superscalar processors7/12/2017CS61C Su18 - Lecture 134

Recap: Pipelining with RISC-Vtinstructioninstruction sequenceadd t0, t1, t2or t3, t4, t5sll t6, t0, t3tcycleTimingInstruction time, tinstructionClock rate, fsRelative speed7/11/2018Single CyclePipeliningtstep 100 200 pstcycle 200 psRegister access only 100 psAll cycles same length tcycle 800 ps1000 ps1/800 ps 1.25 GHz1/200 ps 5 GHz1x4x5

RISC-V Pipelinetinstruction 1000 psadd t0, t1, t2Resource use in aparticular time slotResource use ofinstruction over timeor t3, t4, t5instruction sequenceslt t6, t0, t3sw t0, 4(t3)lw t0, 8(t3)addi t2, t2, 17/11/2018tcycle 200 psCS61C Su18 - Lecture 136

Single-Cycle RISC-V RV32I Datapath 4Reg[]wbalupc :20] AddrB DataBImm.Genalu1inst[19:15] AddrA DataAinst[31:7]pc 4pc0DataW1DataRwb0mem1imm[31:0]ImmSel RegWEn BrUn BrEq BrLTBSel ASel ALUSelMemRWWBSel7

Pipelining RISC-V RV32I Datapath 4Reg[]wbalupc st[24:20] AddrB DataBInstruction Fetch(F)7/11/2018Imm.Genalu1inst[19:15] AddrA DataAinst[31:7]pc 0]InstructionDecode/Register Read(D)ALU Execute(X)Memory Access(M)Write Back(W)8

Pipelined RISC-V RV32I DatapathRecalculate PC 4 in M stage to avoidsending both PC and PC 4 down pipelinepcFpcD 4aluXReg[]DataD1 4rs1XALUAddrD0pcF 4pcMpcXIMEMAddrA DataAAddrBinstDaluM 18DMEMimmXrs2MinstMinstWMust pipeline instruction along with data, socontrol operates correctly in each stage9

Each stage operates on different instructionlw t0, 8(t3)pcFsw t0, 4(t3)Reg[]DataD1aluXIMEM 4rs1XALUAddrA DataAAddrBinstDDMEMaluM 18add t0,t1, t2pcMAddrD0pcF 4or t3, t4, t5pcXpcD 4slt t6, t0, t3immXrs2MinstMPipeline registers separate stages, hold data for each instruction in flightinstW10

Pipelined Control Control signals derived from instruction As in single-cycle implementation Information is stored in pipeline registers for use by later stages7/11/201811

Graphical Pipeline RepresentationALU RegFile: right half is read, left half is writeTime (clock cycles)InI D RegRegs LoadtI D RegRegAddrALURegRegD RegI RegALUI D ALUOr Subde Orr7/12/2017RegALUStoreI D CS61C Su18 - Lecture 13Reg12

Question: Which of the following signals (busesor control signals) for RISC-V does NOT need tobe passed into the EX pipeline stage for a beqinstruction?beq t0 t1 Label(A) BrUn(B) MemWrI IDRegEXALU(C) RegWrIFMem WBD Reg(D) WBSel13

AgendaHazardsAhead! RISC-V Pipeline Hazards– Structural– Data R-type instructions Load– Control Superscalar processors7/12/2017CS61C Su18 - Lecture 1314

Pipelining HazardsA hazard is a situation that prevents starting thenext instruction in the next clock cycle1) Structural hazard– A required resource is busy(e.g. needed in multiple stages)2) Data hazard– Data dependency between instructions– Need to wait for previous instruction tocomplete its data write3) Control hazard– Flow of execution depends on previous instruction7/12/2017CS61C Su18 - Lecture 1315

Agenda RISC-V Pipeline Hazards– Structural– Data R-type instructions Load– Control Superscalar processors7/12/2017CS61C Su18 - Lecture 1316

Structural Hazard Problem: Two or more instructions in the pipelinecompete for access to a single physical resource Solution 1: Instructions take it in turns to use resource,some instructions have to stall Solution 2: Add more hardware to machine Can always solve a structural hazard by adding morehardware7/11/2018CS61C Su18 - Lecture 1317

1. Structural Hazards Conflict for use of a resourceTime (clock cycles)RegRegD RegI RegD RegI RegALUD RegI RegALUI D ALU7/12/2017RegALUO Instr 2rd Instr 3er Instr 4I ALUIns Loadtr Instr 1D CS61C Su18 - Lecture 13Can we read andwrite to registerssimultaneously?Reg18

Regfile Structural Hazards Each instruction: can read up to two operands in decode stage can write one value in writeback stage Avoid structural hazard by having separate “ports” two independent read ports and one independent write port Three accesses per cycle can happen simultaneously7/11/2018CS61C Su18 - Lecture 1319

Regfile Structural Hazards Two alternate solutions:1) Build RegFile with independent read and writeports (what you will do in the project; good forsingle-stage)2) Double Pumping: split RegFile access in two!Prepare to write during 1st half, write on fallingedge, read during 2nd half of each clock cycle Will save us a cycle later.Possible because RegFile access is VERY fast(takes less than half the time of ALU stage) Conclusion: Read and Write to registersduring same clock cycle is okay7/12/2017CS61C Su18 - Lecture 1320

Memory Structural Hazards Conflict for use of a resourceTime (clock cycles)I RegD RegI RegD I RegI CS61C Su18 - Lecture 13D RegRegALURegTrying to read(and maybewrite) samememory twicein same clockcycleRegALUD ALU7/12/2017RegALUO Instr 2rd Instr 3er Instr 4I ALUIns Loadtr Instr 1D Reg21

Instruction and Data CachesMemory sPCRegistersProgramDataCacheArithmetic & Logic Unit(ALU)DataCaches: small and fast “buffer” memories7/11/2018CS61C Su18 - Lecture 1322

Structural Hazards – Summary Conflict for use of a resource In RISC-V pipeline with a single memory Load/store requires data access Without separate memories, instruction fetch would have to stallfor that cycle All other operations in pipeline would have to wait Pipelined datapaths require separate instruction/datamemories Or separate instruction/data caches RISC ISAs (including RISC-V) designed to avoid structuralhazards e.g. at most one memory access/instructionCS61C Su18 - Lecture 1323

Administrivia Proj2-2 due 7/13, HW3/4 due 7/16– 2-2 autograder being run Guerilla Session Tonight! 4-6pm HW0-2 grades should now be accurate onglookup Project 3 released tomorrow night! Supplementary review sessions starting– First one this Sat. (7/14) 12-2p, Cory 540AB7/12/2017CS61C Su18 - Lecture 1324

Agenda RISC-V Pipeline Hazards– Structural– Data R-type instructions Load– Control Superscalar processors7/12/2017CS61C Su18 - Lecture 1325

2. Data Hazards (1/2) Consider the following sequence during WB7/12/2017t1,t0,t0,t0,t0,t2t3t6t8t10Readduring IDCS61C Su18 - Lecture 1326

2. Data Hazards (2/2) Data-flow backward in time are hazardsTime (clock cycles)I D RegHazard if no double pumpingRegD RegI RegD RegI RegD RegI RegALURegWBALU7/12/2017I EX MEMALUOr or t7, t0, t8de xor t9, t0, t10rID/RFALUand t5, t0, t6IFALUIn add t0, t1, t2st sub t4, t0, t3rD CS61C Su18 - Lecture 13Reg27

Solution 1: Stalling Problem: Instruction depends on result from previous instruction addsub Bubble:t0, t1, t2t4, t0, t3 effectively NOP: affected pipeline stages do “nothing”

Stalls and Performance Stalls reduce performance But stalls are required to get correct results Compiler can arrange code to avoid hazards and stalls Requires knowledge of the pipeline structure7/11/201829

Data Hazard Solution: Forwarding Forward result as soon as it is available– OK that it’s not stored in RegFile yetxor t9, t0, t107/12/2017RegRegD RegI RegD RegI RegD RegI RegALUt7, t0, t8I D ALUorRegWBALUand t5, t0, t6I EX MEMALUsub t4, t0, t3ID/RFALUadd t0, t1, t2IFArithmetic resultavailable in EXD Forwarding: grab operand from pipeline stage,rather than register fileReg30

Forwarding (aka Bypassing) Use result when it is computed Don’t wait for it to be stored in a register Requires extra connections in the datapath7/11/2018CS61C Su18 - Lecture 1331

Detect Need for Forwarding(example)DXinstX.rdMWCompare destination ofolder instructions inpipeline with sources ofnew instruction in decodestage.Must ignore writes to x0!add t0, t1, t2instD.rs1or t3, t0, t5sub t6, t0, t37/11/201832

Forwarding PathpcFpcD 4aluXReg[]DataD1 4rs1XALUAddrD0pcF 4pcMpcXIMEMAddrA DataAAddrBinstDaluM 18DMEMForwarding ControlLogicimmXrs2MinstMinstW33

Agenda RISC-V Pipeline Hazards– Structural– Data R-type instructions Load– Control Superscalar processors7/12/2017CS61C Su18 - Lecture 1334

Data Hazard: Loads (1/4) Recall: Dataflow backwards in time arehazardsI RegI EX MEMWBD RegRegALUsub t3, t0, t2ID/RFALUlw t0, 0(t1)IFD Reg Can’t solve all cases with forwarding– Must stall instruction dependent on load, thenforward (more hardware)7/12/2017CS61C Su18 - Lecture 1335

Data Hazard: Loads (2/4)This is what happens inhardware in a “hardwareinterlock” Hardware stalls pipeline– Called “hardware interlock”RegI RegRegbubbleCS61C Su18 - Lecture 13bubbleRegbubbleI RegD RegRegALUMust stallentirepipelineD ALU7/12/2017D I and t5, t0, t4or t7, t0, t6EX MEM WBALUsub t3, t0, t2I ID/RFALUlw t0, 0(t1)IFD 36

Data Hazard: Loads (3/4) Stall is equivalent to nopRegbub bubble blebubblebubblebubbleI RegD RegI RegALUD RegI RegALUsub t3, t0, t2D ALUnopI ALUlw t0, 0(t1)D Regand t5, t0, t4or t7, t0, t67/12/2017CS61C Su18 - Lecture 1337

Data Hazard: Loads (4/4) Slot after a load is called a load delay slot– If that instruction uses the result of the load,then the hardware will stall for one cycle– Equivalent to inserting an explicit nop in theslot except the latter uses more code space– Performance loss Idea: Let the compiler/assembler put anunrelated instruction in that slot no stall!7/12/2017CS61C Su18 - Lecture 1338

Code Scheduling to Avoid Stalls Reorder code to avoid use of load result in the nextinstruction! RISC-V code for D A B; E A C;Stall!Stall!Original Order:lw t1, 0(t0)lw t2, 4(t0)add t3, t1, t2sw t3, 12(t0)lw t4, 8(t0)add t5, t1, t4sw t5, 16(t0)Alternative:lw t1, 0(t0)lw t2, 4(t0)lw t4, 8(t0)add t3, t1, t2sw t3, 12(t0)add t5, t1, t4sw t5, 16(t0)11 cycles7/11/201813 cycles39

Break!7/09/2018CS61C Su18 - Lecture 1140

Agenda RISC-V Pipeline Hazards– Structural– Data R-type instructions Load– Control Superscalar processors7/12/2017CS61C Su18 - Lecture 1341

3. Control Hazards Branch (beq, bne) determines flow of control– Fetching next instruction depends on branchoutcome– Pipeline can’t always fetch correct instruction Still working on ID stage of branch Simple Solution: Stall on every branch untilwe have the new PC value– How long must we stall?7/13/2016CS61C Su16 - Lecture 1342

Branch Stall When is comparison result available?Time (clock cycles)RegRegD RegI RegD RegI RegALUD RegI RegALUI D ALURegALU7/13/2016I ALUIn beqst Instr 1rInstr 2Or Instr 3de Instr 4rD CS61C Su16 - Lecture 13TWO bubblesrequired perbranch!Reg43

3. Control Hazard: Branching Option #1: Moving branch comparator to IDstage– As soon as instruction is decoded, immediatelymake a decision and set the new value of the PC– Benefit: Branch decision made in 2nd stage, soonly one nop is needed instead of two– Side Note: Have to compute new PC value in IDinstead of EX Adds extra hardware and reduces redundancy Branches are idle in EX, MEM, and WB7/13/2016CS61C Su16 - Lecture 1344

Improved Branch Stall When is comparison result available?Time (clock cycles)RegRegD RegI RegD RegI RegALUD RegI RegALUI D ALURegALU7/13/2016I ALUIn beqst Instr 1rInstr 2Or Instr 3de Instr 4rD CS61C Su16 - Lecture 13Only onebubblerequired nowReg45