Advanced Instruction Level Parallelism (ILP)

Compiler-based mechanisms are static approaches to resolving pipeline hazards — meaning these optimizations are performed entirely ahead of time (at compile time) by the software, rather than at runtime by the hardware.

Loop Unrolling

The primary compiler-based mechanism discussed is loop unrolling. Loop unrolling takes a loop and statically replicates its body multiple times, adjusting the loop termination code to step by larger increments.

• Example: Consider a loop multiplying two arrays: A[i] = B[i] * C[i]. In an unrolled version, you would step the loop control variable by 2 (or more) instead of 1. Inside the new loop, you compute both A[i] = B[i] * C[i] and A[i+1] = B[i+1] * C[i+1] sequentially.
• The Benefits: Unrolling eliminates half of the control hazards because there are fewer branch instructions evaluated. Additionally, it slashes the overhead of updating loop control variables and pointers (e.g., pointers to A, B, and C) by half. You can also space out the loads and stores to avoid data hazards.
• The Trade-offs: The resulting code executes significantly fewer instructions overall, improving performance. However, because you are replicating the loop body, the actual source code size (and compiled binary) becomes larger.
• Compiler Flags: Modern compilers inherently do this for you. When you use optimization flags like -O2 or -O3 (unlike -O0), the compiler automatically unrolls loops. If the number of iterations is not perfectly divisible by the unrolling factor (e.g., unrolling by 3 for an array of 100 elements), the compiler handles the remainder by placing a few standard iterations outside the main unrolled loop.

Branch Prediction and Frequencies

Control instructions account for roughly 12% to 20% (about one out of every seven) of all executed instructions. Hardware architects study code execution to find ways to handle these efficiently.

• 66% of all branches are taken. Therefore, relying purely on a static “predict not taken” strategy would only benefit us 33% of the time.
• 85% of backward branches are taken. Backward branches are typically used for loops (e.g., jumping back to the top of a for or while loop), so they are highly likely to be taken.

Because static prediction is insufficient for maximum performance, modern CPUs rely on dynamic prediction — making predictions on the fly based on runtime behavior.

Branch History Table (BHT)

A Branch History Table (BHT) is a simple, dynamic 1-bit prediction scheme. It records the local branching history of a line of code: a 1 means the branch was taken the last time it executed, and a 0 means it was not taken.

• Spatial Locality: BHT relies on a variation of spatial locality applied to behavior — if a specific branch was taken the last time, it will probably be taken the next time.
• Why it works great for loops: For standard loops, the BHT predicts correctly every single time except for two instances: the very first iteration (because it has no history) and the very last iteration (when the loop terminates).

Wrinkles of the BHT:

1. How many entries should the table have? Ideally, you would need one entry for every possible line of code. If you have 16 MB of memory (which holds 4 million 4-byte instructions), you would theoretically need 4 million entries.
2. Where are we going to save these entries? This table cannot be saved in the heap, stack, or globals (RAM) because fetching from memory takes too long (>0.1 ns), and the predictor must deliver a result in less than one clock cycle. It must be stored in the CPU using flip-flops. However, storing millions of flip-flops is physically impossible.
3. The BHT as a Hash Table: To solve the space issue, the BHT is implemented as a hash table of a practical size (e.g., 1024 entries).
4. The Hashing Function Used: Because the hash must evaluate in under 0.1 nanoseconds, complex mathematical hashing is impossible. Instead, the CPU uses the Program Counter (PC) address. Since RISC-V instructions are 4 bytes long, the lowest two bits of every address are always 00. The hashing function simply masks off (ignores) the lowest two bits and reads the next immediate set of bits (e.g., the next 10 bits for a 1024-entry table). This is virtually instantaneous, though it does cause unavoidable collisions, requiring the pipeline to cancel instructions when a collision yields an incorrect prediction.

Decode History Table (DHT)

A Decode History Table (DHT) is a variation of the BHT. Instead of hashing based on the address of the branch instruction itself, a DHT hashes based on the target address of the branch. This was used in architectures like the DEC Alpha, whose pipeline could resolve target addresses earlier than standard RISC-V pipelines.

n-Bit Prediction

To prevent a single anomalous branch behavior from entirely flipping a prediction, CPUs use n-bit prediction (where n>1, typically n=2). A 2-bit predictor provides four states (0, 1, 2, 3), allowing the predictor to require two mispredictions before completely changing its mind.

Saturating Counter

The n-bit entry acts as a saturating counter. It maxes out at its highest value (e.g., 11 in binary) and bottoms out at its minimum (00), meaning 11 + 1 remains 11, and 00 - 1 remains 00.

What Happens in the EX Stage

While the prediction is made in the Instruction Decode (ID) stage, the actual counter update happens later in the Execute (EX) stage. If the branch is definitely taken, the EX stage increments the counter. If it is not taken, it decrements the counter. This update happens independently of whatever the initial prediction was.

Initial Value for the Counter

CPU architects must decide how to initialize the counter.

• 01 (1): Starts near the middle (unbiased), but leans slightly toward "not taken".
• 10 (2): Unbiased, but leans toward "taken." This is highly logical because 66% of branches are taken, matching general code statistics.
• 11 (3): A bolder start that guarantees the first iteration of any backward loop is predicted correctly.
• Advanced Initialization: The CPU could selectively initialize forward branches to 10 or 01 and backward branches (loops) to 11.

