Chapter — Advanced microarchitecture

1.Where the in-order pipeline runs out of road

2.Deeper pipelines & µops

2.1Adding stages

Splitting "EX" into two shorter EX stages means each stage's combinational delay halves ⇒ T_c halves ⇒ frequency doubles.

2.2Cracking instructions into µops

x86: add  [rax+8], rbx     ; one ISA instruction
                              ↓ decode
     µop1: load tmp, [rax+8]
     µop2: add  tmp, tmp, rbx
     µop3: store [rax+8], tmp

The pipeline now schedules µops, not ISA instructions. RISC-V has fewer cracks needed (most ops are already simple), but even RISC cores µ-op load-with-immediate-offset or fused branches.

3.Branch prediction

3.1Static vs dynamic

3.21-bit predictor

Each branch stores one bit: "predict taken" (1) or "predict not taken" (0). Flip on a wrong guess.

3.32-bit saturating predictor

Two bits, four states. Need two consecutive wrongs to flip the predicted direction. One wrong only weakens it.

3.4Worked example — 7-iteration do-while loop

3.4.1GQ Q9 — 100-iteration loop with 2-bit predictor

addi x2, x0, 100
loop:
    addi x2, x2, -1
    bne  x2, x0, loop   # taken 99 times, not-taken on iter 100

4.Superscalar — issuing more than one per cycle

4.1In-order superscalar — same pipe, doubled lanes

An N-wide in-order superscalar fetches N instructions per cycle and feeds them through N parallel pipelines that still preserve program order.

4.2The new constraints

• Intra-bundle hazards: the two instructions issued together can't share a structural unit (only one load-store unit, etc.) and can't depend on each other (the producer wouldn't have finished yet).
• RAW with the previous bundle: if instruction N+1 needs the result of N from the previous cycle, it stalls at Issue (IS) until the value is ready.
• In-order: instruction N+1 cannot pass N even if N+1's operands are ready and N's aren't. That's the killer.

4.3Worked example — 2-wide IO superscalar IPC

I1: lw  x1, 0(x10)
I2: lw  x2, 4(x10)
I3: add x3, x1, x2     ← needs x1, x2
I4: mul x4, x3, x5     ← needs x3
I5: add x6, x4, x2     ← needs x4
I6: add x3, x7, x5     ← independent

5.Out-of-order — letting independent instructions overtake

5.1The three sections of an OoO core

5.2New pipeline stages introduced

The 5-stage RISC pipeline expands into something like:

5.3Why WAR & WAW return — and renaming kills them

In our 5-stage in-order pipe, WAR and WAW were silent because instructions wrote registers in order. The moment we let instructions complete out of order, a younger instruction can finish writing x1 before an older one reads it. That's a WAR. If both write x1, that's a WAW.

6.Register renaming — the hazard solver

6.1Architectural vs physical registers

6.2Renaming walkthrough

lw x1, 0(x10)   →  lw p20, 0(p10)     ; allocate new physreg p20 for x1
lw x2, 4(x10)   →  lw p21, 4(p10)     ; allocate new physreg p21 for x2

add x3, x1, x2  →  add p22, p20, p21  ; reads the NEW p20/p21
mul x4, x3, x5  →  mul p23, p22, p5   ; chains to p22 (true RAW)

6.3Why RAW still survives

In the example above, mul reads p22 which add just wrote. That's a real data dependency — mul can't execute until add's result lands in p22. Renaming gave us fresh names, but it can't invent data out of thin air.

7.The Reorder Buffer (ROB)

7.1How it works

1. When the front-end dispatches an instruction, it allocates a new ROB entry at the tail, in program order.
2. The instruction executes whenever its operands are ready (OoO). Its result lands in its physical register and a "done" flag flips in its ROB entry.
3. The head of the ROB is the oldest in-flight instruction. Each cycle, if the head is done, it commits (retires) — its architectural state becomes visible.
4. If the head is a mispredicted branch or an exception, the entire ROB after the head is flushed: physregs are freed, the rename map is rolled back, fetch restarts.

7.2When the ROB stalls issue

The dispatch stage can't allocate a new ROB entry when the buffer is full. With 96 entries and 4-wide issue: 96/4 = 24 cycles. After that, every cycle has to wait for a commit at the head to free a slot.

7.3Mispredict / exception recovery

Because the ROB commits in order, the architectural state is always a correct prefix of the program. On any speculative failure (wrong branch, page fault, divide-by-zero), the ROB just throws away everything past the offending instruction. The hardware looks like nothing speculative ever happened.

8.OoO performance calculations

8.12-wide pipe IPC with RAW stalls

I1: lw  x1, 0(x10)
I2: lw  x2, 4(x10)
I3: add x3, x1, x2
I4: mul x4, x3, x5
I5: add x6, x4, x2
I6: add x3, x7, x5     ← totally independent — can run early

8.2Distinct physical registers for a renamed sequence

add x5, x1, x2     ; x5 → p_new_1   (1st write to x5 since initial map)
add x5, x5, x3     ; x5 → p_new_2
mul x7, x5, x4     ; reads p_new_2
add x5, x6, x8     ; x5 → p_new_3
sub x9, x5, x10    ; reads p_new_3

8.3Cycles until the ROB blocks issue

Next: Memory Systems → (the other half of the CPU performance story)