分支预测 | Branch Prediction

定义 | Definition

分支预测是一种处理器技术，用于猜测程序中的分支（如条件跳转）是否会被执行，从而提高指令流水线的效率。

Branch prediction is a processor technique used to guess whether a branch (e.g., a conditional jump) will be taken or not, thereby improving the efficiency of the instruction pipeline.

分类 | Types

静态预测 | Static Prediction

静态预测在编译时进行，不依赖于运行时的历史信息。

Static prediction is done at compile time and does not rely on runtime history.

示例 | Example

始终预测不跳转：假设所有条件跳转都不会执行。 Always predict not taken: Assumes all conditional jumps will not be executed.
后向跳转预测跳转：假设所有向后的跳转（通常是循环）都会执行。 Predict backward branches as taken: Assumes all backward jumps (usually loops) will be executed.

动态预测 | Dynamic Prediction

动态预测在运行时进行，依赖于过去的执行历史。

Dynamic prediction is done at runtime and relies on the execution history.

单比特预测 | One-Bit Predictor

每个分支指令对应一个比特，记录上一次是否跳转。

Each branch instruction is associated with a single bit indicating whether it was taken the last time.

如果上次跳转，则预测跳转；否则预测不跳转。
If the last time it was taken, predict taken; otherwise, predict not taken.

两比特预测 | Two-Bit Predictor

使用两比特状态机减少错误预测的概率。

Uses a two-bit state machine to reduce the likelihood of misprediction.

状态转换 | State Transition:

00 (强不跳转 | Strongly Not Taken)
01 (弱不跳转 | Weakly Not Taken)
10 (弱跳转 | Weakly Taken)
11 (强跳转 | Strongly Taken)

只有在两次连续预测错误时才会改变预测方向。
Only change prediction direction after two consecutive mispredictions.

# Example in Pseudocode
state = "00"  # Initial state: Strongly Not Taken
if branch_taken:
    if state in ["10", "11"]:
        state = "11"  # Strongly Taken
    else:
        state = "10"  # Weakly Taken
else:
    if state in ["00", "01"]:
        state = "00"  # Strongly Not Taken
    else:
        state = "01"  # Weakly Not Taken

全局历史预测 | Global History Predictor

使用全局分支历史寄存器记录最近的分支结果。

Uses a global branch history register to record recent branch outcomes.

# Example in Pseudocode
GHR = 0b000  # Global History Register, 3 bits for simplicity
PHT = [0, 0, 0, 0, 0, 0, 0, 0]  # Pattern History Table
 
def predict_and_update(branch_taken):
    index = GHR
    prediction = PHT[index] > 1  # Assuming 2-bit counters in PHT
    if branch_taken:
        PHT[index] = min(PHT[index] + 1, 3)
        GHR = ((GHR << 1) | 1) & 0b111  # Update GHR with taken
    else:
        PHT[index] = max(PHT[index] - 1, 0)
        GHR = (GHR << 1) & 0b111  # Update GHR with not taken
    return prediction
 
# Simulate a branch outcome
print(predict_and_update(True))  # Example prediction

重要性 | Importance

提高流水线效率 | Improve Pipeline Efficiency

分支预测可以减少流水线停顿，使处理器更有效率。

Branch prediction reduces pipeline stalls, making the processor more efficient.

增加吞吐量 | Increase Throughput

通过预测分支，提高指令执行的吞吐量。

By predicting branches, it increases the instruction execution throughput.

误预测处理 | Handling Mispredictions

回滚 | Rollback

在误预测发生时，处理器需要回滚到正确的分支路径。

When a misprediction occurs, the processor needs to roll back to the correct branch path.

性能影响 | Performance Impact

误预测会导致流水线停顿，降低性能。

Mispredictions cause pipeline stalls, reducing performance.

Zephyr's Notes on ISCS & CBMS, UTokyo

Explorer