Instruction-Level Parallelism & Superscalar Processors

CSS Optional — Paper-II, Computer Organization & Architecture

1. Definition

Instruction-Level Parallelism (ILP) is the potential to execute multiple instructions from a single instruction stream simultaneously, by overlapping their execution stages rather than running them strictly one after another. It is exploited primarily through pipelining and superscalar execution.

2. Classification — Techniques for Exploiting ILP

• Pipelining — overlapping the fetch/decode/execute/memory/writeback stages of successive instructions so several instructions are in different stages at once, on a single execution unit.
• Superscalar execution — the processor has multiple execution units (e.g., two ALUs) and can issue more than one instruction per clock cycle, achieving IPC (Instructions Per Cycle) greater than 1.
• VLIW (Very Long Instruction Word) — the compiler, not the hardware, packs multiple independent operations into one long instruction word ahead of time — shifting the parallelism-finding burden from runtime hardware to compile-time software.
• Out-of-order execution — instructions are dispatched to execution units as their operands become ready rather than strictly in program order, with results committed in order to preserve correctness.

🗺️ Architecture Diagram — Pipeline Execution

graph TD
    subgraph Cycle1["Cycle 1"]
        A1["I1: F"]
    end
    subgraph Cycle2["Cycle 2"]
        A2["I1: D"] --- B2["I2: F"]
    end
    subgraph Cycle3["Cycle 3"]
        A3["I1: E"] --- B3["I2: D"] --- C3["I3: F"]
    end
    subgraph Cycle4["Cycle 4"]
        A4["I1: M"] --- B4["I2: E"] --- C4["I3: D"] --- D4["I4: F"]
    end

3. Classification — Pipeline Hazards ⭐ (highest-yield section)

A hazard is any situation that prevents the next instruction from executing in its designated clock cycle.

(a) Structural Hazards

Two instructions need the same hardware resource in the same cycle (e.g., both need the single memory port). Resolved by duplicating resources (e.g., separate instruction and data caches — a Harvard-style split) or by stalling.

(b) Data Hazards

An instruction depends on the result of a prior instruction still in the pipeline.

• RAW (Read After Write) — the true dependency; the only one that requires a genuine fix.
• WAR (Write After Read) and WAW (Write After Write) — "false" dependencies caused by register reuse, not real data flow; eliminated by register renaming.
• Fix for RAW: forwarding/bypassing — the result is routed directly from the producing stage back to the consuming stage without waiting for it to be written back to the register file, eliminating most stall cycles.
• If forwarding cannot resolve it in time (e.g., a load followed immediately by a use of its result — the "load-use hazard"), the pipeline must stall.

(c) Control Hazards

Caused by branches — the pipeline does not know which instruction to fetch next until the branch is resolved.

• Static prediction — always predict "not taken," or use compiler hints.
• Dynamic branch prediction — a hardware predictor (e.g., a branch history table) guesses the outcome based on past behaviour; a misprediction requires flushing the incorrectly fetched instructions and restarting fetch at the correct target, at a real cycle cost.

4. Superscalar Processors

• Have multiple parallel execution units (e.g., two integer ALUs, one floating-point unit) fed by instruction issue logic that can dispatch several instructions per cycle if they are independent.
• Issue width — the maximum number of instructions the processor can issue in one cycle (e.g., a "4-wide" superscalar issues up to 4 instructions/cycle).
• Practical IPC is always well below the issue width because of hazards and limited independent work available in the instruction stream — this gap is exactly what out-of-order execution and register renaming aim to close.

---

🧮 Solved Numerical 1 — Ideal Pipeline Speedup

Q: A pipeline has 5 stages, each taking 1 cycle. 100 instructions are executed. Compare pipelined vs non-pipelined execution time and find the speedup.

Non-pipelined time = n × k = 100 × 5 = 500 cycles
Pipelined time      = k + (n − 1) = 5 + 99 = 104 cycles

Speedup = 500 / 104 ≈ 4.81

Answer: ≈4.81× speedup — approaching, but never reaching, the theoretical maximum of 5× (= number of stages), because the pipeline must still fill and drain.

