5-Stage RISC Pipelines, Forwarding Units & Dynamic Branch Predictors

Instruction pipelining is the seminal microarchitectural technique that transformed computer systems from sequential state machines into high-throughput computing engines. By overlapping the execution of multiple instructions across dedicated hardware stages, pipelining increases computational throughput by multiple orders of magnitude without altering single-instruction latency. However, overlapping instructions introduces physical data dependencies, memory resource collisions, and speculative branch penalties known as pipeline hazards. Mastering hazard mitigation via forwarding units, hazard detection logic, and dynamic branch prediction is essential for understanding modern processor design.

1. Principles of Instruction Pipelining & Throughput Speedup#

In a non-pipelined single-cycle processor, each instruction must sequentially traverse every hardware execution unit before the next instruction can begin. Because different instructions require different hardware paths, execution units sit idle for large fractions of the clock cycle, resulting in inefficient silicon utilization.

The Five Canonical Stages of RISC Execution#

In the classic 5-stage RISC microarchitecture (exemplified by RISC-V RV32I and classic MIPS), instruction execution is partitioned into five distinct, balanced stages:

Clock Cycle:      1      2      3      4      5      6      7      8      9
Instruction 1:  [ IF ] [ ID ] [ EX ] [ MEM] [ WB ]
Instruction 2:         [ IF ] [ ID ] [ EX ] [ MEM] [ WB ]
Instruction 3:                [ IF ] [ ID ] [ EX ] [ MEM] [ WB ]
Instruction 4:                       [ IF ] [ ID ] [ EX ] [ MEM] [ WB ]
Instruction 5:                              [ IF ] [ ID ] [ EX ] [ MEM] [ WB ]

1. Instruction Fetch (IF):

- The Program Counter (PC) supplies the memory address of the current instruction to the Instruction Cache.

- The 32-bit instruction word is fetched into the IF/ID pipeline register.

- A dedicated hardware adder computes PC + 4 to prepare for the next sequential instruction fetch in the subsequent clock cycle.

1. Instruction Decode & Register File Read (ID):

- The opcode, register specifiers (rs1, rs2, rd), and function fields (funct3, funct7) are decoded by the Main Control Unit.

- Operands are read from the dual read ports of the Register File.

- The Immediate Generator extracts and sign-extends constant literal fields (12-bit or 20-bit immediates) to 32 bits.

- All operands and decoded control signals are latched into the ID/EX pipeline register.

1. Execution & Effective Address Calculation (EX):

- The Arithmetic Logic Unit (ALU) performs the designated arithmetic or logical operation (ADD, SUB, AND, OR, XOR, SLL, SRL, SRA).

- For memory access instructions (LOAD and STORE), the ALU computes the effective byte address: Address = Base_Register + Sign_Extended_Immediate.

- For conditional branch instructions (BEQ, BNE, BLT, BGE), the ALU evaluates the comparison condition, while a dedicated branch adder computes the branch target address: Target = PC_Branch + (Immediate << 1).

- Execution outputs are latched into the EX/MEM pipeline register.

1. Memory Access (MEM):

- For LOAD instructions, the effective address drives the Data Cache, and the requested data word/byte is retrieved.

- For STORE instructions, data from register rs2 is written into the Data Cache at the calculated address.

- Arithmetic instructions pass their ALU output directly through this stage without interacting with memory.

- Memory outputs are latched into the MEM/WB pipeline register.

1. Write-Back (WB):

- The final computed result—either the ALU output or the word read from memory—is written back into the destination register rd in the Register File.

- This completes the architectural state retirement of the instruction.

Pipeline Registers & State Synchronization#

The boundary between adjacent pipeline stages is physically bridged by clocked pipeline registers:

• IF/ID Register: Latches the fetched 32-bit instruction and the current PC.
• ID/EX Register: Latches read operands A and B, sign-extended immediate, PC, register identifiers (rs1, rs2, rd), and execution control lines.
• EX/MEM Register: Latches the computed ALU result, store data operand, zero/condition flags, target branch address, destination register rd, and memory control lines.
• MEM/WB Register: Latches the memory read data word, ALU result, destination register rd, and write-back control lines (RegWrite, MemtoReg).

Pipeline registers act as temporal barriers. On each rising clock edge, all five stages advance simultaneously, latching their computed outputs forward into the next stage.

Analytical Speedup Derivation#

Let n be the total number of instructions in a program, k be the number of pipeline stages (k = 5), t be the combinational logic delay of each stage, and d be the latch setup/clock-to-Q overhead of the pipeline registers.

In an unpipelined processor:

• Single instruction latency = k · t.
• Total time to execute n instructions = T_unpipelined = n · k · t.

In an ideal k-stage pipelined processor:

