10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.1CS152Computer Architecture and EngineeringLecture 14Pipelining Control ContinuedIntroduction to Advanced PipeliningOctober 19, 2001John Kubiatowicz (http.cs.berkeley.edu/~kubitron)lecture slides: http://www-inst.eecs.berkeley.edu/~cs152/10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.2Recap: Summary of Pipelining Basics° 5 stages:• Fetch: Fetch instruction from memory• Decode: get register values and decode control information• Execute: Execute arithmetic operations/calculate addresses• Memory: Do memory ops (load or store)• Writeback: Write results back to registers (I.e. COMMIT)° Pipelines pass control information down the pipe just as data moves down pipe° Forwarding/Stalls handled by local control° Balancing length of instructions makes pipelining much smoother° Increasing length of pipe increases impact of hazards; pipelining helps instruction bandwidth, not latency10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.3Recap: Can pipelining get us into trouble?° Yes: Pipeline Hazards• structural hazards: attempt to use the same resource two different ways at the same time- E.g., combined washer/dryer would be a structural hazard or folder busy doing something else (watching TV)• data hazards: attempt to use item before it is ready- E.g., one sock of pair in dryer and one in washer; can’t fold until get sock from washer through dryer- instruction depends on result of prior instruction still in the pipeline• control hazards: attempt to make a decision before condition isevaulated- E.g., washing football uniforms and need to get proper detergent level; need to see after dryer before next load in- branch instructions° Can always resolve hazards by waiting• pipeline control must detect the hazard• take action (or delay action) to resolve hazards10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.4Pipelining the Load Instruction° The five independent functional units in the pipelinedatapath are:• Instruction Memory for the Ifetch stage• Register File’s Read ports (bus A and busB) for the Reg/Dec stage• ALU for the Exec stage• Data Memory for the Mem stage• Register File’s Write port (bus W) for the Wr stageClockCycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7Ifetch Reg/Dec Exec Mem Wr1st lwIfetch Reg/Dec Exec Mem Wr2nd lwIfetch Reg/Dec Exec Mem Wr3rd lw10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.5The Four Stages of R-type° Ifetch: Instruction Fetch• Fetch the instruction from the Instruction Memory° Reg/Dec: Registers Fetch and Instruction Decode° Exec: • ALU operates on the two register operands• Update PC° Wr: Write the ALU output back to the register fileCycle 1 Cycle 2 Cycle 3 Cycle 4Ifetch Reg/Dec Exec WrR-type10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.6Pipelining the R-type and Load Instruction° We have pipeline conflict or structural hazard:• Two instructions try to write to the register file at the same time!• Only one write portClockCycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9Ifetch Reg/Dec Exec WrR-typeIfetch Reg/Dec Exec WrR-typeIfetch Reg/Dec Exec Mem WrLoadIfetch Reg/Dec Exec WrR-typeIfetch Reg/Dec Exec WrR-typeOps! We have a problem!10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.7Important Observation° Each functional unit can only be used once per instruction° Each functional unit must be used at the same stage for all instructions:• Load uses Register File’s Write Port during its 5th stage• R-type uses Register File’s Write Port during its 4th stageIfetch Reg/Dec Exec Mem WrLoad12 345Ifetch Reg/Dec Exec WrR-type12 34° 2 ways to solve this pipeline hazard.10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.8Solution 1: Insert “Bubble” into the Pipeline° Insert a “bubble” into the pipeline to prevent 2 writes at the same cycle• The control logic can be complex.• Lose instruction fetch and issue opportunity.° No instruction is started in Cycle 6!ClockCycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9Ifetch Reg/Dec Exec WrR-typeIfetch Reg/Dec ExecIfetch Reg/Dec Exec Mem WrLoadIfetch Reg/Dec Exec WrR-typeIfetch Reg/Dec Exec WrR-typePipelineBubbleIfetch Reg/Dec Exec Wr10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.9Solution 2: Delay R-type’s Write by One Cycle° Delay R-type’s register write by one cycle:• Now R-type instructions also use Reg File’s write port at Stage 5• Mem stage is a NOOP stage: nothing is being done.ClockCycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9Ifetch Reg/Dec Mem WrR-typeIfetch Reg/Dec Mem WrR-typeIfetch Reg/Dec Exec Mem WrLoadIfetch Reg/Dec Mem WrR-typeIfetch Reg/Dec Mem WrR-typeIfetch Reg/DecExecWrR-type MemExecExecExecExec1234510/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.10Modified Control & DatapathIR <- Mem[PC]; PC <– PC+4;A <- R[rs]; B<– R[rt]S <– A + B;R[rd] <– M;S <– A + SX;M <– Mem[S]R[rd] <– M;S <– A or ZX;R[rt] <– M;S <– A + SX;Mem[S] <- Bif Cond PC < PC+SX;M <– SExecReg. FileMemAccessDataMemABSRegFileEqualPCNext PCIRInst. MemDMM <– S10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.11The Four Stages of Store° Ifetch: Instruction Fetch• Fetch the instruction from the Instruction Memory° Reg/Dec: Registers Fetch and Instruction Decode° Exec: Calculate the memory address° Mem: Write the data into the Data MemoryCycle 1 Cycle 2 Cycle 3 Cycle 4Ifetch Reg/Dec Exec MemStore Wr10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.12The Three Stages of Beq° Ifetch: Instruction Fetch• Fetch the instruction from the Instruction Memory° Reg/Dec: • Registers Fetch and Instruction Decode° Exec: • compares the two register operand, • select correct branch target address• latch into PCCycle 1 Cycle 2 Cycle 3 Cycle 4Ifetch Reg/Dec Exec MemBeq Wr10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.13Control DiagramIR <- Mem[PC]; PC < PC+4;A <- R[rs]; B<– R[rt]S <– A + B;R[rd] <– S;S <– A + SX;M <– Mem[S]R[rd] <– M;S <– A or ZX;R[rt] <– S;S <– A + SX;Mem[S] <- BIf Cond PC < PC+SX;ExecReg. FileMemAccessDataMemABSRegFileEqualPCNext PCIRInst. MemDM <– SM <– SM10/19/01 ©UCB Fall 2001CS152 / Kubiatowicz Lec14.14Administrivia° Updated Lab 5 schedule:• Up there now (sorry about that)• Mail problem 0 to TA by Monday night at Midnight- Evaluation of your partners• Mail Lab 5
View Full Document