Foundations — Branch target buffer (BTB)

Before you can understand the BTB topic, you must be able to read every symbol it throws at you. This page builds each one from nothing — a plain-words meaning, a picture, and the reason the topic needs it. Read top to bottom; each idea leans on the one above it.

1. The instruction and the program counter (PC)

Memory addresses are written in hexadecimal — a counting system that uses digits 0-9 then letters a-f, and is marked with a leading 0x. So 0x1004 is just an address (a house number for one instruction). You don't need to do hex arithmetic; you only need to know 0x1004 names a spot in memory.

Look at the figure: instructions live in a vertical stack of memory slots, and the PC (the coral arrow) points at exactly one of them.

2. "PC + 4" — the default next step

Normally, after running one instruction, the CPU moves to the very next one in memory. On many machines each instruction is 4 bytes wide, so the next address is the current one plus 4.

The "$+4$" is just the width of one instruction. On a machine with 2-byte instructions it would be "$+2$". The important idea is: going straight is the default.

3. Taken vs. not-taken, target vs. fall-through

A conditional branch (like "jump only if two numbers are equal") has two possible outcomes:

• Taken: the condition is true, so the PC jumps to the target.
• Not taken (also called fall-through): the condition is false, so the PC just does PC+4 like normal.

In the figure, the green path is "taken" (jump to the target) and the slate path is "not taken" (fall through to the next line). The BTB stores only the green arrow's destination — where a taken branch lands. It never decides which arrow to follow; that is a different unit's job (Section 6).

4. The pipeline: fetch, decode, execute

A modern CPU is like an assembly line. It does not finish one instruction before starting the next; instead it splits the work into stages and keeps them all busy. This is called a pipeline (Pipeline Hazards explores what goes wrong here).

The three stages you must know:

The figure shows instructions flowing left-to-right through the three stages, one stage per clock cycle (one tick of the CPU's heartbeat).

5. The instruction cache (I-Cache) — the BTB's shape twin

To fetch fast, instructions are kept in a small speedy memory called the Instruction Cache (see Instruction Cache (I-Cache)). The BTB is built the same way a cache is built, so the cache vocabulary transfers directly. From Cache Organization you need three words:

Why split the PC into "lower bits pick the row, upper bits verify"? Because a small table (say 64 rows) cannot have a row for every possible address. Many addresses are forced to share the same row. The index gets you to the shared row instantly; the tag checks whether the address currently living there is yours.

6. Hit, miss, and the branch predictor

Two close cousins the parent note mentions:

• Return Address Stack (RAS) — a special little stack for predicting where function returns jump to (a branch target the BTB alone predicts poorly).
• Branch Delay Slots — an older trick that hid the branch penalty by running one extra instruction after the branch; a different solution to the same delay the BTB attacks.

7. Reading the topic's little equations

The parent note uses a compact bit-slicing notation. Decode it once here:

With those, the parent's whole lookup reads in plain English: chop the PC to get a row number, jump to that row, compare the stored tag against my PC's top bits; if equal it's a hit and the stored target is where I go.

Prerequisite map

The map reads: the PC and PC+4 give us the idea of a branch; the pipeline explains why the target arrives too late; cache structure gives us index/tag/aliasing; the predictor supplies direction. All of them feed the BTB.

Equipment checklist

Test yourself — cover the right side and answer before revealing.