Module Outline:
• Pipelined Data Path Design
• Pipelined Control Path Design • Hazards
• Exception Handling
Module 1: Pipelining
Pipelining is Natural
Sequential Laundry
Pipelined Laundry: Start Work ASAP
Pipelining Lessons
The Five Stages of Load
• Ifetch: Instruction Fetch
– fetch the instruction from the instruction memory
• Reg/Dec: Registers Fetch and Instruction Decode • Exec: Calculate the memory address
• Mem: Read the data from the Data Memory
• Wr: Write the data back to the register file
NOTE: These 5 Stages Were There All Along!
P1: P2: P3: P4:
1 2 3 4 5 6 7 8 1234567 123456 12345
P5: Time
1234 12345678
Pipelining
• As the instruction execution cycle uses different hardware components for different steps, it is possible to set up a pipeline.
P1 P2 P3 P4 P5
Instruction fetch unit
Instruction Address analyzer calculation
Data fetch unit
Instruction execution unit
unit
• Suppose each stage takes 1 nsec. Then each instruction still takes 5 nsec. But once the pipeline has been filled, a complete instruction rolls out every 1 nsec. Thus, the speedup is 5.
• The pipeline rate is limited by the slowest pipeline stage.
Pipelining
• Pipelining is an implementation technique whereby multiple instructions are overlapped in execution.
• Pipelining is the key implementation technique that is currently used to make high- performance CPUs.
• Pipelining does not help to lower the latency of a single instruction, but it helps to increase the throughput of the entire program execution.
• The principle: multiple independent tasks are operating simultaneously.
• Potential speedup = number of pipeline stages.
• Unbalanced lengths of pipeline stages reduce the speedup: that is, the key is every stage should have the same duration.
• The time needed to “fill” the pipeline and the time needed to “drain” it reduces the speedup.
Pipelining in the CPU
• Pipelining is an implementation technique that exploits parallelism among instructions in a sequential instruction stream.
• A major advantage of pipelining over “parallel processing” is that it is not visible to the programmer (whereas in parallel processing, the program usually needs to specify what kinds of tasks to be executed in parallel).
• In a computer system, each pipeline stage completes a part of the instruction being executed.
• The time required between moving an instruction one step down the pipeline is a machine cycle (the clock cycle). The length of a machine cycle is determined by the time required for the slowest stage to proceed.
• The computer engineer should try to balance the length of each pipeline stage so as to achieve the ideal speedup. In practice, however, the pipeline stages will not be perfectly the same, and there are additional overheads. But we can get close to the ideal case.
Design Issues:
Pipelining in the CPU (continued)
• We have to make sure that the same resource (e.g., ALU) is not used in more than one pipeline stage.
• If the resources used in the same pipelining stage are different, then overlapping is possible.
• However, we must note that to retain the intermediate values produced by an
individual instruction for all its pipeline stages, we must include temporary registers
between the pipeline stages.
Program
e x e c u tio n
order
(in instructions)
Tim e (in clock cycles)
CC1 CC2 CC3 CC4 CC5 CC6 CC7
lw $1,100($0)
IM Reg
ALU DM Reg
lw $2,200($0)
IM
Reg ALU DM Reg
lw $3,300($0)
IM Reg ALU DM Reg
Performance of Pipelining
• Pipelining increases the processor instruction throughput—the number of instructions completed per unit time.
• Remember: pipelining does not reduce the execution time of a single instruction.
• The increase in instruction throughput means that the program runs faster, even though no single instruction runs faster.
• Imbalance among the pipeline stages reduces performance since the clock cannot run faster than the time needed for the slowest pipeline stage.
• Pipelining overhead can arise from the combination of pipeline register delay and other factors.
Graphically Representing Pipelines
• Can help with answering questions like:
– how many cycles does it take to execute this code? – what is the ALU doing during cycle 4?
– use this representation to help understand datapaths
Conventional Pipelined Execution Representation
Single Cycle, Multiple Cycle, vs. Pipeline
• Suppose we execute 100 instructions • Single Cycle Machine
Why Pipelining Actually?
– 45 ns/cycle x 1 CPI x 100 instructions = 4500ns • Multi-Cycle Machine
– 10 ns/cycle x 4.6 CPI (due to instruction mix) x 100 instructions = 4600ns • Ideal pipelined machine
– 10 ns/cycle x (1 CPI x 100 instructions + 4 cycles drain) = 1040ns!!
Why Pipeline? Because We Can!
YES: Pipeline Hazards
– branch instructions
Can Pipelining Get Us into Trouble?
• Structural Hazards: attempt to use the same resource in two different ways (e.g., by two different instructions) at the same time
– e.g., combined washer/dryer would be a structural hazard or “folder” busy doing something else (e.g., watching TV 😉
• Control Hazards: attempt to make a decision before condition is evaluated
– e.g., washing football uniforms and need to get proper detergent level; need to see after dryer before next load in
• 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
• Can always resolve these hazards by waiting (pipeline stall):
– pipeline control must detect the hazard
– take action (or delay action) to resolve hazards
Single Memory Is a Structural Hazard
Structural Hazard Limits Performance
• Example: If 1.3 memory accesses per instruction, and only one memory access per cycle then:
– average CPI >= 1.3
– otherwise resource is more than 100% utilized (impossible!)
Control Hazard Solution #1: Stall
Control Hazard Solution #2: Predict
Control Hazard Solution #3: Delayed Branch
Data Hazard on r1: Read After Write (RAW)
add r1, r2, r3 sub r4, r1, r3 and r6, r1, r7 or r8, r1, r9 xor r10, r1, r11
Data Hazard on r1: Read After Write (RAW)
Data Hazard Solution: Forwarding
Forwarding (or Bypassing): What About Loads?
Forwarding (or Bypassing): What About Loads?
Designing a Pipelined Processor
• Go back and examine your datapath and control diagram
• Associate resources with states
• Ensure that flows do not conflict, or figure out how to resolve • Assert control in appropriate stage
Control and Datapath: Split State Diagram into 5 Pieces
• Utilize capabilities of the datapath
• What makes it easy
Summary of Concepts
• Reduce CPI by overlapping many instructions
– average throughput of approximately 1 CPI with fast clock
– start next instruction while working on the current one – limited by length of longest stage (plus fill/flush)
– detect and resolve hazards
– all instructions are of the same length
– just a few instruction formats
– memory operands appear only in loads and stores
• What makes it hard?
– structural hazards: suppose we had only one memory
– control hazards: need to worry about branch instructions
– data hazards: an instruction depends on a previous instruction
Pipelined Processor
Pipelining the Load Instruction
• The 5 independent functional units in the pipeline datapath are:
– instruction memory for the Ifetch stage
– register file’s Read ports (bus A and bus B) 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 stage
The 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 file
Pipelining 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 port
Important Observation
• Each functional unit can only be userd once per instruction
• Each functional unit must be used at the same stage for all instructions
• 2 ways to solve this pipeline hazard
Solution 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!!
Solution 2: Delay R-type’s Write by One Cycle
• Delay R-type’s register write by one cycle:
Modified Control and Datapath
The 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 memory
The 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 operands – select correct branch target address – latch into PC
Control Diagram
Data Stationary Control
Datapath + Data Stationary Control
Let’s Try It Out
Start: Fetch 10
Fetch 14, Decode 10
Fetch 20, Decode 14, Exec 10
Fetch 24, Decode 20, Exec 14, Mem 10
Fetch 30, Decode 24, Exec 20, Mem 14, WB 10
Fetch 100, Decode 30, Exec 24, Mem 20, WB 14
Fetch 104, Decode 100, Exec 30, Mem 24, WB 20
Fetch 110, Decode 104, Exec 100, Mem 30, WB 24
Fetch 114, Decode 110, Exec 104, Mem 100, WB 30
Pipeline Hazards Again
• Avoid some “by design”
Data Hazards
– eliminate WAR by always fetching operands early (DCD) in pipe – eliminate WAW by doing all WBs in order (last stage, static)
• Detect and resolve remaining ones – stall or forward (if possible)
Hazard Detection
• Suppose instruction i is about to be issued and a predecessor instruction j is in the instruction pipeline
• A RAW hazard exists on register ρ if ρ ∈ Rregs(i) ∩ Wregs(j)
– keep a record of pending writes (for instructions in the pipe) and compare with operand regs of current instruction
– when instruction issues, reserve its result register
– when on operation completes, remove its write reservation
• A WAW hazard exists on register ρ if ρ ∈ Wregs(i) ∩ Wregs(j)
• A WAR hazard exists on register ρ if ρ ∈ Wregs(i) ∩ Rregs(j)
Record of Pending Writes
Resolve RAW by Forwarding
– R1 <-- R4 + R5
- R2 <-- Mem[R2 + I]
- R3 <-- R2 + R1
- ==> delayed loads
What about Memory Operations?
•If instructions are initiated in order and operations always occur in the same stage, there can be no hazards between memory operations!
• What does delaying WB on arithmetic operations cost?
– cycles?
– hardware?
• What about data dependence on loads?
• Can recognize this in decode stage and introduce bubble while stalling fetch stage
• Tricky situation:
– R1 <-- Mem[R2 + I]
- Mem[R3 + 34] <-- R1
Handle with bypass in memory stage!
Compiler Avoiding Load Stalls
• External interrupts:
What about interrupts, traps, faults?
- allow pipeline to drain
- load PC with interrupt address
• Faults (within instruction, restartable)
- force trap instruction into IF
- disable writes till trap hits WB
- must save multiple PCs or PC + state
• Recall: precise exceptions ==> state of the machine is preserved as if program executed up to the offending instruction
– all previous instructions completed
– offending instruction and all following instructions act as if they have not even started – same system code will work on different implementations
– how to stop the pipeline? – restart?
– who caused the interrupt?
Exception Problem
• Exceptions/Interrupts: 5 instructions executing in 5 stage pipeline
Stage Problem when interrupts occur
IF page fault on instruction fetch; misaligned memory access; memory- protection violation
ID undefined or illegal opcode
EX arithmetic exception
MEM page fault on data fetch; misaligned memory access; memory-
• Load with data page fault, Add with instruction page fault?
• Solution
1: interrupt vector/instruction
2: interrupt ASAP, restart everything incomplete
protection violation; memory error
Another look at the exception problem
• Use pipeline to sort this out!
– pass exception status along with instruction
– keep track of PCs for every instruction in pipeline – don’t act on exception until it reaches WB stage
• Handle interrupts through “faulting no-op” in IF stage • When instruction reaches WB stage:
– save PC => EPC, interrupt vector address => PC – turn all instructions in earlier stages into no-ops
Exception Handling
Resolution: Freeze above & Bubble below
FYI: MIPS R3000 Clocking Discipline
MIPS R3000 Instruction Pipeline
Recall: Data Hazard on r1
MIPS R3000 Multicycle Operations
Issues in Pipelined Design
• What makes it easy
Summary of Concepts
– all instructions are the same length
– just a few instruction formats
– memory operands appear only in loads and stores
• What makes it hard? HAZARDS!!
– structural hazards: suppose we had only one memory
– control hazards: need to worry about branch instructions
– data hazards: an instruction depends on a previous instruction
• Pipelines pass control information down the pipe just as data moves down pipe
• Forwarding/stalls handled by local control
• Exceptions stop the pipeline
• Pipelines pass control information down the pipe just as data moves down pipe
• Forwarding/stalls handled by local control
• Exceptions stop the pipeline
• MIPS I instruction set architecture made pipeline visible (delayed branch, delayed load)
• More performance from deeper pipleines, parallelism
Is CPI = 1 for our pipeline?
• Remember that CPI is an “average # cycles/instruction”
• CPI here is 1, since the average throughput is 1 instruction every cycle • What if there are stalls or multi-cycle execution?
• Usually CPI > 1. How close can we get to 1??
• 8 stage pipeline:
Case Study: MIPS R4000 (200 MHz)
– IF—first half of fetching of instruction; PC selection happens here as well as initiation of instruction cache access
– IS—second half of access to instruction cache
– RF—instruction decode and register fetch, hazard checking and also instruction cache hit
detection
– EX—execution, which includes effective address calculation, ALU operation, and
branch target computation and condition evaluation
– DF—data fetch, first half of access to data cache
– DS—second half of access to data cache
– TC—tag check, determine whether the data cache access hit
– WB—write back for loads and register-register operations
• 8 stages: what is the impact on Load delay? Branch delay? Why?
Case Study: MIPS R4000
MIPS R4000 Floating Point
• FP adder, FP multiplier, FP divider
• Last step of FP multiplier/divider uses FP adder HW • 8 kinds of stages in FP units:
MIPS FP Pipe Stages
R4000 Performance
• Hazards limit performance
Summary of Concepts
– structural: need more HW resources
– data: need forwarding, compiler scheduling
– control: early evaluation and PC, delayed branch, prediction
• Data hazards must be handled carefully:
– RAW data hazards handled by forwarding
– WAW and WAR hazards don’t exist in 5-stage pipeline
• MIPS I instruction set architecture made pipeline visible (delayed branch, delayed load)
• Exceptions in 5-stage pipeline recorded when they occur, but acted on only at WB (end of MEM) stage
– must flush all previous instructions
• More performance from deeper pipelines, parallelism