Branches and Pipelining

Pipelining

Overlapping instructions:

• Fetch instruction

• Decode instruction

• Calculate operands

• Fetch operands

• Execute instruction

• Write/complete result

Means one instruction is completed each clock cycle

Branching

Branching can cause a pipeline stall - restart overlapping process

Wastes time

Dealing with branching

Delayed branching

Multiple streams

Prefetch Branch target

Loop buffer

Branch prediction

ARM Pipeline

Only fetch, decode, execute

Stalls have lower impact as shorter

Multiple Streams

Have two pipelines

Prefetch each branch into each pipeline

-ve: Leads to bus and register contention

-ve: multiple branches then need more pipelines

Prefetch Branch Target

Target of branch is prefetched in addition to instructions following branch

Keep target until branch is executed

Loop Buffer

Very fast memory stores last N instructions in sequence

Maintained by fetch stage

Check buffer before fetching from memory

Good for small loops or jumps

Branch Prediction

• Static

  • Either assume branch never or always happen

  • Fetch instruction related to assumption

• 'Active'

  • Predict by opcode - some more likely to result in jump than others

  • Uses taken/not taken switch