Pipelining: Stages, Hazards, Forwarding and Branch Prediction

Why pipelining matters

Pipelining is the technique of overlapping the execution of several instructions, each at a different step, so that the processor finishes roughly one instruction every clock cycle instead of one every several cycles. Every modern processor, from microcontrollers to server chips, is pipelined. It is the single most important idea for understanding processor performance after the CPU time equation.

Pipelining is also one of the most heavily tested topics in computer architecture: written tests love numerical problems on speedup and stalls, and interviewers probe whether you understand why the ideal speedup is never reached. Expect questions on:

• the five-stage pipeline and what each stage does,
• speedup, throughput and latency calculations, including unequal stage delays and latch overhead,
• structural, data and control hazards, and the RAW/WAR/WAW classification,
• forwarding and the load-use hazard, drawn as pipeline diagrams,
• branch handling: static prediction, delayed branches, 1-bit and 2-bit dynamic predictors, and the branch target buffer,
• why deeper pipelines eventually stop helping.

The laundry analogy

Suppose doing a load of laundry has three steps: wash (30 minutes), dry (40 minutes) and fold (20 minutes). You have 4 loads.

Sequentially, you finish one load completely before starting the next: 4 × (30 + 40 + 20) = 4 × 90 = 360 minutes.

Pipelined, you put load 2 in the washer as soon as load 1 moves to the dryer. Each machine works on a different load at the same time. But the dryer is the slowest step, so loads queue for it:

Time (min): 0    30   60   90   120  150  170  190  210
            |----|----|----|----|----|----|----|----|
Load 1:     WASH  DRY-----FOLD
Load 2:          WASH .. DRY-----FOLD
Load 3:               WASH ...... DRY-----FOLD
Load 4:                    WASH ......... DRY-----FOLD

Load 1: wash 0-30,   dry 30-70,   fold 70-90
Load 2: wash 30-60,  dry 70-110,  fold 110-130
Load 3: wash 60-90,  dry 110-150, fold 150-170
Load 4: wash 90-120, dry 150-190, fold 190-210

Total: 210 minutes, versus 360. Three lessons appear already:

1. Pipelining does not make one load faster. Each load still needs at least 90 minutes (load 4 takes 120 minutes from start to finish because of waiting). It improves throughput, the rate at which loads finish.
2. The slowest stage sets the pace. Once the pipeline is full, one load finishes every 40 minutes (the dryer time), not every 30.
3. Filling and draining cost time. At the start the dryer and folder sit idle; at the end the washer does.

The five-stage RISC pipeline

A classic RISC processor splits each instruction into five stages, matching the five steps you saw in the datapath lesson:

Between each pair of stages sits a pipeline register (latch): IF/ID, ID/EX, EX/MEM and MEM/WB. At every clock edge, each stage passes its results to the next stage through these registers, so each instruction carries its own operands and control signals with it as it moves down the pipe.

        +----+   +----+   +----+   +-----+   +----+
  PC -->| IF |-->| ID |-->| EX |-->| MEM |-->| WB |
        +----+ ^ +----+ ^ +----+ ^ +-----+ ^ +----+
               |        |        |         |
           IF/ID    ID/EX    EX/MEM    MEM/WB   pipeline registers

The pipeline diagram

A pipeline diagram (space-time diagram) shows which stage each instruction occupies in each clock cycle. Rows are instructions, columns are cycles.

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

Read it column by column: in cycle 5, five different instructions are in five different stages, and the pipeline is full. From then on, one instruction finishes every cycle.

The total time for n instructions in a k-stage pipeline with no stalls is

Cycles = k + (n - 1)

The first instruction takes k cycles to come out; each of the remaining n - 1 follows one cycle later. Above, 5 + 4 = 9 cycles for 5 instructions.

Speedup, throughput and CPI

Let:

• k = number of stages,
• n = number of instructions,
• t_ns = time for one instruction on the non-pipelined machine,
• τ (tau) = pipeline clock period.

Then:

Non-pipelined time = n x t_ns
Pipelined time     = (k + n - 1) x τ
Speedup            = (n x t_ns) / ((k + n - 1) x τ)

