Superscalar execution

What Makes a Processor Superscalar?

The Width Parameter

The issue width N determines how many instructions can be dispatched per cycle. Common values:

2-way superscalar: 2 instructions/cycle (older Intel Pentium)
4-way superscalar: 4 instructions/cycle (Intel Core)
6-8 way superscalar: Modern high-performance cores (Intel Skylake, AMD Zen)

How Superscalar Execution Works: The Pipeline Stages

1. Instruction Fetch (Width N)

What happens: Fetch N instructions from the cache in one cycle.

Why it's hard: The instruction stream isn't always aligned nicely. If you need to fetch 4 instructions but they span a cache-line boundary, you might need two cache accesses.

How it's solved:

Wide instruction cache ports
Branch predictors that predict multiple branches ahead
Instruction bufers to queue fetched instructions

2. Decode (Width N)

What happens: Decode N instructions simultaneously into micro-ops.

Why it's hard: x86 instructions have variable length (1-15 bytes). Finding instruction boundaries for multiple instructions in parallel is complex.

How it's solved:

Pre-decode bits added to cache lines
Complex decoders for the first few positions
Simpler decoders for remaining positions
Micro-op cache (decoded instruction cache) in modern designs

3. Rename and Dispatch

What happens: Rename architectural registers to physical registers to eliminate false dependencies, then dispatch to reservation stations.

The problem this solves:

ADD R1, R2, R3  ; R1 = R2 + R3
MUL R4, R1, R5  ; R4 = R1 * R5  (needs R1, has RAW dependency)
ADD R1, R6, R7  ; R1 = R6 + R7  (WAW hazard with first instruction)
SUB R8, R1, R9  ; R8 = R1 - R9  (which R1? WAR hazard)

Rename solution:

ADD P10, P2, P3   ; Rename R1 → P10
MUL P11, P10, P5  ; Uses P10, can execute when P10 ready
ADD P12, P6, P7   ; Rename R1 → P12 (different physical register!)
SUB P13, P12, P9  ; Uses P12, no confusion

Now instructions1 and 3 don't have a false dependency—they write to different physical registers.

4. Issue (Out-of-Order)

What happens: Instructions wait in reservation stations until their operands are ready, then issue to execution units.

Key insight: Instructions don't issue in program order. They issue when:

Functional unit available
All source operands ready
No structural hazards

This is out-of-order execution.

5. Execute (Multiple Units)

What happens: Multiple functional units execute instructions in parallel.

A typical superscalar might have:

4 integer ALUs
2 load/store units (AGU + data port)
2 floating-point units
1 branch unit

Throughput vs Latency:

Integer ADD: 1 cycle latency, 4/cycle throughput (4 units)
Integer MUL: 3 cycle latency, 1/cycle throughput (1 unit)
FP DIV: 20 cycle latency, 1/20 cycle throughput (1 unit, not pipelined)

6. Retire (In-Order, Width N)

What happens: The reorder buffer (ROB) ensures instructions commit their results in program order, maintaining precise exceptions.

Why in-order retirement: If an exception occurs, all instructions before the faulting instruction must complete, and all after must not have visible effects.

Derivation: Maximum IPC

Let's derive the theoretical maximum instructions per cycle (IPC).

Given:

Issue width: $W$
Number of functional units: $F_i$ of type $i$
Instruction mix: fraction $p_i$ requires unit type $i$
Average instruction latency: $L$

Step 1: Maximum fetch/decode rate = $W$ instructions/cycle

Step 2: Maximum issue rate limited by dependencies. With perfect register renaming and infinite ROB, limited by: $\text{Issue rate} \leq \min(W, \text{functional unit throughput})$

Step 3: Functional unit throughput: For unit type $i$ with $F_i$ units: $\text{Throughput}_i = F_i \text{ instructions/cycle}$

Step 4: Overall throughput considering instruction mix: If fraction $p_i$ of instructions need unit type $i$ : $\text{IPC}_{\text{max}} = \min\left(W, \min_i \frac{F_i}{p_i}\right)$

Why this step?: If50% of instructions are loads/stores ( $p_{\text{mem}} = 0.5$ ) and you have 2 load/store units ( $F_{\text{mem}} = 2$ ), then memory operations limit you to $\frac{2}{0.5} = 4$ IPC maximum.

Step 5: Dependency limit. If average dependency chain length is $D$ and latency is $L$ : $\text{IPC}_{\text{dependency}} \leq \frac{W \cdot \text{Window size}}{D \cdot L}$