• Clock period = T_clk = t + d.
• The first instruction requires k clock cycles to fill the pipeline.
• Each subsequent instruction completes on every successive clock cycle.
• Total clock cycles to complete n instructions = k + (n - 1).
• Total execution time = T_pipelined = (k + n - 1) · (t + d).

The theoretical speedup is:

Speedup = T_unpipelined / T_pipelined = (n · k · t) / [ (k + n - 1) · (t + d) ].

Taking the limit as the program size n approaches infinity:

lim_{n → ∞} Speedup = [ k · t ] / [ t + d ].

If pipeline register overhead d is negligible compared to stage delay t (d << t):

Speedup ≈ k = 5×.

A 5-stage pipeline achieves up to a 5× throughput improvement without decreasing the latency of any individual instruction. In fact, due to register latch delay d, the latency of a single instruction slightly increases from 5t to 5(t + d). Pipelining optimizes throughput (instructions completed per unit time), not latency.

2. Taxonomy of Pipeline Hazards & Silicon Disruptions#

In ideal conditions, a 5-stage pipeline retires one instruction per clock cycle, achieving an ideal Cycles Per Instruction (CPI) of 1.0. In real silicon, however, inter-instruction dependencies cause stalls, forcing hardware to insert idle cycles called pipeline bubbles.

The actual CPI of a pipelined processor is:

CPI_actual = CPI_ideal + Stalls_structural + Stalls_data + Stalls_control.

Pipeline hazards fall into three fundamental classes:

1. Structural Hazards (Hardware Resource Contention)#

A structural hazard occurs when two or more concurrent instructions attempt to access the exact same physical hardware functional unit in the same clock cycle.

• Example: If a processor utilized a unified, single-ported memory array for both instruction fetches and data operands, an instruction in the IF stage (fetching an instruction) would collide with an instruction in the MEM stage (reading or writing data).
• Hardware Solutions:

1. Harvard Architecture: Splitting L1 cache into physically separate L1 Instruction Cache (L1-I) and L1 Data Cache (L1-D), allowing simultaneous instruction fetches and memory operations.

2. Multi-Ported Register Files: Designing register files with dual independent read decoders/buses and a separate write decoder/bus, enabling two reads (ID stage) and one write (WB stage) in the exact same clock phase.

2. Data Hazards (Operand Dependencies)#

A data hazard arises when an instruction requires the result of an earlier instruction that has not yet reached the Write-Back stage:

• Read-After-Write (RAW) / True Data Dependency: Instruction J attempts to read register R before Instruction I writes its computed result to R. This is the dominant hazard in in-order pipelines.
• Write-After-Read (WAR) / Anti-Dependency: Instruction J attempts to write register R before Instruction I reads it. In strict in-order pipelines, WAR hazards cannot cause errors because instructions read operands in the ID stage before subsequent instructions can overwrite them. WAR hazards become critical in out-of-order execution engines.
• Write-After-Write (WAW) / Output Dependency: Instruction J attempts to write register R before Instruction I writes to R, risking leaving an obsolete value in R. Like WAR, WAW hazards occur only in out-of-order or multi-cycle execution pipelines.

3. Control Hazards (Branch & Jump Disruptions)#

A control hazard occurs when a conditional branch or jump instruction alters the Program Counter. Because the branch condition and target address are not resolved until the EX (or ID) stage, the processor does not know which instruction to fetch in the subsequent cycle, risking fetching incorrect instructions that must later be discarded.

3. Data Forwarding (Bypassing) Mechanics & Boolean Control Logic#

Consider the following sequence of instructions exhibiting severe RAW data dependencies:

ADD x1, x2, x3    # Cycle 1: Fetched. Writes result to x1 in Cycle 5 (WB)
SUB x4, x1, x5    # Cycle 2: Fetched. Reads x1 in Cycle 3 (ID) -> HAZARD!
AND x6, x1, x7    # Cycle 3: Fetched. Reads x1 in Cycle 4 (ID) -> HAZARD!
OR  x8, x1, x9    # Cycle 4: Fetched. Reads x1 in Cycle 5 (ID) -> Compatible via WB

Without hardware intervention, Instruction 2 (SUB) would read the obsolete, stale value of x1 during Cycle 3 because Instruction 1 (ADD) does not write its result into the register file until Cycle 5. Resolving this naively would require stalling the pipeline for 2 full clock cycles, injecting two bubble cycles.

The Forwarding Principle#

Notice a fundamental microarchitectural truth:

• The ADD instruction computes its result at the conclusion of its EX stage (Cycle 3).
• The SUB instruction does not actually require the value of x1 until the beginning of its own EX stage (Cycle 4).

The data exists inside the processor in hardware pipeline registers before it is written to the register file! Data Forwarding (Bypassing) routes the computed result directly from intermediate pipeline registers back to the ALU inputs, completely bypassing the register file.

                  +--------------------------------------------------------+
                  |                                                        | EX-to-EX Forwarding Path
                  v                                                        |
