How a Branch Predictor Works

<How a Branch Predictor Works

Learning Module>

START >

>

>

<Goals>

goals by end of module

Be able to describe the two different parts of a branch predictor and their parameters

Be able to describe how the branch target buffer and branch prediction works

Be able to describe the pros and cons of different branch prediction designs

Note: This module is designed for people who are already familar with pipeline-architecture processor design already

>

>

00

01

02

Goals

What is it?

BTB

03

04

05

Quiz

Put it all together

Prediction Schemes

<01> SECTION

What is a Branch Predictor

start >

>

>

'To branch or not to branch? That is the question.'

- Me

>

>

//WhAt is a branch predictor

In a scalar pipeline processor, a branch predictor is a piece of hardware that predicts where a given branch instruction's target program counter (PC) is and whether the given branch instruction will be taken or not

>

>

// Why should i care about branch predictors?

In pipelined architectures, there is always a concern of control flow hazards. With branch instructions specifically, the pipeline cannot load in the next instruction as the next instruction to be executed after the branch cannot be calculated until the branch condition itself is calculated, which occurs well after the next instruction would be fetched from memory. This results in a bubble of 2 cycles for each branch instruction in a normal 5-stage pipeline and possibly more in architectures with more stages.

>

>

// How it works

In the first stage (fetch) of a pipeline processor, two important things happen with the Program Counter (PC): 1. The PC enters the branch target buffer (BTB), which predicts the destination of a branch instruction 2. The PC also enters the branch predictor, which decides if the branch will be taken This two-part prediction system helps the processor guess what instruction to execute next before knowing for certain.

>

>

// What happens if the prediction is wrong?

Later in the pipeline, the processor finally calculates the actual branch result. If this actual result differs from the prediction made earlier:1. The processor realizes its mistake 2. It stops processing all instructions that followed the wrong prediction 3. It clears ("flushes") these incorrect instructions from the pipeline 4. It starts fresh by fetching the correct next instruction

Let's say that the first instruction is a branch and it mispredicts. The pipeline won't know until the ALU stage as that's when it computes the branch. Then, on the next cycle, all previous stages are flushed/killed and the correct instruction (at target PC) is used in its place.

<02> SECTION

What is a Branch Target Buffer?

START >

>

>

// Branch target buffer

A branch target buffer is a fixed-sized array that at each index stores the PC of where an instruction would branch to, a tag to validate that the correct PC was used for the index, and a valid bit indicating that the PC listed is accurate. The index into the buffer is a hash of the PC (usually the lowest n bits). The hash size is equal to the log base two of the number of entries the buffer can have.

// How tHe buffer updates

When the branch target gets calculated later on in the pipeline, the target along with the PC at that point gets sent back to the BTB to update it.

<03> SECtion

Different Prediction Schemes

START >

>

>

// WHat goes into a predictor

The prediction part of the branch predictor is essentially a large fixed-sized array, like the BTB, which contains a Smith-Counter.

// WHat's a Smith COunter?

A Smith-Counter is an n-bit (usually 2) long counter where the highest bit tells you whether the branch is taken (1) or not taken (0) and gets updated by adding 1 if the branch was actually taken and subtracting 1 if the branch was not actually taken.

This is a picture of a predictor with a Smith-Counter value of 10 at index 010110, which is a prediction to take the branch.

>

>

// How the smith counter gets updated

During the execution stage, where the condition of the branch gets calculated, the condition along with the index into the predictor array gets sent back to the first stage where it updates the corresponding Smith-Counter.

This is a picture of a 2-bit Smith-Counter written out as a state machine showing the transitions based on whether the branches were actually taken or not.

>

>

// Different ways of calculating the index into a predictor

// pc to Local history Table

// hash the pc

// Combine both

Like the BTB, you can take n bits of the PC to be used as the index into the array.

Take the hashed PC and the GHR and combine them together to create the index into the array. This is known as G-Share.

Take the hashed PC into a table that contains the local branch history at that given index and use that as a new index to get the prediction. This is basically having two tables.

// Global History Register

You can keep track of the last n branches and whether they were taken or not (Branch History Table) and use that as the index into the array. This array is also known as a pattern history table.

>

>

// GSHARE EXAMPLE

These are some pictorial representations of different prediction schemes which are shown to the side.

// GLOBAL history table example

// PC to lht EXAMPLE

<04> SECTION

Combining Predictor with BTB

START >

>

>

// how to use the outputs from the btb and predictor

After getting the tag, target, and valid bit from the BTB, and after getting the prediction from the predictor, the tag will be compared to the remaining bits of the PC that weren't used for the hash to make sure that the tag has the correct value. If the tag is verified to be correct and the valid bit is set, then the prediction gotten from the predictor is used. If it predicts 0, then the next instruction to be used will be the next instruction directly after. If it predicts 1, then the target from the BTB will be the next instruction to be used.

>

>

For more information, here is a wonderful video on the topic of branch prediction by the Youtube channel, Computerphile!

<QUIZ>

Test your knowledge on what you've learned!

START >

QUESTION 1 of 5

QUESTION 2 of 5

QUESTION 3 of 5

QUESTION 4 of 5

QUESTION 5 of 5

¡congratulations!

>

Module completed

//Resources

>

>

+ info

< BACK

START >

00