Final formula: $\boxed{\text{IPC} = \min\left(W, \min_i \frac{F_i}{p_i}, \frac{W \cdot ROB\_size}{D \cdot L_{\text{avg}}}\right)}$

Worked example Worked Example:4-way Superscalar IPC

Given:

4-way superscalar ( $W = 4$ )
3 integer ALUs, 2 FPUs, 2 load/store units
Instruction mix: 40% integer, 20% FP, 30% load/store, 10% branch
Average dependency chain: 3 instructions
ROB size: 128 entries
Average latency: 2 cycles Solution: Fetch/decode limit: 4 instructions/cycle Functional unit limits:
Integer: $\frac{3}{0.4} = 7.5$ IPC
FP: $\frac{2}{0.2} = 10$ IPC
Memory: $\frac{2}{0.3} = 6.67$ IPC
Branch: $\frac{1}{0.1} = 10$ IPC

Minimum FU limit = 6.67 IPC Dependency limit: $\frac{4 \times 128}{3 \times 2} = \frac{512}{6} = 85.3 \text{ IPC}$ (Dependencies don't limit us with a large ROB)

Final IPC: $\min(4, 6.67, 85.3) = 4$ IPC

Why? The fetch/decode width of 4 is the bottleneck. We have enough functional units and a large enough window to hide dependencies. A wider design would help.

Critical Structures for Superscalar

Reorder Buffer (ROB)

What: Circular buffer tracking in-flight instructions in program order.

Why: Enables out-of-order execution with in-order retirement (precise exceptions).

How: Each ROB entry contains:

PC of instruction
Destination register (logical)
Result value or pointer to physical register
Status (pending/complete)
Exception flags

Size matters: $\text{Max instructions flight} = \text{ROB size}$

Larger ROB → more instructions to search for independent work → higher IPC, but more complex hardware.

Register Alias Table (RAT)

What: Maps architectural registers to physical registers.

Size: For $R$ architectural registers and $P$ physical registers:

RAT entries: $R$ (one per architectural register)
Each entry: $\lceil \log_2 P \rceil$ bits

Why: Eliminates WAW and WAR hazards, enabling more paralelism.

Example: x86-64 has 16 integer registers. A modern design might have 180 physical registers. $\text{RAT size} = 16 \times \lceil \log_2 180 \rceil = 16 \times 8 = 128 \text{ bits}$

Reservation Stations

What: Buffers holding instructions waiting for operands.

Why: Decouple instruction issue from execution, allowing instructions to wait without blocking dispatch.

Key property: Instructions wake up when their last operand becomes ready (associative search).

Limitations and Tradeoffs

Common mistake Common Misconception: "N-way superscalar gives N× speedup"

Why it feels right: If you can do N things at once, you should get N times faster.

Why it's wrong:

Dependencies: True RAW dependencies limit paralelism. Long dependency chains serialize execution.
Structural hazards: Not enough functional units for instruction mix.
Control hazards: Branches interrupt the instruction stream.
Memory bottlenecks: Cache misses stall everything.

Reality: A 4-way superscalar typically achieves 2-3 IPC on real code (50-75% efficiency).

Steel-man the mistake: The N× assumption is valid for embarrassingly parallel workloads with no dependencies, like SIMD vector operations. But control flow code has inherent dependencies.

The fix: Understand that IPC is limited by the instruction stream's inherent paralelism, not just hardware width. Amdahl's Law applies: if only 50% of code can run parallel, even infinite width gives at most 2× speedup.

Recall Explain Superscalar to a 12-Year-Old

Imagine you're doing homework. You have multiple problems to solve: math problems, reading comprehension, and drawing a picture.

Normal computer (scalar): You have one desk. You do one problem at a time. Math problem → reading → drawing → next math problem. You have to finish each before starting the next.

Pipelined computer: You still do one at a time, but as soon as you finish reading the math problem, you can read the next one while solving the first. Like an assembly line.

Superscalar computer: Now you have THREE desks and three copies of you! One can do math, one can read, and one can draw—all at the same time! But there's a catch: if the drawing requires the answer from the math problem, you have to wait. Also, you only have one pencil sharpener, so if all three of you need to sharpen pencils, two have to wait.

That's superscalar: doing multiple things at once, but only when they don't depend on each other and you have enough tools for everyone.

Connections

Instruction-Level Parallelism: Superscalar is the primary technique for exploiting ILP
Register Renaming: Essential for eliminating false dependencies
Out-of-Order Execution: Superscalar processors typically execute OoO
Branch Prediction: Critical for keeping the pipeline fed with instructions
Tomasulo's Algorithm: Classic dynamic scheduling algorithm for superscalar
Reorder Buffer: Maintains precise exceptions in out-of-order superscalar
VLIW Architecture: Alternative approach where compiler does instruction scheduling
Cache Hierarchy: Must provide sufficient bandwidth for multiple memory ops/cycle
Power-Performance Tradeoffs: Wider superscalar means more power consumption

#flashcards/hardware

What is a superscalar processor? :: A processor that can fetch, decode, and execute multiple instructions simultaneously in the same clock cycle using multiple functional units and dynamic scheduling.

What are the three types of data dependencies?

RAW (Read After Write - true dependency), WAW (Write After Write - false/output dependency), WAR (Write After Read - false/anti-dependency).

How does register renaming eliminate false dependencies?

By mapping architectural registers to a larger pool of physical registers, so two instructions writing to the same architectural register actually write to different physical registers, eliminating WAW and WAR hazards.

What is the purpose of the Reorder Buffer (ROB)?

To track in-flight instructions in program order and ensure they retire (commit) in order, maintaining precise exceptions even though execution is out-of-order.

Why is in-order retirement necessary in superscalar processors?

To maintain precise exceptions—if an exception occurs, all instructions before the faulting instruction must complete and all after must not have visible architectural effects.

What limits the IPC of a superscalar processor?

The minimum of: fetch/decode width, functional unit throughput per instruction type, and the instruction window size divided by average dependency chain length times latency.

What is the issue width of a superscalar processor?

The maximum number of instructions that can be dispatched to functional units in a single clock cycle (e.g., 4-way superscalar can issue 4 instructions/cycle).

How do reservation stations enable out-of-order execution? :: They buffer instructions waiting for operands and issue them to functional units as soon as operands become ready and units are available, decoupling dispatch from execution.

What is the difference between throughput and latency for functional units?

Latency is how many cycles one operation takes; throughput is how many operations per cycle the processor can start (can be higher than 1/latency with multiple units or pipelining).

Why don't N-way superscalar processors achieve N× speedup?

Due to true data dependencies, control hazards (branches), structural hazards (limited functional units), and memory bottlenecks—real code achieves 50-75% efficiency.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Superscalar execution ka matlab hai ki processor ek sath multiple instructions ko handle kar sakta hai—same clock cycle mein! Socho jaise highway pek lane ke bajaye 4 lanes hain, toh 4 gadiyan sath mein chal sakti hain. Normal processor (scalar) ek hi instruction process karta hai per cycle, lekin superscalar 4-way processor 4 instructions ko simultaneously fetch, decode, aur execute kar sakta hai. Iska result? Theoretically 4× zyada throughput!

Lekin practical mein itna simple nahi hai. Hardware ko register renaming karni padti hai taki false dependencies (WAW, WAR) hat jayein. Phir out-of-order execution hoti hai—instructions ready hone pe execute ho jati hain, program order mein nahi. Multiple ALUs, FPUs, aur load/store units parallel mein kaam karte hain. Lekin end mein Reorder Buffer (ROB) ensure karta hai ki results program order mein hi commit hon, taki exceptions precise rahein.

Ek badi challenge: real code mein dependencies bohot hoti hain (RAW hazards), branches interrupt karte hain, aur memory bottlenecks aa jate hain. Isliye 4-way superscalar typically sirf 2-3 IPC (instructions per cycle) achieve karta hai real applications pe, 4 nahi. Industry mein balance banana padta hai—kitne functional units, kitna bada ROB, kitna power consumption. Modern Intel aur AMD processors 4 se 8-way superscalar hote hain with hundreds of physical registers for renaming, enabling high performance without crazy high clock speeds.

Samajhne ki key baat: superscalar hardware complexity badha kar instruction-level parallelism (ILP) exploit karta hai jo code mein naturally available hai, lekin actual speedup code ki inherent paralelism pe depend karta hai, sirf hardware width pe nahi.

What Makes a Processor Superscalar?

The Width Parameter

How Superscalar Execution Works: The Pipeline Stages

1. Instruction Fetch (Width N)

2. Decode (Width N)

3. Rename and Dispatch

4. Issue (Out-of-Order)

5. Execute (Multiple Units)

6. Retire (In-Order, Width N)

Derivation: Maximum IPC

Critical Structures for Superscalar

Reorder Buffer (ROB)

Register Alias Table (RAT)

Reservation Stations

Limitations and Tradeoffs

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced Microarchitecture

Connections