+----+    +----+    +------+    +--------+    +----+                       |
| IF |--->| ID |--->|  EX  |--->|  MEM   |--->| WB |-----------------------+
+----+    +----+    +------+    +--------+    +----+
                       ^            |           |
                       |            +-----------+  MEM-to-EX Forwarding Path
                       +------------------------+

Forwarding Multiplexer Architecture#

Two 3-to-1 multiplexers are inserted immediately before the ALU inputs:

• Multiplexer A controls ALU Input 1 (corresponding to register rs1).
• Multiplexer B controls ALU Input 2 (corresponding to register rs2).

Control Signals ForwardA and ForwardB select the operand source:

• 00: Original operand from ID/EX register (no forwarding needed).
• 10: Forward from EX/MEM pipeline register (result from instruction 1 cycle ahead).
• 01: Forward from MEM/WB pipeline register (result from instruction 2 cycles ahead).

Forwarding Unit Boolean Control Logic#

The Forwarding Unit continuously monitors register identifiers in pipeline registers during each clock cycle.

1. EX Hazard (Forward from EX/MEM to ALU Input A):

A RAW dependency exists on rs1 with the immediately preceding instruction if:

- The preceding instruction writes to a register: EX/MEM.RegWrite == 1.

- The preceding destination register is not x0: EX/MEM.RegisterRd != 0.

- The preceding destination matches the current source: EX/MEM.RegisterRd == ID/EX.RegisterRs1.

Boolean Rule:

```verilog

if (EX/MEM.RegWrite and (EX/MEM.RegisterRd != 0) and (EX/MEM.RegisterRd == ID/EX.RegisterRs1))

ForwardA = 2'b10;

```

1. MEM Hazard (Forward from MEM/WB to ALU Input A with Priority):

A RAW dependency exists on rs1 with the instruction two cycles ahead if:

- The older instruction writes to a register: MEM/WB.RegWrite == 1.

- The older destination register is not x0: MEM/WB.RegisterRd != 0.

- The older destination matches current source: MEM/WB.RegisterRd == ID/EX.RegisterRs1.

- Crucial Priority Condition: The EX hazard condition is NOT active for the same register! If both the EX/MEM and MEM/WB stages are writing to the same register, the EX/MEM stage holds the most recent architectural value.

Boolean Rule:

```verilog

if (MEM/WB.RegWrite and (MEM/WB.RegisterRd != 0) and

not (EX/MEM.RegWrite and (EX/MEM.RegisterRd != 0) and (EX/MEM.RegisterRd == ID/EX.RegisterRs1)) and

(MEM/WB.RegisterRd == ID/EX.RegisterRs1))

ForwardA = 2'b01;

```

Identical symmetric boolean equations govern ForwardB for source register rs2.

4. The Unavoidable Load-Use Data Hazard & Hazard Detection Units#

While forwarding eliminates stalls between arithmetic instructions, it cannot overcome the Load-Use Data Hazard.

Consider a LOAD instruction followed immediately by an instruction consuming the loaded register:

LW  x1, 0(x2)     # Loads word from memory into x1
ADD x3, x1, x4    # Consumes x1 in EX stage

Look at the temporal progression:

• LW retrieves its data from memory at the conclusion of the MEM stage (Cycle 4).
• ADD requires the operand at the beginning of its EX stage (Cycle 3).

Forwarding would require sending data backward in time from Cycle 4 to Cycle 3! Because physical hardware cannot violate causality, forwarding alone cannot prevent a stall. The pipeline must insert a 1-cycle bubble.

Cycle:       1      2      3      4      5      6      7
LW:        [ IF ] [ ID ] [ EX ] [ MEM] [ WB ]
ADD:              [ IF ] [ ID ] [ STALL] [ EX ] [ MEM] [ WB ]
                                  (Bubble)  ^
                                            | (Forwarded from MEM stage)

The Hazard Detection Unit (HDU)#

The Hazard Detection Unit operates during the ID stage to intercept load-use hazards before the consuming instruction enters execution:

Condition:

if (ID/EX.MemRead and ((ID/EX.RegisterRd == IF/ID.RegisterRs1) or (ID/EX.RegisterRd == IF/ID.RegisterRs2)))

When this condition is detected, the HDU enforces three coordinated actions on the next clock edge:

1. Freeze Program Counter: De-assert PC_Write (PC retains its current address, re-fetching the stalled instruction).
2. Freeze IF/ID Register: De-assert IF/ID_Write (preserves the stalled instruction in the ID stage).
3. Inject Pipeline Bubble: Clear all execution, memory, and write-back control lines in the ID/EX register to 0 (NOP).

After this single-cycle stall, the LW instruction advances to the MEM stage, and standard forwarding safely routes the loaded memory data from MEM/WB directly into the ALU input of ADD in Cycle 4 without further delay.

5. Branch Prediction Architectures & Speculative Execution#

