Course contentsShow
← Computer Science
Lesson 1178 of 2,87227. Pipelining and PerformanceFree lesson

One-Bit Branch Predictor

Simplest dynamic predictor storing last outcome per branch; limitations with loops and alternating patterns.

One-Bit Branch Predictor

You'll learn: How the simplest dynamic branch predictor works by remembering only the last outcome of each branch.

The Core Idea

A one-bit branch predictor is the most basic form of dynamic branch prediction. It maintains a single bit of history for each branch instruction—essentially remembering "did this branch take last time?" If the branch was taken before, predict taken; if not taken before, predict not taken.

Think of it like a weather forecaster who only remembers yesterday: "It rained yesterday, so I predict rain today."

How It Works

Each branch instruction gets an entry in a Branch History Table (BHT) with one bit:

  • Bit = 1: Last time, branch was taken → predict taken
  • Bit = 0: Last time, branch was not taken → predict not taken

When the branch actually executes, update the bit to reflect the actual outcome.

The Problem with Loops

One-bit predictors struggle with loop behavior. Consider a loop that iterates 10 times:

for (i = 0; i < 10; i++) {
    // loop body
}

The branch at the loop end is taken 9 times, then not taken once to exit. A one-bit predictor will:

  • Mispredict twice per loop: once when entering (predicts not-taken but takes), and once when exiting (predicts taken but doesn't)

For alternating patterns (taken, not-taken, taken, not-taken...), it mispredicts every single time—always guessing the opposite of what happens next.

Accuracy: 50% in Worst Cases

In loops and alternating branches, one-bit predictors can achieve accuracy as low as 50%—no better than random guessing or static prediction.

Key Takeaway: A one-bit branch predictor remembers only the last branch outcome, making it simple but prone to mispredictions on loops and any pattern that doesn't repeat the same outcome consecutively.