Systems I Pipelining II Topics Pipelining hardware registers and feedback paths Difficulties with pipelines hazards Method of mitigating hazards SEQ Hardware valM data out Mem control Memory read Data Data memory memory write Addr Still sequential implementation Reorder PC stage to put at beginning Execute Bch valE CC CC ALU ALU ALU A Data ALU fun ALU B PC Stage Task is to select PC for current instruction Based on results computed by previous instruction valA Decode Processor State PC is no longer stored in register A ifun rA rB valC Instruction Instruction memory memory But can determine PC based on other stored information dstE dstM srcA srcB dstE dstM srcA srcB B Register Register M file file E icode Fetch valB Write back valP PC PC increment increment PC PC PC pIcode pBch pValM pValC pValP 2 Adding Pipeline Registers valE valM Write back valM W icode W valM W valE W valM W dstE W dstM valM W valM Data Data memory memory Memory Memory Addr Data Data Data memory memory M icode M Bch M valA Addr Data M valE Bch Bch CC CC Execute ALU ALU Execute aluA aluB srcA srcB dstA dstB icode valC valP E Fetch A B Register M Register file file E Instruction Instruction memory memory d srcA d srcB Decode valP icode ifun rA rB valC D A PC B M Register Register file file E Write back valP Instruction Instruction memory memory Fetch pState valA valB icode ifun rA rB valC PC PC increment increment PC PC ALU ALU aluA aluB valA valB Decode valE CC CC valP PC PC increment increment predPC f PC F 3 Pipeline Stages Fetch Select current PC Read instruction Compute incremented PC Decode Read program registers Execute Operate ALU Memory Read or write data memory Write Back Update register file 4 PIPE Hardware Pipeline registers hold intermediate values from instruction execution Forward Upward Paths Values passed from one stage to next Cannot jump past stages e g valC passes through decode Write back W icode valE valM dstE dstM data out read Mem control write Memory Data Data memory memory data in Addr M valA M Bch M icode Bch valE valA dstE dstM e Bch Execute E ALU fun ALU ALU CC CC icode ifun ALU A ALU B valC valA valB dstE dstM srcA srcB d srcA d srcB Select A Decode D Fetch A dstE dstM srcA srcB W valM B Register Register M file file E icode ifun rA rB Instruction Instruction memory memory f PC Select PC F d rvalA valC W valE valP PC PC increment increment Predict PC M valA W valM predPC 5 Signal Naming Conventions S Field Value of Field held in stage S pipeline register s Field Value of Field computed in stage S 6 Feedback Paths Predicted PC Guess value of next PC Write back W icode valE Jump taken not taken Fall through or target address Return point read Mem control write Memory To register file write ports Data Data memory memory data in Addr M valA M Bch M icode Bch valE valA dstE dstM e Bch Execute E ALU fun ALU ALU CC CC icode ifun ALU A ALU B valC valA valB dstE dstM srcA srcB d srcA d srcB Select A Decode D Fetch A icode ifun rA rB Instruction Instruction memory memory f PC Select PC F d rvalA dstE dstM srcA srcB W valM B Register Register M file file E Read from memory Register updates dstE dstM data out Branch information valM valC W valE valP PC PC increment increment Predict PC M valA W valM predPC 7 Pipeline Demonstration irmovl 1 eax I1 irmovl 2 ecx I2 irmovl 3 edx I3 irmovl 4 ebx I4 halt I5 1 2 3 4 5 6 7 8 9 F D F E D F M E D F W M E D F W M E D W M E W M W Cycle 5 File demo basic ys W I1 M I2 E I3 D I4 F I5 8 Data Dependencies 3 Nop s demo h3 ys 0x000 irmovl 10 edx 0x006 irmovl 3 eax 0x00c nop 0x00d nop 1 2 3 4 5 6 7 F D F E D F M E D W M E W M W F D F E D F 0x00e nop 0x00f addl edx eax 0x011 halt 8 9 10 M E D W M E W M W F D E M Cycle 6 W R eax 3 Cycle 7 D valA R edx 10 valB R eax 3 9 11 W Data Dependencies 2 Nop s demo h2 ys 0x000 irmovl 10 edx 0x006 irmovl 3 eax 1 2 3 4 5 F D E M W F D F E D F 0x00c nop 0x00d nop 0x00e addl edx eax 0x010 halt 6 7 8 M E D W M E W M W F D F E D M E 9 10 W M W Cycle 6 W R eax 3 Can t transport value produced by first instruction back in time D valA R edx 10 valB R eax 0 Error 10 Data Dependencies 1 Nop demo h1 ys 1 2 3 4 5 6 0x000 irmovl 10 edx F D F E D M E W M W F D F E D F M E D 0x006 irmovl 3 eax 0x00c nop 0x00d addl edx eax 0x00f halt 7 8 9 W M E W M W Cycle 5 W R edx 10 M Now a problem with both operands M valE 3 M dstE eax D valA R edx 0 valB R eax 0 Error 11 Data Dependencies No Nop demo h0 ys 0x000 irmovl 10 edx 0x006 irmovl 3 eax 0x00c addl edx eax 0x00e halt 1 2 3 4 5 6 7 8 F D F E D F M E D F W M E D W M E W M W Cycle 4 M M valE 10 M dstE edx E Wow we really missed the boat here e valE 0 3 3 E dstE eax D valA R edx 0 valB R eax 0 Error 12 Predicting the PC D M icode M Bch M valA W icode W valM icode ifun rA rB valC valP Predict PC Need valC Instr valid Need regids Split Split PC PC increment increment Align Align Byte 0 Bytes 1 5 Instruction Instruction memory memory Select PC F predPC Start fetch of new instruction after current one has completed fetch stage Not enough time to reliably determine next instruction Guess which instruction will follow Recover if prediction was incorrect 13 Our Prediction Strategy Instructions that Don t Transfer Control Predict next PC to be valP Always reliable Call and Unconditional Jumps Predict next PC to be valC destination Always reliable Conditional Jumps Predict next PC to be valC destination Only correct if branch is taken Typically right 60 of time Return Instruction Don t try to predict 14 Recovering from PC Misprediction M icode M Bch M valA W icode W valM D icode ifun rA rB valC …