Conditional branch instructions represent the most severe impediment to high pipeline throughput.

The Cost of Branch Penalties#

In the baseline 5-stage pipeline, branch condition evaluation and target address calculation occur in the EX stage (Cycle 3).

If the processor simply waited for branch resolution before fetching the next instruction, every branch would incur a mandatory 2-cycle penalty.

In modern deep out-of-order processors (e.g., Intel Golden Cove with 20+ pipeline stages), resolving a branch takes 15 to 20 clock cycles. If branches constitute 20% of all executed instructions and are resolved sequentially, the average CPI would jump from 1.0 to:

CPI = 1.0 + 0.20 · 15 = 4.0 (a 75% performance collapse!).

Processors must therefore engage in Speculative Execution: predicting the branch outcome at instruction fetch time and speculatively fetching subsequent instructions down the predicted path.

Static Branch Prediction#

Static prediction relies on compile-time heuristics without runtime tracking:

1. Always Not-Taken: Assume conditional branches will not be taken. The processor continues fetching PC + 4 sequentially. If the branch is taken, speculatively fetched instructions are converted into NOPs (flushed), incurring a penalty.
2. Backward Taken, Forward Not-Taken (BTFNT):

- Backward branches (target address < current PC) are predicted TAKEN. This exploits the empirical reality of program loops: loops branch backward to their beginning on almost every iteration except the final termination.

- Forward branches (target address > current PC) are predicted NOT-TAKEN. Forward branches typically represent exception handlers, assertions, or error checks that rarely execute in production paths.

Dynamic Branch Prediction: 2-Bit Saturating Counters#

Static prediction fails on data-dependent branches. Dynamic predictors utilize dedicated hardware tables indexed by the branch instruction's memory address to track historical behavior.

A 1-bit predictor simply records whether the branch was taken or not taken on its last execution.

Flaw of 1-bit Predictor: Consider a nested loop that iterates 100 times:

• On loop termination (iteration 100), the branch falls through (Not-Taken). The 1-bit predictor flips its state to Not-Taken (Misprediction 1).
• On the very next entry into the loop, the first iteration branches back (Taken). The predictor flips back to Taken (Misprediction 2).

A 1-bit predictor mispredicts twice for every loop execution!

The 2-Bit Saturating Counter (Smith Predictor):

To add hysteresis and prevent single loop exits from altering prediction state, modern microarchitectures implement a 4-state saturating counter:

            Taken                Taken                Taken
            ----->               ----->               ----->
     [ 00: Strongly ]     [ 01: Weakly   ]     [ 10: Weakly   ]     [ 11: Strongly ]
     [  Not-Taken   ]     [  Not-Taken   ]     [    Taken     ]     [    Taken     ]
            <-----               <-----               <-----
          Not-Taken            Not-Taken            Not-Taken

State Transitions:

• 00 (Strongly Not-Taken): Predict Not-Taken. If Not-Taken, stay at 00. If Taken, transition to 01.
• 01 (Weakly Not-Taken): Predict Not-Taken. If Not-Taken, transition to 00. If Taken, transition to 10.
• 10 (Weakly Taken): Predict Taken. If Taken, transition to 11. If Not-Taken, transition to 01.
• 11 (Strongly Taken): Predict Taken. If Taken, stay at 11. If Not-Taken, transition to 10.

Because the predictor requires two consecutive mispredictions to flip its prediction policy, an isolated loop exit at iteration 100 moves the counter from 11 to 10. On the next loop invocation, it still predicts Taken (10 >= 2), achieving >99% prediction accuracy across inner loops!

Branch Target Buffers (BTB) & Two-Level Adaptive Predictors#

Knowing that a branch is Taken is useless unless the hardware knows WHERE to branch.

• Branch Target Buffer (BTB): A high-speed cache indexed by the instruction PC that stores the target destination address. During the IF stage, if the PC hits in the BTB and the predictor predicts Taken, the hardware immediately redirects the PC to the cached target address in Cycle 2 with zero stall cycles!
• Two-Level Adaptive Predictors (GShare): Correlate the outcome of the current branch with the outcomes of recent neighboring branches. A Global History Register (GHR) records the binary outcomes of the last m branches (e.g., 10110011). The GHR is bitwise XORed with the low-order bits of the branch PC to index into a table of 2-bit saturating counters. GShare and modern TAGE (TAgged GEometric history length) predictors achieve over 97% branch prediction accuracy on production workloads.

6. Real-World Engineering Case Studies & Low-Level Optimization#

Pipelining and branch prediction characteristics dictate the execution performance of systems software and high-frequency algorithms.

Linux Kernel Compiler Branch Annotations#

In the Linux kernel source code, developers annotate critical control flow paths using the likely() and unlikely() macros:

#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

if (unlikely(ptr == NULL)) {
    // Exceptional error recovery path
    return -ENOMEM;
}
// Hot execution path

