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.