🧮 Solved Numerical 2 — Effective CPI With Stalls

Q: An ideal pipeline has CPI = 1. Data hazards force a 1-cycle stall on 20% of instructions. Find the effective CPI and the resulting slowdown.

Stall contribution = 0.20 × 1 = 0.20
Effective CPI       = 1 + 0.20 = 1.20

Slowdown = 1.20 / 1.00 = 1.2×  (20% slower than the ideal pipeline)

Answer: Effective CPI = 1.2; the pipeline runs 20% slower than its ideal-case rate.

🧮 Solved Numerical 3 — Superscalar IPC and Speedup

Q: A 2-issue superscalar processor executes 100 instructions in 60 cycles. Find its IPC and its speedup over an ideal scalar (single-issue) processor.

IPC = Instructions / Cycles = 100 / 60 ≈ 1.67

Scalar processor (CPI = 1): 100 instructions take 100 cycles

Speedup = 100 / 60 ≈ 1.67×

Answer: IPC ≈ 1.67; ≈1.67× faster than a scalar processor — well short of the 2× the issue width might suggest, illustrating why real superscalar IPC rarely approaches the issue width.

🧮 Solved Numerical 4 — Branch Misprediction Penalty

Q: 20% of instructions are branches. The branch predictor is wrong 10% of the time, and each misprediction costs 15 extra cycles. Find the average CPI overhead due to branches.

Overhead per instruction = P(branch) × P(mispredict) × penalty
                          = 0.20 × 0.10 × 15
                          = 0.30 cycles added to CPI

Answer: +0.30 CPI on average from branch mispredictions alone — a concrete illustration of why deeper pipelines (which raise the misprediction penalty) put ever more pressure on accurate branch prediction.

---

🎯 CSS Exam Angle