The GCC/Clang compiler uses __builtin_expect() to rearrange generated machine code:

• The hot, expected execution path is laid out sequentially in physical memory directly following the branch. This maximizes instruction cache prefetching and ensures fall-through execution matches static BTFNT heuristics.
• The error handling path is relocated to a separate, cold memory page, preventing rarely executed recovery code from polluting the CPU's L1 Instruction Cache.

Branchless Code in High-Frequency Trading (HFT)#

In ultra-low-latency financial trading engines, a single branch misprediction flushing a 16-cycle pipeline costs 4 to 5 nanoseconds—enough to lose an order execution to a competitor.

Engineers eliminate branches using conditional move instructions (CMOV on x86, CSEL on ARM64) or bitwise arithmetic:

// Branching implementation (risks branch misprediction on random price data)
int max_price_branching(int a, int b) {
    return (a > b) ? a : b;
}

// Branchless implementation using conditional move
int max_price_branchless(int a, int b) {
    int result;
    asm("cmp %1, %2\n\t"
        "cmovg %1, %0"
        : "=r" (result)
        : "r" (a), "r" (b), "0" (b));
    return result;
}

The branchless version compiles into a single CMP instruction followed by a CMOVG instruction. Because there is no conditional jump, the branch prediction hardware is completely bypassed, eliminating misprediction flushes and yielding deterministic, jitter-free nanosecond execution.

7. Common Architectural Pitfalls & Misconceptions#

Understanding pipeline mechanics requires identifying subtle hardware fallacies.

Pitfall 1: Believing Forwarding Eliminates All Stalls#

A ubiquitous mistake among systems engineers is assuming that full forwarding hardware completely eliminates all pipeline stalls. As proven in Section 4, a Load-Use data dependency represents an unbridgeable temporal gap: data retrieved from memory is physically unavailable until the MEM stage. A 1-cycle bubble stall is mathematically and physically unavoidable unless compiler code scheduling separates the load from the consuming instruction.

Pitfall 2: Assuming Deep Pipelines Always Increase Performance#

In the early 2000s, Intel designed the NetBurst microarchitecture (Pentium 4) with up to 31 pipeline stages to push clock frequencies past 3.8 GHz.

However:

• Each stage boundary introduces pipeline register latch overhead d, consuming an increasing fraction of the clock period.
• Deep pipelines dramatically magnify branch misprediction penalties: flushing a 31-stage pipeline wastes 30+ clock cycles.
• Power dissipation exploded due to high frequencies. Modern architectures retreated to balanced 14–18 stage pipelines, focusing on instruction-level parallelism (wide superscalar execution) rather than extreme pipeline depth.

Pitfall 3: Overlooking Speculative Execution Side-Channel Vulnerabilities#

When a processor speculatively executes instructions past an unresolved branch, it may access memory locations that the program is not architecturally permitted to read (e.g., kernel memory or array out-of-bounds).

When the branch resolves as mispredicted:

• Architectural state (registers) is completely rolled back and discarded.
• Microarchitectural state (L1 cache lines pulled into cache during speculative execution) is NOT rolled back!

This asymmetry gave birth to the Spectre (Variant 1: Bounds Check Bypass) hardware vulnerability, where attackers measure cache access timing to exfiltrate secret data across security boundaries.

8. Comprehensive Checkpoint Practice Problems & Complete Step-by-Step Solutions#

Mastery of pipelined architectures and hazard control requires solving rigorous quantitative problems.

Problem 1 (Pipeline CPI & Speedup Calculation with Hazard Penalties):

A high-performance RISC-V processor implements a 5-stage pipeline operating at a clock frequency of 2.5 GHz.

Empirical workload profiling across a server benchmark reveals the following instruction mix and hazard characteristics:

• ALU Arithmetic Instructions: 45% of total instructions (ideal CPI = 1, zero hazard stalls due to full forwarding).
• Store Instructions: 15% of total instructions (ideal CPI = 1, zero hazard stalls).
• Load Instructions: 20% of total instructions. Profiling indicates that 35% of all load instructions are immediately followed by an instruction that consumes the loaded register (triggering an unavoidable 1-cycle Load-Use stall).
• Conditional Branch Instructions: 20% of total instructions. The processor utilizes a dynamic branch predictor achieving an 85% prediction accuracy. Branch target and condition resolution occurs in the EX stage, incurring a 2-cycle flush penalty on every misprediction.

1. Calculate the overall average Cycles Per Instruction (CPI) of the pipelined processor.
2. Compute the instruction execution throughput in Millions of Instructions Per Second (MIPS).
3. If an unpipelined single-cycle implementation of this processor requires a clock period of 1.60 ns to accommodate the slowest instruction, calculate the real-world speedup achieved by the pipelined implementation.

Solution:

Step 1: Calculate Average CPI