Ideal case: stages perfectly balanced (t_ns = k × τ) and no latch overhead:

Speedup = (n x k) / (k + n - 1)   ->   k   as n grows large

So the ideal speedup equals the number of stages. For 8 instructions on 5 stages, speedup = 40 / 12 = 3.33; for a million instructions it is essentially 5.

Throughput is instructions completed per unit time: about 1 / τ once the pipeline is full. Ideal CPI for a pipeline is 1: each instruction still takes k cycles of latency, but one completes every cycle.

Latency of one instruction is k × τ, which is never shorter than on a non-pipelined machine, and usually slightly longer because of latch overhead and imbalance.

Why real speedup is lower

Three things pull speedup below k:

1. Unequal stage delays: the clock must fit the slowest stage, so faster stages wait.
2. Latch overhead: each pipeline register adds setup time and clock-to-output delay, plus clock skew, to every cycle.
3. Hazards: stalls add cycles beyond the ideal CPI of 1.

Worked example 1: unequal stages and latch overhead

A non-pipelined processor executes each instruction through five steps taking 200, 150, 250, 200 and 100 ps. It is pipelined into five stages with those delays, and each pipeline register adds 20 ps. Find the clock period, the time for 1,000 instructions on each design, and the speedup.

1. Non-pipelined time per instruction = 200 + 150 + 250 + 200 + 100 = 900 ps (no latches needed between steps).
2. Pipeline clock = slowest stage + latch overhead = 250 + 20 = 270 ps.
3. Non-pipelined, 1,000 instructions = 1,000 × 900 = 900,000 ps (900 ns).
4. Pipelined, 1,000 instructions = (5 + 1,000 − 1) × 270 = 1,004 × 270 = 271,080 ps (about 271 ns).
5. Speedup = 900,000 / 271,080 ≈ 3.32.
6. Limit as n grows = 900 / 270 ≈ 3.33, well below the ideal 5.

Where did the rest go? A perfectly balanced 5-stage split of 900 ps would give 180 ps stages, a 200 ps clock with latches, and a limit of 900 / 200 = 4.5. Imbalance (the 250 ps stage) costs the rest. Latency of one instruction rises from 900 ps to 5 × 270 = 1,350 ps.

Worked example 2: a four-stage pipeline

A four-stage pipeline has stage delays of 60, 50, 90 and 80 ns, and the interface latch delay is 10 ns. How long do 1,000 tasks take, and what is the speedup over a non-pipelined unit?

1. Clock = max(60, 50, 90, 80) + 10 = 100 ns.
2. Pipelined time = (4 + 1,000 − 1) × 100 = 1,003 × 100 = 100,300 ns.
3. Non-pipelined time per task = 60 + 50 + 90 + 80 = 280 ns; for 1,000 tasks = 280,000 ns.
4. Speedup = 280,000 / 100,300 ≈ 2.79 (limit 280 / 100 = 2.8).

Pipeline hazards

A hazard is a situation that prevents the next instruction from executing in its scheduled cycle. There are three kinds.

Structural hazards

A structural hazard occurs when two instructions need the same hardware in the same cycle.

Example: with a single memory for both instructions and data, a load in its MEM stage and a later instruction in its IF stage both need memory in the same cycle. One must wait.

