How Branch History Tables Use Binary Address Bits

Modern microprocessors use dynamic branch prediction to guess the outcome of conditional branches before they execute, preventing costly pipeline stalls. This hardware relies on Branch History Tables (BHT) and Pattern History Tables (PHT) indexed using specific binary bits extracted from the branch instruction’s memory address. This article explains the mechanics of address extraction, bit selection, table indexing, outcome tracking via saturating counters, and advanced XOR-based indexing schemes.

Extracting the Binary Index from the Instruction Address

Every instruction in a program resides at a unique memory address tracked by the Program Counter (PC). When a processor encounters a branch instruction, it uses the binary representation of this address to locate the prediction entry in hardware tables.

In modern computer architectures, instructions are aligned in memory (typically to 32-bit/4-byte boundaries). Because of this alignment, the lowest bits of the PC are always zero: * For 32-bit aligned architectures, the least significant 2 bits ([1:0]) are always 00. * For 64-bit aligned instructions, the lowest 3 bits ([2:0]) are always 000.

Hardware ignores these fixed trailing zeros. To index a table with \(2^k\) entries, the branch prediction hardware extracts a \(k\)-bit slice directly above the ignored alignment bits (for example, bits [k+1:2]).

Example: 32-bit PC with a 1024-entry (10-bit index) table
+------------------------------------+--------------------+--------+
| Unused Tag / Higher Bits (20 bits) | Index Bits (10 bits)| Fixed0 |
| PC[31:12]                          | PC[11:2]           | PC[1:0]|
+------------------------------------+--------------------+--------+

Accessing Saturating Counters in History Tables

The selected \(k\)-bit binary number serves as a direct memory index into the table. Each entry in a standard Branch History Table contains a state machine, most commonly a 2-bit saturating counter:

When a branch instruction is fetched: 1. The hardware extracts the index bits from the PC. 2. It retrieves the 2-bit value at that specific index. 3. The most significant bit of the counter determines the prediction (0 = Not Taken, 1 = Taken). 4. Once the actual outcome is resolved during execution, the hardware increments the counter (up to 11) if the branch was taken, or decrements it (down to 00) if the branch was not taken.

Handling Branch Aliasing

Because the table has a finite number of entries, two completely different branch instructions with different high-order address bits can share the exact same low-order index bits. This condition is called branch aliasing or interference.

Correlating Predictions: The Gshare Indexing Scheme

To reduce aliasing and account for surrounding program flow, modern processors combine address bits with dynamic branch history rather than using address bits alone.

In a Gshare predictor, the hardware maintains a Global History Register (GHR)—a shift register where each bit represents the outcome of the most recent branches across the entire program. The hardware calculates the table index using a bitwise XOR operation between the binary PC bits and the GHR bits:

\[\text{Index} = \text{PC}[k+1:2] \oplus \text{GHR}[k-1:0]\]

This binary hashing mechanism ensures that the same branch address produces different table indices depending on the path taken through the program, significantly reducing destructive aliasing and improving overall branch prediction accuracy.