The total CPI is the sum of the ideal baseline CPI (1.0) and the stall penalties contributed by each instruction class:

CPI_actual = CPI_ideal + Penalty_loads + Penalty_branches.

1. Load-Use Stall Penalty:

- Fraction of instructions that are Loads = 0.20.

- Fraction of loads triggering a Load-Use hazard = 0.35.

- Stall cycles incurred per hazard = 1 cycle.

Penalty_loads = 0.20 · 0.35 · 1 cycle = 0.070 stalls/instruction.

1. Branch Misprediction Penalty:

- Fraction of instructions that are Branches = 0.20.

- Branch misprediction rate = 1 - 0.85 = 0.15 (15% mispredicted).

- Flush penalty incurred per misprediction = 2 cycles.

Penalty_branches = 0.20 · 0.15 · 2 cycles = 0.060 stalls/instruction.

1. Calculate Total Average CPI:

CPI_actual = 1.0 + 0.070 + 0.060 = 1.130 cycles/instruction.

Step 2: Compute Instruction Throughput (MIPS)

Throughput in MIPS is calculated as:

MIPS = Frequency (in MHz) / CPI = Frequency (in Hz) / (CPI · 10^6).

Given f = 2.5 GHz = 2500 MHz = 2.5 × 10^9 Hz:

MIPS = 2500 / 1.130 ≈ 2212.39 MIPS.

The processor executes approximately 2.212 billion instructions per second.

Step 3: Calculate Real-World Speedup Over Single-Cycle

Execution time for a program of n instructions is:

Time = (n · CPI) / Frequency = n · CPI · Clock_Period.

For the unpipelined single-cycle processor:

• Single-cycle CPI = 1.0.
• Single-cycle Clock Period T_single = 1.60 ns.

Time_single = n · 1.0 · 1.60 ns = 1.60 · n ns.

For the 5-stage pipelined processor:

• Pipelined CPI = 1.130.
• Pipelined Clock Period T_pipe = 1 / f = 1 / (2.5 × 10^9 s^-1) = 0.40 ns (400 ps).

Time_pipe = n · 1.130 · 0.40 ns = 0.452 · n ns.

Calculate the real-world speedup:

Speedup = Time_single / Time_pipe = (1.60 · n) / (0.452 · n) = 1.60 / 0.452 ≈ 3.5398× (or 3.54×).

The 5-stage pipeline achieves a 3.54× throughput speedup over the single-cycle design, demonstrating how overlapping execution overcomes hazard penalties.

Problem 2 (Cycle-by-Cycle Pipeline Trace with Forwarding & Hazard Stalls):

Trace the execution of the following four-instruction RISC-V assembly sequence through the 5-stage pipeline:

• I1: ADD x1, x2, x3 # computes x1 = x2 + x3
• I2: LW x4, 0(x1) # loads memory at address x1 into x4
• I3: SUB x5, x4, x6 # computes x5 = x4 - x6
• I4: OR x7, x5, x1 # computes x7 = x5 | x1

1. Construct a cycle-by-cycle execution matrix showing which stage (IF, ID, EX, MEM, WB) each instruction occupies across clock cycles 1 through 9.
2. Identify all instances of data forwarding: specify the producing instruction, consuming instruction, the specific pipeline register forwarded from, and the ALU operand input receiving the forwarded data.
3. Identify where a pipeline bubble stall must be inserted and explain why.

Solution:

Step 1: Dependency Analysis

1. Dependency between I1 (ADD) and I2 (LW):

- I1 produces x1.

- I2 consumes x1 as its base address in the EX stage.

- I1 computes x1 in EX (Cycle 3). I2 needs x1 in EX (Cycle 4).

- This is resolved via EX-to-EX forwarding from EX/MEM to ALU Input A with ZERO stalls.

1. Dependency between I2 (LW) and I3 (SUB):

- I2 loads x4 from memory in the MEM stage (Cycle 5).

- I3 consumes x4 in its EX stage.

- This is a Load-Use Data Hazard. I3 cannot execute its EX stage in Cycle 4 because x4 has not yet been read from memory.

- The Hazard Detection Unit stalls I3 in the ID stage for 1 cycle (Cycle 4), inserting a bubble into EX.

- In Cycle 5, MEM-to-EX forwarding routes x4 from MEM/WB into I3's EX stage.

1. Dependency between I3 (SUB) and I4 (OR):

- I3 produces x5 in EX (Cycle 5).

- I4 consumes x5 in its EX stage (Cycle 6).

- Resolved via EX-to-EX forwarding from EX/MEM to ALU Input A with ZERO stalls.

1. Dependency between I1 (ADD) and I4 (OR):

- I1 produces x1 (Cycle 3).

- I4 consumes x1 in EX (Cycle 6).

- By Cycle 6, I1 has already completed the WB stage (Cycle 5). I4 reads x1 directly from the register file during its ID stage (Cycle 5) with zero hazard.

