University

Pipelining

Pipelining

Course: Computer Architectures
Type: Concept

1. What pipelining is

Pipelining overlaps the execution of multiple instructions.

Different stages work on different instructions at the same time.

A typical five-stage pipeline is:

IF  = Instruction Fetch
ID  = Instruction Decode / Register Fetch
EX  = Execute / Effective Address
MEM = Memory Access / Branch Completion
WB  = Write Back

Example:

Cycle:  1   2   3   4   5   6   7
 
I1      IF  ID  EX MEM  WB
I2          IF  ID  EX MEM  WB
I3              IF  ID  EX MEM  WB
I4                  IF  ID  EX MEM  WB

2. Throughput and CPI

Pipelining mainly increases throughput.

It does not necessarily make a single instruction finish faster.

CPI = clock cycles per instruction

In an ideal filled pipeline:

CPI ≈ 1

The clock period is limited by the slowest stage.

3. Pipeline registers

Typical pipeline registers:

IF/ID
ID/EX
EX/MEM
MEM/WB

They preserve intermediate results between stages.

4. Pipeline hazards

A hazard prevents an instruction from executing in its intended cycle.

Three main classes:

Structural hazard -> hardware resource conflict
Data hazard       -> needed value is not ready
Control hazard    -> next PC is not known yet

5. Stall and bubble

A stall temporarily stops instructions from advancing.

A stall creates a bubble, an empty slot in the pipeline.

6. Structural hazards

A structural hazard occurs when two operations need the same hardware resource at the same time.

Example:

Instruction A needs memory for MEM
Instruction B needs memory for IF

If there is only one memory port, one must wait.

Possible solutions:

- more hardware
- duplicated resources
- stall

7. Data hazards

Example:

add x1, x2, x3
sub x4, x1, x5

The sub needs the new x1, but the add may not have written it back yet.

8. Forwarding

Forwarding sends a result directly to the instruction that needs it instead of waiting for WB.

ADD ALU result ─────→ SUB ALU input

This avoids many stalls.

9. Load-use hazard

Example:

lw  x1, 0(x2)
sub x4, x1, x5

The loaded value becomes available too late for the immediately following instruction.

So a stall is required:

lw   IF ID EX MEM WB
sub     IF ID -- EX MEM WB
               ↑
             stall

10. How a load-use stall is inserted

The control logic can:

- freeze the PC
- freeze IF/ID
- insert a nop into ID/EX

In RISC-V:

nop

corresponds to:

addi x0, x0, 0

11. Control hazards

Control hazards are caused by branches and jumps.

The problem: later instructions may already have been fetched before the processor knows the correct next PC.

12. Taken vs untaken branch

For:

beq x1, x2, target

Taken:

x1 == x2
PC = target

Not taken:

x1 != x2
PC = PC + 4

13. Why a taken branch can cost cycles

In the basic pipeline from the lecture, the branch outcome is known late enough that two following instructions can already be in the pipeline.

Branch        IF ID EX
Branch + 1       IF ID
Branch + 2          IF

If the branch is taken, those later instructions are wrong-path instructions and must be discarded.

14. Flush

A flush discards instructions fetched from the wrong path.

They can effectively be replaced with nop operations.

15. Branch-management techniques

The lecture presents four approaches:

1. Freeze the pipeline
2. Predict untaken
3. Predict taken
4. Delayed branch

16. Freeze the pipeline

When a branch is detected, stop and wait until the branch decision is known.

Advantage:

simple

Disadvantage:

lost cycles

17. Predict untaken

Assume the branch will not be taken.

Continue fetching sequential instructions:

PC + 4
PC + 8
...

If wrong, flush the incorrectly fetched instructions.

18. Predict taken

Assume the branch will be taken.

Start fetching from the target as early as possible.

If wrong, flush the target-path instructions and resume from PC + 4.

19. Compiler role and loops

A loop branch is often taken many times and not taken once at the end.

Example:

loop:
    ...
    bne x1, x0, loop

Typical pattern:

taken
taken
taken
...
not taken

The compiler can arrange code to better match a processor’s prediction strategy.

20. Delayed branch

A delayed branch uses the instruction slot after a branch for useful work.

Example:

beq  x1, x2, target
addi x5, x5, 1

The compiler must ensure the delay-slot instruction is safe regardless of the branch outcome.

This technique becomes less attractive in deeper pipelines.

Summary

Structural = resource problem
Data       = value not ready
Control    = next PC unknown

Graph View

Backlinks