BitFlow

Gshare Branch Predictor

advanced · state_machine · 360 XP

Sign in to write your solution, run it in the simulator and submit it for grading.

Sign in or create a free account →

Problem

Gshare Branch Predictor Implement a **Gshare predictor** for a 5-bit PC and 5-bit global history register (GHR). The PHT (Pattern History Table) is indexed by `PC[4:0] XOR GHR[4:0]`, with 32 entries of 2-bit saturating counters. **Counters:** - `2'b00` = strongly not taken - `2'b01` = weakly not taken - `2'b10` = weakly taken - `2'b11` = strongly taken **On each cycle:** 1. Compute index: `pht_idx = pc[4:0] XOR ghr[4:0]` 2. Read PHT[pht_idx] to make prediction 3. Input actual outcome (`branch_taken`) 4. Update counter at PHT[pht_idx]: - If actual=taken and counter<3: increment - If actual=not-taken and counter>0: decrement 5. Update GHR (shift left, insert new bit): `ghr = {ghr[3:0], branch_taken}` **Interface** | Port | Direction | Description | |----------------|-----------|-------------------------------------| | `clk` | input | Clock | | `rst` | input | Reset (initializes PHT to 2'b10) | | `pc` | input | Program counter (5 bits) | | `branch_taken` | input | Actual branch outcome (1=taken) | | `prediction` | output | Predicted outcome (1=predict taken) | **Prediction rule:** `prediction = pht[pht_idx][1]` (MSB of counter) **Testbench notes:** - Always-taken branch: counter saturates to `2'b11`, prediction always 1 - Always-not-taken: counter saturates to `2'b00`, prediction always 0 - Alternating branch: prediction accuracy oscillates, eventually settles - Reset: verify PHT initialized to `2'b10` (weakly taken) across all 32 entries This problem appears in RISC-V processor design interviews and ARM CPU design courses.

Constraints

  • PHT: 32 entries (5-bit index), each 2-bit saturating counter.
  • GHR: 5-bit shift register updated on every branch.
  • Index: pht_idx = pc XOR ghr (bit-wise).
  • Prediction: MSB of counter (pht[idx][1]).
  • Counter update: saturating increment/decrement (don't overflow/underflow).

Examples

Input: Always branch taken (pc=0, branch_taken=1 for 100 cycles)

Output: Counter at PHT[0] saturates to 2'b11; prediction=1 after 3 cycles

Strong prediction converges

Input: Branch at pc=5, outcome alternates (1,0,1,0...)

Output: Prediction lags actual by ~1 cycle; accuracy stabilizes at ~50%

Alternating pattern

Input: Reset

Output: PHT[0..31] all 2'b10, GHR=0

Initialization

Common questions

What does the Gshare Branch Predictor problem ask you to build?
Gshare Branch Predictor Implement a **Gshare predictor** for a 5-bit PC and 5-bit global history register (GHR). The PHT (Pattern History Table) is indexed by `PC[4:0] XOR GHR[4:0]`, with 32 entries of 2-bit saturating counters.
What constraints does Gshare Branch Predictor have?
PHT: 32 entries (5-bit index), each 2-bit saturating counter.; GHR: 5-bit shift register updated on every branch.; Index: pht_idx = pc XOR ghr (bit-wise).; Prediction: MSB of counter (pht[idx][1]).; Counter update: saturating increment/decrement (don't overflow/underflow).
What is an example input and output for Gshare Branch Predictor?
Input Always branch taken (pc=0, branch_taken=1 for 100 cycles) gives output Counter at PHT[0] saturates to 2'b11; prediction=1 after 3 cycles. Strong prediction converges
Which Verilog concepts does Gshare Branch Predictor practise?
state_machine, capstone, branch-predictor, interview, machine-learning.