Step 2: Cycle-by-Cycle Pipeline Execution Matrix

Cycle:      1     2     3     4       5     6     7     8     9
I1 (ADD):  [IF]  [ID]  [EX]  [MEM]   [WB]
I2 (LW ):        [IF]  [ID]  [EX ]   [MEM] [WB]
I3 (SUB):              [IF]  [ID ]*  [EX]  [MEM] [WB]
(Bubble):                    --      [EX]  [MEM] [WB]
I4 (OR ):                    [IF ]*  [ID]  [EX]  [MEM] [WB]

Note: In Cycle 4, I3 is stalled in [ID] and I4 is stalled in [IF]. A bubble (NOP) advances into EX.

Step 3: Explicit Forwarding Events

1. Cycle 4: Forwarding from EX/MEM (holding I1's ALU result for x1) to ALU Input A of I2 (LW). ForwardA = 2'b10.
2. Cycle 5: Forwarding from MEM/WB (holding I2's memory read data for x4) to ALU Input A of I3 (SUB). ForwardA = 2'b01.
3. Cycle 6: Forwarding from EX/MEM (holding I3's ALU result for x5) to ALU Input A of I4 (OR). ForwardA = 2'b10.

Problem 3 (2-Bit Saturating Counter Branch Predictor Simulation):

A 2-bit saturating counter branch predictor tracks a conditional branch at address 0x00401020.

• The 4 counter states are: 00 (Strongly Not-Taken), 01 (Weakly Not-Taken), 10 (Weakly Taken), 11 (Strongly Taken).
• Prediction policy: If the counter is in state 10 or 11, predict TAKEN (T). If in state 00 or 01, predict NOT-TAKEN (NT).
• Initial State: The predictor is initialized to state 10 (Weakly Taken).

The branch instruction is executed 8 consecutive times with the following sequence of actual outcomes:

Sequence = [ Taken, Taken, Not-Taken, Taken, Taken, Taken, Not-Taken, Not-Taken ]

1. Trace the predictor state step-by-step for each of the 8 executions: record the initial state, the prediction made (T or NT), the actual outcome, whether the prediction was a Hit or Misprediction, and the updated counter state.
2. Calculate the overall prediction accuracy percentage across the 8 executions.
3. Compare this result with a 1-bit predictor initialized to Taken (T) on the same sequence.

Solution:

Step 1: Step-by-Step 2-Bit Predictor Trace

+------+---------------+------------+--------+---------------+---------------+
| Step | Current State | Prediction | Actual | Result        | Next State    |
+------+---------------+------------+--------+---------------+---------------+
| 1    | 10 (WT)       | Taken      | Taken  | HIT (Correct) | 11 (ST)       |
| 2    | 11 (ST)       | Taken      | Taken  | HIT (Correct) | 11 (ST)       |
| 3    | 11 (ST)       | Taken      | Not-Tk | MISPREDICTION | 10 (WT)       |
| 4    | 10 (WT)       | Taken      | Taken  | HIT (Correct) | 11 (ST)       |
| 5    | 11 (ST)       | Taken      | Taken  | HIT (Correct) | 11 (ST)       |
| 6    | 11 (ST)       | Taken      | Taken  | HIT (Correct) | 11 (ST)       |
| 7    | 11 (ST)       | Taken      | Not-Tk | MISPREDICTION | 10 (WT)       |
| 8    | 10 (WT)       | Taken      | Not-Tk | MISPREDICTION | 01 (WNT)      |
+------+---------------+------------+--------+---------------+---------------+

Detailed Walkthrough:

• Step 1: State 10 predicts Taken. Actual is Taken. State saturates upward to 11. (Hit)
• Step 2: State 11 predicts Taken. Actual is Taken. State remains 11. (Hit)
• Step 3: State 11 predicts Taken. Actual is Not-Taken. Misprediction. State decrements to 10.
• Step 4: State 10 predicts Taken. Actual is Taken. Hit! State increments back to 11. (The single anomaly at Step 3 did not cause a misprediction on Step 4!).
• Step 5 & 6: State 11 predicts Taken. Actual is Taken. (2 Hits).
• Step 7: State 11 predicts Taken. Actual is Not-Taken. Misprediction. State decrements to 10.
• Step 8: State 10 predicts Taken. Actual is Not-Taken. Misprediction. State decrements to 01.

Step 2: Calculate Prediction Accuracy

• Total executions: 8
• Correct predictions (Hits): 5 (Steps 1, 2, 4, 5, 6)
• Mispredictions: 3 (Steps 3, 7, 8)

Accuracy = (5 / 8) · 100% = 62.5%.

Step 3: Comparison with 1-Bit Predictor

Trace for 1-bit predictor (initialized to T):

• Step 1: Predicts T, Actual T -> Hit. State: T.
• Step 2: Predicts T, Actual T -> Hit. State: T.
• Step 3: Predicts T, Actual NT -> Misprediction. State flips to NT.
• Step 4: Predicts NT, Actual T -> Misprediction! (Flips to T).
• Step 5: Predicts T, Actual T -> Hit. State: T.
• Step 6: Predicts T, Actual T -> Hit. State: T.
• Step 7: Predicts T, Actual NT -> Misprediction. State flips to NT.
• Step 8: Predicts NT, Actual NT -> Hit! State: NT.

Total Hits for 1-bit predictor: 5 / 8 = 62.5%.

Crucial distinction: Notice Step 4. The 2-bit counter correctly predicted Taken on Step 4 because state 10 remembered the previous history, whereas the 1-bit counter was fooled by the single glitch in Step 3 and suffered an extra misprediction on Step 4.

Problem 4 (GShare Two-Level Adaptive Branch Predictor Indexing & Correlation):

A microprocessor features a GShare branch predictor with an 8-entry table (indexed by 3 bits, 2^3 = 8) of 2-bit saturating counters.

• The predictor maintains a 3-bit Global History Register (GHR) where the most recent branch outcome is shifted in from the right (1 for Taken, 0 for Not-Taken).
• The table index is computed by taking the bitwise exclusive-OR (XOR) of the 3 least significant bits of the branch instruction address (shifted right by 2 bits to discard byte alignment zeroes: (PC >> 2) & 0x7) and the 3-bit GHR:

Index = ((PC >> 2) & 0x7) ⊕ GHR.

• All 8 table counters are initialized to state 10 (Weakly Taken).

Consider two correlated branches in a loop:

• Branch B1 at PC = 0x00400014
• Branch B2 at PC = 0x00400018

At the start of the trace, the Global History Register holds GHR = 010 (binary).

The following two branch events occur sequentially:

• Event 1: Branch B1 is evaluated and its actual outcome is Taken (1).
• Event 2: Branch B2 is evaluated and its actual outcome is Not-Taken (0).

1. For Event 1: Calculate the 3-bit PC slice, the GShare table index, the prediction made for B1, and the updated counter state and updated GHR.
2. For Event 2: Calculate the 3-bit PC slice, the new GShare table index using the updated GHR, the prediction made for B2, and the updated counter state and final GHR.
3. Explain why GShare avoids the destructive interference (aliasing) that degrades simple bimodal branch prediction tables.

Solution:

Step 1: Evaluate Event 1 (Branch B1 at PC = 0x00400014)

1. Extract PC bits:

PC = 0x00400014 = 0001 0100 (binary for last byte).

Shift right by 2 bits: 0x14 >> 2 = 20 >> 2 = 5 = 101 (binary).

Mask with 0x7: 101 & 111 = 101 (binary 5).

1. Calculate GShare Index for B1:

Current GHR = 010 (binary 2).

Index = 101 ⊕ 010 = 111 (binary 7).

1. Predict & Update:

- Counter at Index 7 is currently in initial state 10 (Weakly Taken).

- Prediction for B1: TAKEN.

- Actual Outcome: Taken. Result: HIT (Correct).

- Counter at Index 7 increments from 10 to 11 (Strongly Taken).

1. Update GHR:

Shift in actual outcome (1) from right:

New GHR = (010 << 1) | 1 = 101 (binary 5).

Step 2: Evaluate Event 2 (Branch B2 at PC = 0x00400018)

1. Extract PC bits:

PC = 0x00400018 = 0001 1000 (binary for last byte).

Shift right by 2 bits: 0x18 >> 2 = 24 >> 2 = 6 = 110 (binary).

Mask with 0x7: 110 & 111 = 110 (binary 6).

1. Calculate GShare Index for B2:

Current GHR = 101 (binary 5).

Index = 110 ⊕ 101 = 011 (binary 3).

1. Predict & Update:

- Counter at Index 3 is in initial state 10 (Weakly Taken).

- Prediction for B2: TAKEN.

- Actual Outcome: Not-Taken. Result: MISPREDICTION.

- Counter at Index 3 decrements from 10 to 01 (Weakly Not-Taken).

1. Update GHR:

Shift in actual outcome (0) from right:

Final GHR = (101 << 1) | 0 = 010 (binary 2).

Step 3: Why GShare Prevents Destructive Aliasing

In a simple non-global branch table, multiple branches that share the same lower PC bits collide on the exact same counter entry (destructive interference).

GShare solves this by XORing the branch PC with the Global History Register. Even if two branches share the exact same PC, or if the same branch is executed under different execution paths, different prior histories produce completely different table indices (e.g., Index 7 vs. Index 3). This allows the hardware to learn branch correlations (e.g., "if branch 1 was taken, branch 2 is always not-taken") and maintain independent prediction states for identical addresses executed under different program contexts.