A pipeline overlaps instructions, but even a perfect one finishes at most one instruction per cycle. In the previous chapter, Handling Hazards: Stalls, Forwarding & Branch Prediction, all our effort went into getting the CPI down to 1. Modern processors do better: a modern laptop core can complete several instructions (4 or more at its peak) in a single cycle. They do it by finding instructions that do not depend on each other and running them at the same time.
Instruction-level parallelism (ILP) is the potential overlap among the instructions of a single program: the extent to which instructions can be executed in parallel without changing the program's result.
Think of a kitchen. One cook following a recipe step by step is a simple processor. A pipeline is the cook starting to chop the next vegetable while the first is frying. A superscalar processor is a kitchen with several cooks who look ahead in the recipe and grab any step whose ingredients are ready. The recipe (the program) is still written as one sequence; the parallelism is found by reading it cleverly.
Once we can start more than one instruction per cycle, the CPI can fall below 1, so we usually talk about its inverse:
IPC (instructions per cycle) = 1 / CPI
A 4-wide superscalar has ideal CPI = 0.25, ideal IPC = 4In this chapter we look at what limits ILP (dependences), how compilers expose it (loop unrolling and scheduling), and how hardware exploits it (superscalar issue, dynamic scheduling, register renaming, speculation), plus the VLIW and superpipelining alternatives.
Dependences: What Stops Instructions Running Together
Two instructions can run in parallel only if neither depends on the other. We met RAW, WAR and WAW in Pipeline Hazards; here we revisit them from the point of view of a processor that wants to run many instructions at once, where WAR and WAW suddenly matter a lot. There are three kinds of dependence.
1. Data Dependence (True Dependence)
Instruction j uses a value produced by instruction i. This is a real flow of information and can never be removed; it can only be made cheaper (by forwarding). It causes RAW (read after write) hazards.
2. Name Dependence
Two instructions use the same register name but no value flows between them:
- Anti-dependence: i reads a register that j later writes. Causes WAR (write after read) hazards if j's write happens too early.
- Output dependence: i and j both write the same register. Causes WAW (write after write) hazards if the writes complete in the wrong order.
Name dependences exist only because the ISA has a limited number of register names. Give one of the instructions a different register and the dependence vanishes. This is the idea behind register renaming.
3. Control Dependence
Instruction j executes only if a branch i goes a particular way. Instructions after a branch cannot simply be executed before the branch is resolved, unless the processor speculates.
Worked Example: Classifying Dependences
I1: add r1, r2, r3
I2: sub r4, r1, r5
I3: mul r1, r6, r7
I4: add r8, r1, r4
I5: sw r8, 0(r2)
I6: lw r4, 4(r2)Checking every pair (and ignoring a pair if a write in between already breaks the link) gives:
| Type | Pair | Register | Why |
|---|---|---|---|
| RAW | I1 → I2 | r1 | I2 reads r1 written by I1 |
| RAW | I2 → I4 | r4 | I4 reads r4 written by I2 |
| RAW | I3 → I4 | r1 | I4 reads the r1 written by I3 (not the one from I1) |
| RAW | I4 → I5 | r8 | The store's data is r8 |
| WAR | I2 → I3 | r1 | I3 must not overwrite r1 before I2 reads it |
| WAR | I4 → I6 | r4 | I6 must not overwrite r4 before I4 reads it |
| WAW | I1 → I3 | r1 | Final r1 must be I3's value |
| WAW | I2 → I6 | r4 | Final r4 must be I6's value |
So: 4 RAW, 2 WAR, 2 WAW. Note that I1 → I4 is not a RAW on r1, because I3 rewrites r1 in between. (In GATE questions, read carefully whether they want such "killed" pairs counted; the usual convention, used here, is not to count them.)
Register Renaming
Rename every destination to a fresh physical register (p1, p2, ...) and update later readers to use the new name:
Original Renamed
I1: add r1, r2, r3 I1: add p1, r2, r3
I2: sub r4, r1, r5 I2: sub p2, p1, r5
I3: mul r1, r6, r7 I3: mul p3, r6, r7
I4: add r8, r1, r4 I4: add p4, p3, p2
I5: sw r8, 0(r2) I5: sw p4, 0(r2)
I6: lw r4, 4(r2) I6: lw p5, 4(r2)All 2 WAR and 2 WAW dependences are gone; only the 4 true RAW dependences remain. Now I1, I3 and I6 have no dependence on any earlier instruction, so a wide processor can start all three in the same cycle. The longest chain left is I1 → I2 → I4 → I5, which sets the minimum time no matter how wide the machine is.
Hardware renaming uses a register alias table (map table) from architectural to physical registers and a free list of physical registers. Modern cores have far more physical registers (often 200 or more) than architectural ones (32 in RISC-V).
Exposing ILP in Software: Loop Unrolling and Scheduling
Inside one loop iteration there is often little parallelism, but different iterations are frequently independent. The compiler can exploit this with loop unrolling: copy the loop body several times, adjust offsets, and use different registers for each copy, so that independent operations from different iterations can be interleaved.
Take this loop, which scales an array of doubles (x1 walks backwards through the array, x2 marks the end, f2 holds the constant):
C: for (i = n - 1; i >= 0; i--) x[i] = x[i] * s;
Loop: fld f0, 0(x1) ; load x[i]
fmul.d f4, f0, f2 ; multiply by s
fsd f4, 0(x1) ; store x[i]
addi x1, x1, -8 ; move to previous element
bne x1, x2, LoopAssume a single-issue pipeline with these stall cycles between a producer and a dependent consumer (all other pairs need no stalls, and branches are predicted correctly):
| Producer | Consumer | Stall cycles |
|---|---|---|
| Load (fld) | FP multiply using the value | 1 |
| FP multiply | Store of the result | 3 |
| Integer ALU (addi) | Branch using the result | 1 |
Step 1: Unscheduled
1 fld f0, 0(x1)
2 stall
3 fmul.d f4, f0, f2
4 stall
5 stall
6 stall
7 fsd f4, 0(x1)
8 addi x1, x1, -8
9 stall
10 bne x1, x2, Loop -> 10 cycles per elementStep 2: Scheduled
Move the addi up into the load's stall slot. The store now executes after x1 has been decremented, so its offset changes from 0 to +8:
1 fld f0, 0(x1)
2 addi x1, x1, -8
3 fmul.d f4, f0, f2
4 stall
5 stall
6 stall
7 fsd f4, 8(x1)
8 bne x1, x2, Loop -> 8 cycles per elementOnly 3 of the 8 cycles (load, multiply, store) do real work on the array; the rest is loop overhead and stalls. One iteration simply does not contain enough independent work to hide a 3-cycle multiply.
Step 3: Unroll 4 Times and Schedule
Unrolling 4 times (assume n is a multiple of 4) gives four independent load-multiply-store chains, each with its own registers, and only one addi and one bne per four elements. Simply unrolling without reordering is 31 cycles (7.75 per element), because each chain still stalls. Interleaving the chains removes every stall:
1 fld f0, 0(x1)
2 fld f4, -8(x1)
3 fld f8, -16(x1)
4 fld f12, -24(x1)
5 fmul.d f1, f0, f2
6 fmul.d f5, f4, f2
7 fmul.d f9, f8, f2
8 fmul.d f13, f12, f2
9 fsd f1, 0(x1) ; f1 ready: 5 + 1 + 3 = 9
10 fsd f5, -8(x1)
11 addi x1, x1, -32
12 fsd f9, 16(x1) ; was -16, +32 after the addi
13 fsd f13, 8(x1) ; was -24, +32 after the addi
14 bne x1, x2, Loop -> 14 cycles for 4 elements = 3.5 per element| Version | Cycles per iteration | Cycles per element | Speedup vs unscheduled |
|---|---|---|---|
| Unscheduled | 10 | 10 | 1.00 |
| Scheduled | 8 | 8 | 1.25 |
| Unrolled x4, not scheduled | 31 | 7.75 | 1.29 |
| Unrolled x4 and scheduled | 14 | 3.5 | 2.86 |
The costs of unrolling: larger code (more instruction-cache pressure), more registers needed (we used 8 FP registers instead of 2), and extra cleanup code when n is not a multiple of the unroll factor.
Superscalar Processors
A superscalar processor fetches, decodes and issues more than one instruction per clock cycle to multiple, parallel execution units. The instructions come from an ordinary sequential program; the hardware decides at run time which of them can go together. An n-way (or n-issue) superscalar can issue up to n instructions per cycle.
2-way superscalar, 5-stage pipeline, no dependences (ideal):
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
I5 IF ID EX MEM WB
I6 IF ID EX MEM WB
^ from here, 2 instructions complete every cycleTo make this work, every stage must be widened: fetch n instructions per cycle, decode n, read 2n registers, have enough ALUs and memory ports, write n results, and check for dependences among all n instructions issued together (the number of comparisons grows roughly as n2).
Ideal Timing Formula
For N independent instructions on a k-stage, m-way superscalar (N a multiple of m):
Cycles = k + N/m - 1 (first group takes k cycles, then one group per cycle)
Example: k = 5, m = 2, N = 100
superscalar : 5 + 50 - 1 = 54 cycles
scalar : 5 + 100 - 1 = 104 cycles
speedup = 104 / 54 = 1.93 (approaches 2 as N grows)Dependences Limit Real Superscalars
Consider an in-order superscalar where a dependent instruction cannot issue in the same cycle as its producer, ALU results can be used in the next cycle, load results 2 cycles after the load issues, and there is only one memory port (at most one load or store per cycle):
I1: lw r1, 0(r10)
I2: lw r2, 4(r10)
I3: add r3, r1, r2
I4: addi r10, r10, 8
I5: sub r4, r3, r5
I6: add r6, r7, r8
I7: or r9, r4, r6
I8: sw r9, 0(r11)| Issue cycle | 1-wide (scalar) | 2-wide, in order |
|---|---|---|
| 1 | I1 | I1 (I2 waits: only one memory port) |
| 2 | I2 | I2 (I3 waits for r2) |
| 3 | (stall) | (stall: r2 not ready) |
| 4 | I3 | I3, I4 |
| 5 | I4 | I5, I6 |
| 6 | I5 | I7 |
| 7 | I6 | I8 |
| 8 | I7 | |
| 9 | I8 | |
| IPC | 8/9 = 0.89 | 8/7 = 1.14 |
Doubling the width gave only 9 → 7 cycles, not 9 → 4.5. The chain I2 → I3 → I5 → I7 → I8 and the single memory port leave little to overlap. Even an out-of-order machine with this one memory port cannot beat 7 cycles here, because that chain is the critical path. More width is useless without enough independent instructions.
Dynamic Scheduling and Out-of-Order Execution
An in-order superscalar stops issuing as soon as one instruction must wait, even if instructions behind it are ready. An out-of-order (OoO) processor fetches and decodes in order, but lets any instruction whose operands are ready execute, then commits results in the original order.
Fetch & decode --> Rename --> Issue queue / --> Execute --> Reorder buffer
(in order) (map table) reservation stations (out of order) commit (in order)
(wait for operands)Scoreboarding (CDC 6600, 1964)
A central scoreboard tracks which functional units are busy and which registers are waiting for results. An instruction is allowed to execute when its operands are ready. Scoreboarding allows out-of-order execution but handles WAR and WAW hazards by stalling, because it does not rename registers.
Tomasulo's Algorithm (IBM 360/91, 1967)
Robert Tomasulo's scheme adds two key ideas:
- Reservation stations in front of each functional unit hold an instruction together with either its operand values or the tag of the reservation station that will produce each missing value. Because operands are captured by tag rather than by register name, this renames registers and removes WAR and WAW hazards.
- A common data bus (CDB) broadcasts each result with its tag. Every reservation station waiting for that tag grabs the value at once, and the register file is updated if that tag is still the latest producer of the register.
Reorder Buffer and Speculation
If instructions finish out of order, what happens when one of them causes an exception, or turns out to be on the wrong side of a mispredicted branch? The reorder buffer (ROB) holds results of instructions in program order until they commit. An instruction updates the architectural registers or memory only when it reaches the head of the ROB and everything before it has committed. This gives:
- Precise exceptions: when an instruction faults, all earlier instructions have committed and no later one has, exactly as if execution were sequential.
- Hardware speculation: the processor predicts branches and executes past them. On a misprediction, the ROB simply discards all younger, uncommitted entries.
| Feature | Scoreboard | Tomasulo | Tomasulo + ROB |
|---|---|---|---|
| Out-of-order execution | Yes | Yes | Yes |
| Register renaming | No (stalls on WAR/WAW) | Yes (via tags) | Yes |
| Result distribution | Through register file | Common data bus | CDB, then ROB |
| Precise exceptions | No | No | Yes |
| Speculation past branches | No | No (needs a way to undo work) | Yes |
VLIW: Let the Compiler Do It
Checking dependences among many instructions every cycle costs a lot of hardware and power. A Very Long Instruction Word (VLIW) processor moves that work to the compiler.
VLIW: each instruction word contains several independent operations (for example 2 memory, 2 integer, 2 floating-point, 1 branch), one for each functional unit. The compiler guarantees they are independent; the hardware issues the whole bundle without checking.
One VLIW instruction word (bundle):
+---------------+---------------+---------------+---------------+---------------+
| mem op 1 | mem op 2 | FP op | int op | branch |
| fld f0,0(x1) | fld f4,-8(x1) | fmul f9,f8,f2 | addi x6,x6,-1 | nop |
+---------------+---------------+---------------+---------------+---------------+
Empty slots must be filled with NOPs.Notice that the multiply uses f8, which was loaded by an earlier bundle. It could not use f0, because the load of f0 is in the same bundle, and operations packed into one bundle must be independent of each other.
Strengths: simpler, lower-power hardware. Weaknesses: the compiler cannot know run-time events such as cache misses; code size grows (NOPs, unrolling); and binaries are tied to one machine's slot layout, so a new implementation may need recompilation. Intel's Itanium (IA-64) used a VLIW-style approach called EPIC (Explicitly Parallel Instruction Computing). VLIW is common today in digital signal processors.
Superpipelining
Another route to more throughput is to split each stage into smaller pieces so the clock can run faster. A pipeline with many stages (often well over 10) is called superpipelined. It still issues one instruction per (faster) cycle.
| Aspect | Superpipelined | Superscalar | VLIW |
|---|---|---|---|
| How parallelism is obtained | More, shorter stages; faster clock | Several instructions issued per cycle | Several operations packed in one instruction |
| Who finds the parallelism | Hardware (pipeline overlap) | Hardware, at run time | Compiler, at compile time |
| Ideal CPI | 1 (per short cycle) | 1/n | 1 bundle per cycle |
| Main limit | Latch overhead, bigger branch penalty | Dependence checking, power, ILP | Compiler knowledge, code size, compatibility |
| Binary compatibility | Yes | Yes | Often no |
Real high-performance cores combine all of these: a fairly deep pipeline, wide superscalar issue, out-of-order execution, renaming and speculation.
Limits of ILP
- True dependences: the critical path of RAW chains cannot be shortened.
- Branches: in typical integer code roughly one instruction in five to seven is a branch. Every misprediction throws away all the work in a wide, deep pipeline.
- Memory latency: a cache miss to DRAM costs hundreds of cycles; the instruction window fills up and the core stalls.
- Window size and complexity: finding independent instructions requires a large window, and dependence checking, renaming and wake-up logic grow quickly with width.
- Power: speculative work that is thrown away still burns energy.
Around the mid-2000s these limits, together with the power wall, made designers turn to thread-level parallelism: running several independent instruction streams. Simultaneous multithreading (SMT, such as Intel Hyper-Threading) lets one superscalar core fill its idle issue slots with instructions from two threads. Using many processors together is covered in Parallel Processing & Flynn's Classification and Multicore Processors & Cache Coherence.
Common Mistakes
- Thinking WAR and WAW are "real" dependences. They are name dependences and can be removed by renaming; only RAW is a true dependence.
- Counting a RAW pair when a later write in between kills it (I1 → I4 above).
- Assuming an n-way superscalar is n times faster. n is the peak; dependences, branches and cache misses keep the real IPC well below it.
- Forgetting offset adjustment when moving a load or store past the pointer-update instruction during scheduling.
- Confusing out-of-order execution with out-of-order commit. Modern processors execute out of order but commit in order (via the ROB) to keep exceptions precise.
- Mixing up superscalar and VLIW. Superscalar: hardware finds parallelism among ordinary instructions. VLIW: the compiler bundles operations into one long instruction.
GATE and Interview Questions
Q1. Identify all hazards in: I1: mul r1,r2,r3; I2: add r2,r1,r4; I3: sub r1,r5,r6.
RAW: I1 → I2 on r1. WAR: I1 → I2 on r2 (I1 reads r2, I2 writes it) and I2 → I3 on r1 (I2 reads r1, I3 writes it). WAW: I1 → I3 on r1. So 1 RAW, 2 WAR, 1 WAW.
Q2. A 4-stage, 3-way superscalar runs 60 independent instructions. How many cycles? What is the speedup over a 4-stage scalar pipeline?
Superscalar: 4 + 60/3 - 1 = 23 cycles. Scalar: 4 + 60 - 1 = 63 cycles. Speedup = 63/23 = 2.74.
Q3. How does register renaming remove WAR and WAW hazards but not RAW hazards?
WAR and WAW arise only because two instructions reuse the same register name. Giving each new write its own physical register means a later write can never clobber a value an earlier instruction still needs, and writes to different physical registers cannot be ordered wrongly. A RAW hazard is a real flow of data: the consumer needs the producer's value, so it must wait whatever the name.
Q4. Why does an out-of-order processor need a reorder buffer?
To commit results in program order. This gives precise exceptions and lets the processor speculate past branches: wrong-path or faulting results stay in the ROB and are discarded without ever changing registers or memory.
Q5. What are the costs of loop unrolling?
Larger code size (more instruction-cache misses), more registers needed (possible spills), and extra cleanup code for leftover iterations when the trip count is not a multiple of the unroll factor.
Q6. Superscalar vs VLIW: who detects parallelism, and what is the main trade-off?
Superscalar: hardware at run time, which costs area and power but keeps binary compatibility and adapts to events like cache misses. VLIW: the compiler at compile time, which simplifies hardware but makes code bigger, cannot react to run-time events and may need recompilation for a new machine.
Summary
- ILP is parallelism among instructions of one program. Exploiting it lets CPI drop below 1 (IPC above 1).
- Dependences: true (RAW), anti (WAR), output (WAW) and control. Only RAW is fundamental; renaming removes WAR and WAW.
- Compilers expose ILP with loop unrolling and scheduling: in our example, 10 → 3.5 cycles per element.
- A superscalar issues up to n instructions per cycle; ideal time k + N/n - 1 cycles. Real gains are limited by dependences and resources.
- Dynamic scheduling (scoreboard, Tomasulo) executes instructions out of order; Tomasulo renames via reservation-station tags and a common data bus; a reorder buffer commits in order, enabling precise exceptions and speculation.
- VLIW/EPIC moves parallelism discovery to the compiler; superpipelining raises clock rate with deeper pipelines.
- ILP has practical limits (dependences, branches, memory, power), which pushed the industry towards thread-level parallelism and multiple cores.