Branch Predictor Simulator

A simulator for dynamic branch prediction written in C++. Implements and compares three classic prediction schemes — Bimodal, GShare, and a Hybrid meta-predictor — using 2-bit saturating counters and a configurable global branch history register (BHR). Accepts real branch trace files and reports misprediction rates along with final predictor table contents.

Features

• Bimodal predictor — indexed by PC bits, no history
• GShare predictor — PC bits XORed with a global branch history register (BHR)
• Hybrid predictor — a meta-predictor that dynamically selects between GShare and Bimodal using a chooser table
• 2-bit saturating counters throughout (range 0–3)
• Configurable table sizes via power-of-2 index widths
• Detailed final table contents printed on exit

Build

Requires g++ and make.

make

This produces the sim binary.

Usage

The predictor mode is selected via the first argument.

Bimodal:

./sim bimodal <M2> <trace_file>

GShare:

./sim gshare <M1> <N> <trace_file>

Hybrid:

./sim hybrid <K> <M1> <N> <M2> <trace_file>

Parameter	Description
M2	Bimodal table size = 2^M2 entries
M1	GShare table size = 2^M1 entries
N	Number of BHR bits used in GShare XOR (N ≤ M1)
K	Chooser table size = 2^K entries (Hybrid only)
trace_file	Path to branch trace file

Examples

# Bimodal with 2^4 = 16-entry table
./sim bimodal 4 trace.txt

# GShare: 2^9 table, 3-bit history
./sim gshare 9 3 trace.txt

# Hybrid: 2^8 chooser, gshare(2^9, 3-bit BHR), bimodal(2^8)
./sim hybrid 8 9 3 8 trace.txt

Trace File Format

Each line is one branch:

<hex_address> <outcome>

• t = taken
• n = not taken

Example:

00a08400 t
00a08400 t
00a08400 n

Output

Example (Bimodal):

COMMAND
./sim bimodal 4 trace.txt
OUTPUT
number of predictions:    100000
number of mispredictions: 11242
misprediction rate:       11.24%
FINAL BIMODAL CONTENTS
 0	2
 1	3
 2	1
 ...

Example (Hybrid):

COMMAND
./sim hybrid 8 9 3 8 trace.txt
OUTPUT
number of predictions:    100000
number of mispredictions: 8901
misprediction rate:       8.90%
FINAL CHOOSER CONTENTS
...
FINAL GSHARE CONTENTS
...
FINAL BIMODAL CONTENTS
...

Implementation Details

• Bimodal indexing: lower 2 PC bits discarded (byte-offset), next M2 bits used as index.
• GShare indexing: take M1 PC bits, XOR the top N of them with the BHR, leave the bottom (M1−N) bits unchanged.
• BHR update: shift right, insert actual outcome into MSB position. Updated after every branch.
• Hybrid update rule: only the sub-predictor selected by the chooser is updated. The chooser counter increments if GShare was correct and Bimodal was wrong, decrements if vice-versa, and stays unchanged if both agree.
• Counter initialization: all prediction counters start at 2 (weakly taken); chooser counters start at 1 (weakly favoring Bimodal).

Technologies

• Language: C++ (C++11 compatible)
• Build: GNU Make + g++
• Standard libraries: <stdio.h>, <stdlib.h>, <string.h>, <vector>