• Pipeline hazards (structural/data/control) with their fixes (forwarding, stalling, branch prediction) is one of the most reliably asked short/long questions in this chapter — always name the fix alongside the hazard, not just the hazard itself.
• A pipeline-speedup numerical (Numerical 1's style) is close to guaranteed; know the two formulas (n×k vs k+n−1) cold.
• Distinguish superscalar (hardware finds parallelism at runtime) from VLIW (compiler finds it at compile time) — a common "compare" question.

🔁 Repeated CSS Questions

1. Explain pipelining with a diagram and calculate the speedup for a given number of stages and instructions. (Numerical — frequently repeated)
2. Explain the three types of pipeline hazards with their solutions.
3. Differentiate between superscalar and VLIW architectures.
4. What is register renaming, and which hazards does it eliminate?
5. Calculate the CPI overhead caused by branch mispredictions. (Numerical)

⚠️ MCQ Traps

• RAW is a true dependency; WAR and WAW are false dependencies caused only by register reuse — register renaming eliminates WAR/WAW but cannot eliminate RAW.
• Forwarding/bypassing fixes most data hazards without stalling — a stall is only needed when forwarding cannot deliver the value in time (e.g., load-use hazard).
• Pipeline speedup approaches but never equals the number of stages, because of pipeline fill/drain time.
• Superscalar hardware discovers parallelism at runtime; VLIW parallelism is discovered by the compiler at compile time — do not swap these.
• Issue width is a ceiling, not a guarantee — actual IPC is almost always lower due to hazards and dependency chains.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2018 · Paper-II · Q2(C) · 6 marks

Q. Discuss instruction pipelining in the context of the fetch-decode-execute cycle.

Ans.

• Pipelining overlaps the stages of different instructions, like an assembly line. While one instruction is executing, the next is being decoded and the one after that is being fetched.
• Stages (4-stage example): fetch (F), decode (D), execute (E), write-back (W).

Cycle:   1  2  3  4  5  6
I1:      F  D  E  W
I2:         F  D  E  W
I3:            F  D  E  W

• Speed-up: n instructions in k stages take k + n − 1 cycles instead of n × k.
• Hazards that cause stalls: structural (resource conflict), data (an instruction needs a result that is not ready) and control (branches).

2019 · Paper-II · Q2(b) · 6 marks

Q. Demonstrate the use of the superscalar approach to achieve instruction-level parallelism using a suitable example.

Ans.

• A superscalar processor has several execution units and issues more than one instruction per clock cycle. Independent instructions run in parallel.
• Example:

I1: ADD R1, R2, R3     ┐ independent: issued together in cycle 1
I2: SUB R4, R5, R6     ┘ (two ALUs)
I3: MUL R7, R1, R4     ← needs R1 and R4, so it is issued in cycle 2

• With two pipelines, these three instructions take 2 cycles instead of 3.
• Techniques: dynamic scheduling, out-of-order execution, register renaming and branch prediction.

2020 · Paper-II · Q2(c) · 7 marks

Q. What is instruction-level parallelism? What are the typical distinguishing characteristics of RISC organisation?

Ans.

• ILP is the ability of a processor to execute several instructions of one program at the same time (through pipelining, superscalar or VLIW designs and out-of-order execution). It is limited by dependences between instructions.
• RISC characteristics: one instruction per cycle, simple fixed-length instructions, load/store architecture, a large register file, few addressing modes, a hardwired control unit, and heavy use of pipelining.

2022 · Paper-II · Q4(a) · 8 marks

Q. A pipeline has four stages: fetch instruction (FI), decode and calculate address (DA), fetch operand (FO), execute (EX). Draw a diagram for 7 instructions in which the third instruction is a branch that is taken, with no data dependencies.

Ans. Instructions are I1, I2, I3 (branch to I15), then the target stream I15, I16, I17, I18.

• The branch is resolved only at EX in cycle 6, so the instruction fetched after it (I4) is discarded and the target I15 is fetched in cycle 7. Cycles 4–6 are the branch penalty (the pipeline does useful work only on the I1–I3 stream).

2023 · Paper-II · Q5(c) · 5 marks

Q. What is the distinction between instruction-level parallelism and machine parallelism?

Ans.

• Instruction-level parallelism is a property of the program: how many of its instructions are independent and could in principle be executed at the same time (limited by data and control dependences).
• Machine parallelism is a property of the processor: how many instructions it can actually fetch, issue and execute at once (number of pipelines and functional units, window size).
• Performance is limited by the smaller of the two. A machine with high parallelism gains nothing from a program with low ILP, and the reverse.

⚠️ Practice question (not verified as a 2026 paper question)

Source unconfirmed: this was not found in the 2026 Paper-I paper, and no 2026 Paper-II paper has been checked. Treat it as a likely-style practice question until verified.

Q. Explain the synergistic relationship among ILP, superscalar execution and multi-core architectures in modern CPU design. Analyse how their combined use affects pipeline design, mitigation of control hazards and overall throughput.

Ans.

• ILP: extracts parallelism within one instruction stream by overlapping and reordering independent instructions.
• Superscalar execution: hardware realisation of ILP: several pipelines and functional units that issue multiple instructions per cycle, supported by out-of-order execution, register renaming and a reorder buffer.
• Multi-core: places several such cores on one chip to exploit thread-level parallelism across different programs or threads.
• Synergy: ILP and superscalar raise the speed of each core, but ILP has diminishing returns (typically about 4–6 instructions per cycle, limited by dependences and branches) and clock speed is limited by power. Multi-core therefore adds parallelism at a higher level. The three work together, each at a different level: instruction, core and thread.
• Effect on pipeline design:
  • deeper, wider pipelines with several issue slots
  • forwarding and register renaming to resolve data hazards
  • larger instruction windows and reorder buffers
  • per-core caches with coherence between cores
• Control hazard mitigation: branch prediction (dynamic predictors, branch target buffer), speculative execution (with rollback on a wrong guess), delayed branches and predication. Superscalar pipelines depend heavily on prediction because a misprediction wastes many issue slots.
• Throughput: throughput roughly equals cores × IPC per core × clock. Superscalar raises IPC, multi-core multiplies it, and the gain is limited by Amdahl's law (the serial fraction) and by memory bandwidth.
• Conclusion: modern CPUs combine all three to scale performance within a power budget.