Correlating Prediction

Correlating predictors recognize that the behavior of some branches is tied to the behavior of other branches (e.g., an outer loop’s branch condition is highly correlated with the inner loop’s completion).

The (m,n) Predictor: This captures both global and local histories.

• m represents the global history (the outcome of the last m branches across the entire program). This acts as a selector.
• n represents the local predictor size (e.g., a 2-bit counter).

How it works: For every line of code, instead of one local predictor, there are 2m local predictors. The global m-bit history tells the CPU which of the local n-bit predictors to select for the current branch.

Tournament Prediction

Tournament prediction runs multiple types of predictors simultaneously and uses a “scorekeeper” to pick the most accurate one at runtime.

Local vs. Global Predictors: A local predictor tracks the pattern of a single specific branch (great for standalone loops). A global predictor tracks the history of all recent branches (great for correlated nested loops).

The Difference in the Tournament: Unlike correlating prediction which mixes the two, tournament prediction maintains one local predictor per line of code and one overarching global predictor. It adds a scorekeeper counter to track which predictor has been more accurate recently.

Updates in the EX Stage:

• The Predictors (local and global) are updated based on the direction of the branch (incremented if taken, decremented if not taken).
• The Scorekeeper is updated based on accuracy. If the local predictor was correct, it shifts toward the local state; if the global predictor was correct, it shifts toward the global state. This yields an exceptional ~97% prediction accuracy

Improving Branch Prediction: Early Target Identification

To achieve maximum instruction-level parallelism and eliminate pipeline stalls (pipeline bubbles), it is not enough to accurately predict the direction (taken or not taken) of a branch. The processor must also determine the branch’s target address as early as possible so the correct instruction can be fetched without delay. Hardware architects utilize several techniques to identify these targets during the Instruction Fetch (IF) stage.

The Branch-Target Buffer (BTB)

A Branch-Target Buffer (or branch-target cache) is a specialized hardware cache used to predict the next instruction address before the fetched instruction is even fully decoded.

• How it Works: During the Instruction Fetch (IF) stage, the processor simultaneously sends the Program Counter (PC) to the instruction memory and to the BTB. If the PC matches an entry in the BTB, the hardware knows it is dealing with a branch and immediately begins fetching from the predicted target PC associated with that entry, effectively reducing the branch penalty to zero cycles if predicted correctly.
• What it Stores: The BTB only stores entries for branches that are predicted as taken, because untaken branches simply fall through to the next sequential instruction. Each entry in the table stores the address of the known branch instruction and its predicted target address.
• The Hash Function: Because it must be evaluated in less than a tenth of a nanosecond, the BTB cannot use a complex hashing algorithm or be stored in main memory. It is implemented as a hardware hash table inside the CPU that takes the branch instruction’s PC address as its input key. In RISC-V, since all instructions are exactly 4 bytes long, the lowest two bits of any instruction address are always 00. The hashing function simply masks off (ignores) these two lowest bits and uses the immediately following bits to index into the buffer, making the lookup virtually instantaneous.

Branch Folding

Branch folding is an optimization of the BTB where the buffer stores the actual target instruction(s) instead of, or in addition to, the target address.

• How it Works: When the BTB signals a hit for an unconditional branch, the pipeline substitutes the target instruction stored in the buffer directly into the Instruction Register (IR) in place of the branch instruction. This allows the target instruction to enter the pipeline immediately, effectively executing the branch in zero clock cycles.
• RISC-V 32-bit Storage Advantage: In a 64-bit architecture like RISC-V, standard memory addresses are 64 bits long. However, RISC-V instructions are encoded with a fixed length of 32 bits. This means that the 64 bits of storage space normally required for a single target address in the BTB can comfortably store two 32-bit target instructions at absolutely no extra hardware cost.
• Folding Multiple Instructions: Because the hardware can store multiple instructions in the buffer space, the CPU can fold multiple instructions at once. In scenarios involving very short, tight loops containing multiple branches, the processor can pull multiple instructions into the pipeline simultaneously. This effectively allows the CPU to make multiple branch predictions at the same time, behaving similarly to a correlating predictor.

Indirect Jump Stacks

While the BTB is excellent for standard branches, it struggles with indirect jumps — where the destination address changes dynamically at runtime. The most common examples of these are procedure/function returns (e.g., using the jalr instruction) or deeply nested recursive function calls.

An indirect jump stack (also known as a return address stack) is a small, dedicated hardware stack made of internal CPU flip-flops used exclusively to predict return addresses.

How it Works and Examples: The hardware caches the most recent return addresses by pushing them onto the stack at every function call and popping them off at every function return.

• Example: If a function invokes another function using the Jump and Link (jal) or Jump and Link Register (jalr) instruction, the CPU pushes the return address (the next sequential instruction, or PC + 4) onto the top of the indirect jump stack.
• Later, when the function completes and executes its return instruction, instead of waiting for the pipeline’s Execute (EX) stage to slowly compute the return target by adding an offset to the register, the IF stage pops the predicted address directly off the top of the indirect jump stack.

Performance: Because call depths are typically not extremely deep, this mechanism is highly effective. Simulation studies show that an indirect jump stack with just 16 entries achieves an astonishing 95% accuracy in correctly predicting return addresses.

🔙 Back to all notes 𝕏 Let’s Connect

Backlinks: *Computer Architecture Notes: A Quantitative Guide to Modern Computing*