Page 1Advanced PipeliningCS740October 30, 2007Topics• Data Hazards– Stalling and Forwarding– Systematic testing of hazard-handling logic• Control Hazards– Stalling, Predict not taken• Exceptions• Multicycle InstructionsCS 740 F ’07–2–Alpha ALU InstructionsOp ra rb funct rc31-26 25-21 20-16 15-13 11-5 4-0RR-type instructions (addq, subq, xor, bis, cmplt): rc <-- ra funct rb000 012Op ra ib funct rc31-26 25-21 20-13 11-5 4-0RI-type instructions (addq, subq, xor, bis, cmplt): rc <-- ra funct ib112Encoding• ib is 8-bit unsigned literalOperation Op field funct fieldaddq 0x10 0x20subq 0x10 0x29bis 0x11 0x20xor 0x11 0x40cmoveq 0x11 0x24cmplt 0x11 0x4DCS 740 F ’07–3–Pipelined ALU Instruction DatapathIFinstruction fetchIDinstruction decode/register fetchMEMmemoryaccessEXexecuteWBwrite backPCInstr. Mem.Reg. ArrayregAregBregWdatWdatAdatBALU25:2120:16+4Data Mem.datInaddrdatOutaluAaluBIncrPCInstr4:0WdestWdata20:13IF/ID ID/EX EX/MEM MEM/WBAdataALUoutCS 740 F ’07–4–Data Hazards in Alpha PipelineProblem• Registers read in ID, and written in WB• Must resolve conflict between instructions competing for register array– Generally do write back in first half of cycle, read in second• But what about intervening instructions?• E.g., suppose initially $2 is zero:IF ID EX M WBIF ID EX M WBIF ID EX M WBIF ID EX M WBIF ID EX M WBaddq $31, 63, $2addq $2, 0, $3addq $2, 0, $4addq $2, 0, $5addq $2, 0, $6$2$3$4$5$6Time$2 writtenPage 2CS 740 F ’07–5–Handling Hazards by StallingIdea• Delay instruction until hazard eliminated• Put “bubble” into pipeline– Dynamically generated NOPPipe Register Operation• “Transfer” (normal operation) indicates should transfer next state to current• “Stall” indicates that current state should not be changed• “Bubble” indicates that current state should be set to 0– Stage logic designed so that 0 is like NOP– [Other conventions possible]StallBubbleCurrentStateNextStateTransferCS 740 F ’07–6–Detecting DependenciesPending Register Reads• By instruction in ID• ID_in.IR[25:21]: Operand A• ID_in.IR[20:16]: Operand B–Only for RRPCInstr.Mem.Reg.ArrayregAregBregWdatWdatAdatBALU25:2120:16+4DataMem.datInaddrdatOutaluAaluBIncrPCInstr4:0WdestWdata20:13IF/ID ID/EX EX/MEM MEM/WBAdataALUoutWDstWDstWDstPending Register Writes• EX_in.WDst: Destination register of instruction in EX• MEM_in.WDst: Destination register of instruction in MEMRead SourcesRead SourcesWrite Dests.Write Dests.CS 740 F ’07–7–Implementing StallsStall Control Logic• Determines which stages to stall, bubble, or transfer on next updateRule:• Stall in ID if either pending read matches either pending write– Also stall IF; bubble EXEffect• Instructions with pending writes allowed to complete before instruction allowed out of IDInstr.Mem.Reg.FileDataMem.IF ID EX MEMStall ControlStall Stall Bubble Transfer TransferCS 740 F ’07–8–Stalling for Data HazardsOperation• First instruction progresses unimpeded• Second waits in ID until first hits WB• Third waits in IF until second allowed to progressIF ID EX M WBIFIDEX M WBIF ID EX M WBIF ID EX M WBIF ID EX M WBaddq $31, 63, $2addq $2, 0, $3addq $2, 0, $4addq $2, 0, $5addq $2, 0, $6$2$3$4$5$6Time$2 writtenIDIDIF IFPage 3CS 740 F ’07–9–Observations on StallingGood• Relatively simple hardware• Only penalizes performance when hazard existsBad• As if placed NOPs in code– Except that does not waste instruction memoryReality• Some problems can only be dealt with by stalling– Instruction cache miss– Data cache miss• Otherwise, want technique with better performanceCS 740 F ’07–10–Forwarding (Bypassing)Observation• ALU data generated at end of EX– Steps through pipe until WB• ALU data consumed at beginning of EXIdea• Expedite passing of previous instruction result to ALU• By adding extra data pathways and controlCS 740 F ’07–11–Forwarding for ALU InstructionsOperand Destinations• ALU input A–Register EX_in.ASrc• ALU input B–Register EX_in.BSrcOperand Sources• MEM_in.ALUout– Pending write to MEM_in.WDst• WB_in.ALUout– Pending write to WB_in.WDstPCInstr.Mem.Reg.ArrayregAregBregWdatWdatAdatBALU25:2120:16+4DataMem.datInaddrdatOutaluAaluBIncrPCInstr4:0WdestWdata20:13IF/ID ID/EX EX/MEM MEM/WBAdataALUoutWDstASrcBSrcWDstWDst25:2120:16PCInstr.Mem.Reg.ArrayregAregBregWdatWdatAdatBALU25:2120:16+4DataMem.datInaddrdatOutaluAaluBIncrPCInstr4:0WdestWdata20:13IF/ID ID/EX EX/MEM MEM/WBAdataALUoutWDstASrcBSrcWDstWDst25:2120:16CS 740 F ’07–12–Bypassing PossibilitiesEX-EX• From instruction that just finished EXMEM-EX• From instruction that finished EX two cycles earlierPCInstr.Mem.Reg.ArrayregAregBregWdatWdatAdatBALU25:2120:16+4DataMem.datInaddrdatOutaluAaluBIncrPCInstr4:0WdestWdata20:13IF/ID ID/EX EX/MEM MEM/WBAdataALUoutWDstASrcBSrcWDstWDst25:2120:16PCInstr.Mem.Reg.ArrayregAregBregWdatWdatAdatBALU25:2120:16+4DataMem.datInaddrdatOutaluAaluBIncrPCInstr4:0WdestWdata20:13IF/ID ID/EX EX/MEM MEM/WBAdataALUoutWDstASrcBSrcWDstWDst25:2120:16EX-EXMEM-EXPage 4CS 740 F ’07–13–Bypassing Data HazardsOperation• First instruction progresses down pipeline• When in MEM, forward result to second instruction (in EX)–EX-EX forwarding• When in WB, forward result to third instruction (in EX)–MEM-EX forwardingIF ID EX M WBIF ID EX M WBIF ID EX M WBaddq $31, 63, $2addq $2, 0, $3 # EX-EXaddq $2, 0, $4 # MEM-EXaddq $2, 0, $5addq $2, 0, $6$2$3$4$5$6Time$2 writtenIF ID EX M WBIF ID EX M WBCS 740 F ’07–14–Load & Store InstructionsLoad: Ra <-- Mem[Rb +offset]31-26 25-21 20-16 15-0Op ra rb offsetID: Instruction decode/register fetch• Store: A <-- Register[IR[25:21]]• B <-- Register[IR[20:16]]MEM: Memory• Load: Mem-Data <-- DMemory[ALUOutput]• Store: DMemory[ALUOutput] <-- AWB: Write back• Load: Register[IR[25:21]] <-- Mem-DataStore: Mem[Rb +offset] <-- Ra31-26 25-21 20-16 15-0Op ra rb offsetCS 740 F ’07–15–Analysis of Data TransfersData Sources• Available after EX– ALU Result Reg-Reg Result• Available after MEM–Read Data Load result– ALU Data Reg-Reg Result passing through MEM stageData Destinations• ALU A input Need in EX– Reg-Reg or Reg-Immediate Operand• ALU B input Need in EX– Reg-Reg Operand– Load/Store Base• Write Data Need in MEM– Store DataCS 740 F ’07–16–Some Hazards with Loads & StoresData Generated by LoadLoad-ALUldq $1, 8($2)addq $2, $1, $2Load-Store Dataldq $1, 8($2)stq $1,
View Full Document
Unlocking...