GShare is a simple yet highly effective branch prediction algorithm that significantly enhances processor performance by accurately predicting the outcome of conditional branches in a program. It is widely used due to its balance of accuracy and implementation simplicity.
Core Mechanism
At its heart, GShare combines information about the global history of recent branches with the current instruction address of the branch being predicted. It then uses a simple hashing function to merge these two pieces of data, which serves as an index into a table of two-bit counters. These counters record past branch behaviors and dictate the prediction.
Key Components of GShare
Understanding GShare involves familiarizing oneself with its three main components:
1. Global History Register (GHR)
The Global History Register (GHR) is a shift register that stores the outcomes of the most recently executed conditional branches across the entire program. If a branch was taken, a '1' (or similar representation) is shifted into the GHR; if it was not taken, a '0' is shifted in. The length of the GHR (typically a few bits to a few tens of bits) determines how much global context the predictor considers. This register provides a global "memory" of program execution flow.
2. Pattern History Table (PHT)
The Pattern History Table (PHT) is a crucial component, typically implemented as an array or table of two-bit saturating counters. Each entry in the PHT corresponds to a unique combination of the branch's instruction address and the global history.
These two-bit counters are essential for adaptive prediction:
| State | Value | Prediction | Next if Not Taken | Next if Taken |
|---|---|---|---|---|
| Strongly Not Taken | 00 |
Not Taken | 00 |
01 |
| Weakly Not Taken | 01 |
Not Taken | 00 |
10 |
| Weakly Taken | 10 |
Taken | 01 |
11 |
| Strongly Taken | 11 |
Taken | 10 |
11 |
- A counter in the '00' or '01' state indicates a prediction of "Not Taken."
- A counter in the '10' or '11' state indicates a prediction of "Taken."
- The term "saturating" means the counter stops incrementing at '11' and stops decrementing at '00', preventing it from continuously flipping with oscillating branch patterns.
3. Hashing Function
The hashing function is the mechanism that combines the local and global context to derive an index for the PHT. In GShare, this is typically a simple XOR operation between the lower bits of the branch's Instruction Address (PC) and the contents of the Global History Register (GHR).
For example:
PHT_Index = (Lower_Bits_of_PC) XOR (GHR_Value)
This XOR operation allows GShare to capture correlations between the branch's location in the code and the preceding sequence of branch outcomes, enabling more accurate predictions for branches that exhibit context-dependent behavior.
How the Prediction is Made
The process of making a prediction with GShare involves these steps:
- Encounter Branch: When a conditional branch instruction is fetched, its instruction address (PC) is used.
- Generate Index: The lower bits of the PC are XORed with the current value of the Global History Register (GHR). This produces a unique hash value.
- Access PHT: The hash value serves as an index into the Pattern History Table (PHT).
- Determine Prediction: The two-bit counter found at the indexed PHT entry is read. Based on its value (as shown in the table above), the branch is predicted as either Taken or Not Taken.
Updating the Predictor
After the actual outcome of the branch is determined (i.e., after the branch executes and its target is known), the GShare predictor "learns" from this outcome:
- Update PHT Counter: The two-bit counter in the PHT (the one that was used for the prediction) is updated based on the actual outcome:
- If the branch was actually taken, the counter is incremented towards '11' (saturating at '11').
- If the branch was actually not taken, the counter is decremented towards '00' (saturating at '00').
- Update GHR: The Global History Register (GHR) is updated by shifting in the actual outcome of the just-resolved branch. For instance, a '1' might be shifted in for taken, and a '0' for not taken, discarding the oldest history bit.
This continuous feedback loop allows GShare to adapt to changes in program behavior and refine its predictions over time.
Practical Insights and Benefits
GShare's effectiveness stems from several key advantages:
- Contextual Awareness: By combining the local branch address with global history, GShare can differentiate between instances of the same branch that behave differently depending on the preceding control flow. This helps it capture complex branch patterns.
- Simplicity and Efficiency: The use of simple XOR operations and two-bit counters makes GShare computationally inexpensive and fast, which is critical for high-performance processors.
- Adaptive Learning: The saturating counters allow the predictor to be robust against occasional mispredictions and to slowly adapt to changes in a branch's common behavior, making it more accurate over long execution runs.
GShare's ability to capture global correlations while maintaining a straightforward implementation has made it a foundational element in the design of many modern branch predictors in high-performance CPUs.