Cycle:      1    2    3    4    5    6
lw         IF   ID   EX   MEM  WB
I2              IF   ID   EX   MEM  WB
I3                   IF   ID   EX   MEM
I4                        --   IF   ID     (IF stalls: memory busy with lw's MEM)

Fixes: duplicate the resource (separate instruction and data caches, which is why L1 caches are split), or pipeline the resource. The register file avoids a structural hazard between WB and ID by writing in the first half of the cycle and reading in the second half.

Data hazards

A data hazard occurs when an instruction depends on the result of an earlier instruction that has not yet finished. Data hazards are classified by the order of accesses, for an earlier instruction i and a later instruction j:

In the simple in-order five-stage pipeline, only RAW hazards occur: all reads happen in ID and all writes in WB, in program order. WAR and WAW hazards appear in pipelines where instructions can complete out of order (variable-length execution units, out-of-order processors). They are name dependences, caused by reusing a register name rather than by real data flow, and register renaming removes them.

Control hazards

A control hazard (branch hazard) occurs when the pipeline does not yet know which instruction to fetch next because a branch has not been resolved. If the branch outcome is known only in EX (cycle 3 of the branch), two instructions have already been fetched from the fall-through path. They may be wrong.

Stalls and bubbles

The simplest fix for any hazard is to stall: hold the dependent instruction (and those behind it) in place while the earlier instruction makes progress. The hardware inserts a bubble, a do-nothing operation (effectively a nop), into the following stage. Each bubble costs one cycle.

Example: RAW hazard without forwarding

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

add writes x1 in WB (cycle 5). sub reads x1 in ID. With write-first-half/read-second-half, sub's ID can happen in cycle 5 at the earliest.

Cycle:            1    2    3    4    5    6    7    8
add x1,x2,x3     IF   ID   EX   MEM  WB
sub x4,x1,x5          IF   ID*  ID*  ID   EX   MEM  WB
                           (bubble)(bubble)

ID* means the instruction sits in ID, stalled. Two bubbles flow down the pipe behind add. Cost: 2 stall cycles. (Without the split-cycle register file, it would be 3.)

Forwarding (bypassing)

Look closely: add computes x1 at the end of its EX stage (cycle 3). sub needs the value at the start of its EX stage (cycle 4). The value exists; it just has not been written to the register file yet.

Forwarding (or bypassing) adds wires and multiplexers that route a result directly from a pipeline register (EX/MEM or MEM/WB) to the ALU inputs, skipping the register file.

Cycle:            1    2    3    4    5    6
add x1,x2,x3     IF   ID   EX   MEM  WB
                             \
                              v  (EX/MEM -> ALU input)
sub x4,x1,x5          IF   ID   EX   MEM  WB

Zero stalls. A forwarding unit compares the destination register in EX/MEM and MEM/WB with the source registers of the instruction in EX:

if EX/MEM.RegWrite and EX/MEM.rd != 0 and EX/MEM.rd == ID/EX.rs1:
    forward EX/MEM result to ALU input A
else if MEM/WB.RegWrite and MEM/WB.rd != 0 and MEM/WB.rd == ID/EX.rs1:
    forward MEM/WB result to ALU input A
(same checks for rs2 and input B)

The EX/MEM check comes first because it holds the most recent value when both stages write the same register. The rd != 0 test is there because x0 is always zero in RISC-V.

The load-use hazard

Forwarding cannot fix everything. A load gets its data only at the end of MEM. If the very next instruction needs it at the start of EX, the value is needed one cycle before it exists. Time cannot run backward, so one stall is unavoidable.

lw  x1, 0(x2)
add x3, x1, x4

Cycle:            1    2    3    4    5    6    7
lw  x1,0(x2)     IF   ID   EX   MEM  WB
                                  \
                                   v (MEM/WB -> ALU input)
add x3,x1,x4          IF   ID   ID*  EX   MEM  WB
                                (bubble)

Cost: 1 stall cycle with forwarding (it would be 2 without forwarding). A hazard detection unit in ID spots this case:

if ID/EX.MemRead and (ID/EX.rd == IF/ID.rs1 or ID/EX.rd == IF/ID.rs2):
    stall: hold PC and IF/ID, insert a bubble into ID/EX

Avoiding load-use stalls by scheduling

Compilers reorder instructions so that loaded values are not used immediately. Consider:

a = b + c;
d = e + f;

Naive code (variables addressed from a base register x9):

lw   x1, 0(x9)      # b
lw   x2, 4(x9)      # c
add  x3, x1, x2     # stall: uses x2 right after its load
sw   x3, 8(x9)      # a
lw   x4, 12(x9)     # e
lw   x5, 16(x9)     # f
add  x6, x4, x5     # stall: uses x5 right after its load
sw   x6, 20(x9)     # d

Two load-use stalls. Total cycles = 5 + 8 − 1 + 2 = 14.

Scheduled code: move the load of e up, and interleave:

lw   x1, 0(x9)      # b
lw   x2, 4(x9)      # c
lw   x4, 12(x9)     # e
add  x3, x1, x2     # x2 loaded 2 instructions earlier: forwarded, no stall
lw   x5, 16(x9)     # f
sw   x3, 8(x9)      # a
add  x6, x4, x5     # x5 loaded 2 instructions earlier: no stall
sw   x6, 20(x9)     # d

No stalls. Total = 5 + 8 − 1 = 12 cycles, about 14% fewer. This is why compilers need to know the target pipeline, and why using more registers (to hold several values at once) helps.

Worked example 3: CPI with stalls

A program has 20% loads, and half of them are immediately followed by an instruction that uses the loaded value. 15% of instructions are branches; the predictor is wrong 10% of the time, and each misprediction costs 2 cycles. With full forwarding, what is the effective CPI?

CPI = ideal CPI + load-use stalls + branch stalls
    = 1 + (0.20 x 0.5 x 1) + (0.15 x 0.10 x 2)
    = 1 + 0.10 + 0.03
    = 1.13

The pipeline delivers 1 / 1.13 ≈ 88% of its ideal throughput. The speedup over a non-pipelined machine becomes pipeline depth / CPI in the balanced ideal case, for example 5 / 1.13 ≈ 4.4 instead of 5.

General formula:

Speedup = Pipeline depth / (1 + stall cycles per instruction)
          (assuming balanced stages and no latch overhead)

Handling control hazards

Branches are frequent (often around 15 to 20% of instructions in integer code), so how the pipeline handles them matters a lot.

Stall until resolved

Simplest: stop fetching after a branch until its outcome is known. If the branch resolves in EX, that costs 2 cycles per branch. If 20% of instructions are branches with a 3-cycle penalty, CPI = 1 + 0.2 × 3 = 1.6: a 60% slowdown.

Resolving earlier helps: moving the comparison and target calculation into ID (with a dedicated comparator and adder) cuts the penalty to 1 cycle, at the cost of extra hardware and new data hazards in ID.

Static prediction

Static prediction uses a fixed rule decided before the program runs.

• Predict not taken: keep fetching sequentially. If the branch turns out taken, flush (discard) the wrongly fetched instructions, converting them into bubbles. No penalty when the prediction is right.
• Predict taken: useful only if the target is known early.
• Backward taken, forward not taken (BTFN): branches that jump backward are usually loop branches and are usually taken; forward branches (if-statements) are often not taken.
• Compiler hints: some ISAs let the compiler mark a branch as likely or unlikely (C programmers can pass hints with __builtin_expect in GCC and Clang).

Example: with 20% branches, a 3-cycle penalty and predict-not-taken where 60% of branches are taken: CPI = 1 + 0.2 × 0.6 × 3 = 1.36.

Delayed branch

A delayed branch changes the ISA rule: the instruction immediately after the branch (in the branch delay slot) always executes, whether or not the branch is taken. The compiler tries to fill the slot with a useful instruction, typically one from before the branch that the branch does not depend on.

Before:                     After filling the delay slot:
  add  x5, x6, x7             beq  x1, x2, target
  beq  x1, x2, target         add  x5, x6, x7     # delay slot
  ...                         ...

If nothing useful can be moved, the compiler inserts a nop. Classic MIPS and SPARC used one delay slot. The idea fits short, simple pipelines; with deep pipelines and multi-issue processors the penalty is many cycles, a single slot no longer covers it, and the slot becomes awkward legacy baggage. Modern ISAs such as RISC-V and AArch64 do not use delay slots.

Dynamic branch prediction

Dynamic prediction uses hardware that learns each branch's behavior at run time.

1-bit predictor

A branch history table (BHT) (or pattern history table) is a small table indexed by low bits of the branch's address. Each entry holds 1 bit: the last outcome. Predict that the branch will do what it did last time.

Its weakness shows on loops. Consider an inner loop that runs 4 iterations each time it is entered, so its branch produces the repeating pattern T T T N (taken three times, then not taken to exit). Start with the entry set to T.

5 mispredictions in 12. In steady state, 2 per loop execution: once at the exit (predicted T, actual N), and again on re-entry (the bit now says N, but the loop branch is taken). Accuracy 50% on this pattern.

2-bit saturating counter

A 2-bit saturating counter has four states. It must be wrong twice in a row to change its prediction.

 Taken outcome (T) moves right, not-taken outcome (N) moves left;
 the ends saturate (T at 11 stays 11, N at 00 stays 00).

    N          N          N          N
  <----      <----      <----      <----
 +------+   +------+   +------+   +------+
 |  00  |   |  01  |   |  10  |   |  11  |
 |strong|   | weak |   | weak |   |strong|
 |not tk|   |not tk|   |taken |   |taken |
 +------+   +------+   +------+   +------+
  ---->      ---->      ---->      ---->
    T          T          T          T
 predict: N         N          T          T

In words, as a counter from 0 to 3: on taken, add 1 (stop at 3); on not taken, subtract 1 (stop at 0). Predict taken if the counter is 2 or 3, not taken if 0 or 1. "Saturating" means it sticks at the ends instead of wrapping.

Same T T T N pattern, starting at 11 (strongly taken):

Step by step for the first loop: three T outcomes keep the counter at 3. The N is mispredicted and drops it to 2, which still predicts taken. On re-entry, the next T is predicted correctly and moves it back to 3.

1 misprediction per loop execution, 3 in 12: accuracy 75%, versus 50% for the 1-bit scheme. The single loop exit no longer flips the prediction.

You can reproduce both traces:

pattern = ['T', 'T', 'T', 'N'] * 3

bit, miss1 = 'T', 0              # 1-bit: remember last outcome
for actual in pattern:
    miss1 += bit != actual
    bit = actual

ctr, miss2 = 3, 0                # 2-bit saturating counter, start strongly taken
for actual in pattern:
    pred = 'T' if ctr >= 2 else 'N'
    miss2 += pred != actual
    ctr = min(3, ctr + 1) if actual == 'T' else max(0, ctr - 1)

print(miss1, miss2)  # 5 3

Beyond 2-bit counters

Real processors go further. Correlating (two-level) predictors use the outcomes of recent branches (global history) as part of the table index, because branches often depend on each other (if (x > 0) followed later by if (x > 5)). Tournament predictors pick between a local and a global predictor per branch. Modern high-performance cores use sophisticated history-based designs (TAGE-style and perceptron-style predictors are well-known research designs) that reach well above 90% accuracy on typical programs. The exact designs in commercial chips are largely undisclosed.

Branch target buffer

Predicting the direction is not enough: to fetch the right instruction in the next cycle, the fetch stage must also know the target address before the branch is even decoded. A branch target buffer (BTB) is a small cache, indexed by the PC of the instruction being fetched, that stores the target addresses of previously taken branches.

            PC of instruction being fetched
                         |
      +------------------+------------------+
      |  Tag (branch PC) | Predicted target | (+ prediction bits)
      +------------------+------------------+
      |  0x400120        |   0x400080       |
      |  0x4002A4        |   0x400310       |
      +------------------+------------------+
           match and predicted taken?
             yes -> next PC = predicted target
             no  -> next PC = PC + 4

In the IF stage, the PC is looked up in the BTB. On a hit with a "taken" prediction, the next fetch comes from the stored target, so a correctly predicted taken branch costs zero cycles. If the prediction turns out wrong, the pipeline flushes the wrongly fetched instructions and restarts from the correct address.

Two related structures:

• A return address stack (RAS) predicts targets of function returns by pushing the return address on each call, since a return's target changes with each caller and a BTB predicts it poorly.
• Indirect branch predictors handle jumps through registers (virtual function calls, switch tables).

Worked example 4: misprediction cost

A processor resolves branches 3 cycles after fetch. Branches are 20% of instructions. Compare: (a) always stall, (b) predict not taken with 60% of branches taken, (c) a dynamic predictor that is right 90% of the time (with a BTB, so correctly predicted taken branches cost nothing).

(a) CPI = 1 + 0.20 x 3        = 1.60
(b) CPI = 1 + 0.20 x 0.60 x 3 = 1.36
(c) CPI = 1 + 0.20 x 0.10 x 3 = 1.06

Dynamic prediction recovers most of the lost performance: relative to (a), (c) is 1.60 / 1.06 ≈ 1.51 times faster.

Exceptions in a pipeline

When an instruction causes an exception (for example a page fault in MEM), later instructions are already in earlier stages. To keep the exception precise, the pipeline flushes the faulting instruction and everything after it, lets earlier instructions complete, saves the faulting instruction's PC, and jumps to the handler. Exceptions are typically recorded as the instruction moves down the pipe and acted on at a single point (late in the pipeline), so they are handled in program order.

Limits of pipelining

Why not use 100 stages? Several forces push back:

1. Latch overhead: each stage adds a fixed register delay. As stages get shorter, the overhead becomes a larger fraction of the cycle.
2. Imbalance: some operations cannot be split evenly.
3. Hazard penalties grow: a deeper pipeline means more cycles between fetch and branch resolution (larger misprediction penalty) and between producing and using values (more stalls).
4. Power: more pipeline registers and higher clock rates mean more power; after the end of Dennard scaling, power is the binding constraint.
5. Clock skew and wiring: distributing a very fast clock across a chip becomes harder.

Superpipelining

Superpipelining means splitting the classic stages further into a deeper pipeline with a shorter clock period. Using the 900 ps instruction from worked example 1, with 20 ps latch overhead and perfectly balanced stages:

Doubling the depth from 10 to 20 raises speedup by only about 69%, before counting larger hazard penalties. In practice, a historical example is Intel's Pentium 4 (NetBurst), whose very deep pipeline (about 20 stages, and around 31 in later versions) reached high clock rates but suffered large misprediction penalties and high power, and the next generation returned to a shorter pipeline. Most current high-performance cores use pipelines in the mid-teens of stages.

Interview questions

Q1. Does pipelining reduce the execution time of a single instruction?

No. Each instruction still passes through every stage, and latch overhead and stage imbalance usually make its latency slightly longer. Pipelining increases throughput by overlapping instructions, so the program as a whole finishes faster.

Q2. What is the ideal speedup of a k-stage pipeline and why is it not achieved?

For n instructions, speedup = nk / (k + n − 1), which approaches k for large n. It is not achieved because stages are unbalanced (the clock fits the slowest), pipeline registers add overhead to every cycle, and hazards cause stalls that push CPI above 1.

Q3. A 5-stage pipeline has stage delays 200, 150, 250, 200 and 100 ps with 20 ps latches. What is the clock and the speedup for 1,000 instructions?

The clock is 250 + 20 = 270 ps. Pipelined time = (5 + 999) × 270 = 271,080 ps; non-pipelined = 1,000 × 900 = 900,000 ps. Speedup ≈ 3.32, approaching 3.33 for very large n.

Q4. Name the three types of hazards.

Structural hazards occur when two instructions need the same hardware at once, fixed by duplicating resources. Data hazards occur when an instruction needs a result not yet produced, fixed by forwarding, stalling or scheduling. Control hazards occur when the next instruction depends on an unresolved branch, fixed by prediction, early resolution or delay slots.

Q5. Explain RAW, WAR and WAW hazards. Which occur in the classic 5-stage pipeline?

RAW (read after write) is a true dependence where a later instruction reads a value before an earlier one writes it. WAR (write after read) and WAW (write after write) are name dependences where a later write could clobber a value an earlier instruction still reads or writes. The in-order 5-stage pipeline reads in ID and writes in WB in order, so only RAW occurs; WAR and WAW appear with out-of-order completion and are removed by register renaming.

Q6. What is forwarding and when does it fail?

Forwarding routes a result from the EX/MEM or MEM/WB pipeline register directly to the ALU inputs of a later instruction, avoiding a wait for write-back. It removes most RAW stalls between ALU instructions. It fails for a load followed immediately by a use, because the loaded value appears only at the end of MEM, one cycle too late, so one stall remains.

Q7. How many stall cycles does a load-use hazard cost, with and without forwarding?

With forwarding, one stall cycle; the value is forwarded from MEM/WB to the dependent instruction's EX. Without forwarding, but with a register file that writes in the first half and reads in the second half of the cycle, two stall cycles. Compilers schedule an independent instruction between the load and its use to hide the stall.

Q8. What is a pipeline bubble?

A bubble is an empty slot, effectively a no-op, inserted into a pipeline stage when an instruction must be held back. The hazard detection unit holds the PC and IF/ID register and zeroes the control signals entering ID/EX. Each bubble adds one cycle to execution time.

Q9. Compare 1-bit and 2-bit branch predictors.

A 1-bit predictor remembers the last outcome, so a loop branch is mispredicted twice per loop execution: at the exit and again on re-entry. A 2-bit saturating counter must be wrong twice in a row to flip, so the loop exit costs only one misprediction. For a loop of 4 iterations, accuracy rises from 50% to 75%.

Q10. What is a branch target buffer?

It is a cache indexed by the fetch PC that stores the targets of previously taken branches, often with prediction bits. During IF, a hit with a "taken" prediction redirects the next fetch to the stored target, so correctly predicted taken branches cost no cycles. Returns use a return address stack instead, since their targets vary.

Q11. What is a delayed branch and why do modern ISAs avoid it?

The instruction after a branch, in the delay slot, always executes, and the compiler fills the slot with useful work. It hid a one-cycle branch penalty in short pipelines like early MIPS. In deep or superscalar pipelines the penalty is many cycles, one slot no longer helps, and the rule complicates the hardware forever, so RISC-V and AArch64 dropped it in favor of dynamic prediction.

Q12. Calculate the CPI if 20% of instructions are loads, half followed by a dependent instruction, and 15% are branches mispredicted 10% of the time with a 2-cycle penalty.

CPI = 1 + 0.2 × 0.5 × 1 + 0.15 × 0.1 × 2 = 1 + 0.10 + 0.03 = 1.13. With balanced stages the speedup over a non-pipelined design is about 5 / 1.13 ≈ 4.4 for a 5-stage pipeline.

Q13. Why can't we keep deepening pipelines?

Latch overhead becomes a larger share of each shrinking cycle, branch misprediction and data hazard penalties grow with depth, and power rises with more registers and higher clock rates. Beyond some depth the extra stalls and power outweigh the faster clock. The Pentium 4's very deep pipeline is a well-known example of hitting these limits.

Q14. How does the register file avoid a structural hazard between ID and WB?

The register file is written in the first half of the clock cycle and read in the second half. An instruction in WB and another in ID can therefore use it in the same cycle, and the reader even sees the newly written value. Separate read and write ports provide the hardware for this.

Q15. What is the difference between superpipelining and superscalar execution?

Superpipelining splits work into more, shorter stages to raise the clock rate, still issuing about one instruction per cycle. Superscalar processors issue several instructions per cycle using multiple parallel pipelines or functional units, allowing CPI below 1. Modern cores combine both with out-of-order execution.

Key takeaways

• Pipelining overlaps instructions to raise throughput; latency per instruction does not improve.
• n instructions on k stages take k + n − 1 cycles; ideal speedup is nk / (k + n − 1), approaching k.
• The clock is the slowest stage plus latch overhead; unequal stages and latches cut real speedup well below k.
• Hazards are structural (shared hardware), data (RAW true dependences; WAR/WAW name dependences only with out-of-order completion) and control (branches).
• Forwarding removes most RAW stalls; a load immediately followed by its use still costs one stall, which compiler scheduling can hide.
• Effective CPI = 1 + stall cycles per instruction; compute each stall source as frequency × fraction affected × penalty.
• Branches: stall, predict statically, use delay slots (legacy), or predict dynamically. A 2-bit saturating counter mispredicts a loop branch once per loop execution, versus twice for 1-bit.
• A branch target buffer supplies target addresses at fetch time so correctly predicted taken branches cost nothing.
• Deeper (superpipelined) designs face diminishing returns from latch overhead, bigger hazard penalties and power.

Next lesson

Continue with Cache memory.