5.0 Branch prediction

Question 1

What stage is branch prediction a part of?

Answer 1

Instruction fetch.
This is to allow the stage to fetch as many, and as useful, instructions as possible at the same time.

Question 2

What two things does branch prediction do?

Answer 2

Predict if branch is taken, and the target address

Question 3

How does pipeline depth affect cost of mispredicted branches?

Answer 3

Cost is proportional to pipeline depth

Question 4

What are the two ways of doing branch direction prediction

Answer 4

Statically: Before program execution, done by compiler/programmer inserting a hint

Dynamically: during program execution, use global and local history to make predictions, done in hardware

Question 5

What are some advantages with static branch prediction?

Answer 5

Easy to implement, little hardware needed.

Question 6

What are a disadvantage with static branch prediction

Answer 6

Prediction is the same regardless of dynamic behaviour

Question 7

What are the three types of static prediction?

Answer 7

Rule, program, profile-based

Question 8

Define rule-based static prediction

Answer 8

Implement a rule that is always used, in the pipeline

Rules:
- Not taken (sequential fetch)
- Always taken (requires compute branch target, a little more complex, branch target known at decode stage)
- Back taken forward not taken (combine these two, loops are typically taken)

Question 9

Define program-based prediction

Answer 9

Typically more accurat then rule-based

requires a hint in opcode, specifying behaviour for different branch-types:

• If branch is loop - take
• if compare pointer to NULL - not take
• if compare pointers - take branch to inequality

Question 10

What is profile based prediction?

Answer 10

When you first compile and execute a binary with a certain set of training input data.

This run collects profile data that defines how branching is taken statistically

Use this to predict branches. over 50% - taken, under - not taken

Question 11

What context can dynamic branch prediction use to predict branches?

Answer 11

Local history: The branch’s own history

Global history: Other branches’ history

Question 12

what is a bimodal predictor

Answer 12

The hash of the PC is used as a pointer into a buffer holding a counter that defines branch outcomes

Using a two bit predictor, predict taken if 11 or 10, and not taken if 01 or 00. if branch was actually taken +1, if not taken -1.

Question 13

What are the components of 2-level predictors?
How does a global 2-level predictor work?

Answer 13

Uses two levels of branch history to make predictions (bimodal only uses the branch address)

Two level use local history or global history

History: Outcome of prior branch executions

History acts as shift register. Newest outcome is inserted, oldest is discarded

1st level for a global predictor is a Branch History Register containing h bits and the global history. h bits shows branch outcome of last h branches

Then take the hash of the branch address and concatenate with the global history and use this as index to a pattern history table containing counters.

Question 14

Why does a two-level global predictor work?

Answer 14

Because there is correlation between branches.

If a branch is taken - it is probable that the next also will be taken

Question 15

What is a two level predictor using local history?

Answer 15

Have a 1st level branch history table containing local history.

Hash the PC and use this as index to the BHT.

Concat the PC hash with the entry from BHT and index into pattern history table that contains counter.

Question 16

Why does a two level local predictor work?

Answer 16

Branches have local behaviour (alternating, loops)

Question 17

How does the number of bits used in the PC hash affect the branch predicor implementation-type?

Answer 17

m: number of bits retrieved from the PC, used to index pattern history table

if m is 0: all branches share the same pattern history table - this would be a global history table

if m is not 0: per-address pattern history table

Question 18

What is a gshare predictor

Answer 18

Instead of concatinating the h bits from the global history with the m bits from the branch address, these are XORed

Question 19

What are some causes of mispredictions when using dynamic prediction?

Answer 19

Some branches are just hard to predict

Can be caused by interference: predictor is to small for branches - branches with different behaviour may be mapped onto the same PHT entry

Branch behaviour doesn’t match branch predictor type. Global predictor, but branch doesn’t use global state

Question 20

What is hybrid branch prediction?

Answer 20

combine different type of branch predictors, and learn which ones are most accurate.

Question 21

What is a tournament predictor?

Answer 21

PC hash is used to index into the metapredictor table. This table contains a counter that records the behaviour of the predictors used. The metapredictor entry is used to choose what predictor result to use. If entry < 2 P1 is used, entry >= 2 P2 is used.

The metapredictor counter is updated on every prediction
- if both predictors correct/incorrect - do nothing
- if P1 correct - decrement
- if P2 correct - increment

Entries in P1 and P2 are updated every prediction, regardless of which one is used

Question 22

What is a BTB (Branch target buffer) or Branch Target Address Cache (BTAC)

Answer 22

Input: branch address (PC)
Output: Target address

Accessed in the same cycle as we access the instruction cache

If an instruction is a branch, we use the target address as PC in next cycle

Used in IF stage. If target is cached, we are able to continue fetching without loosing cycles

Target is used to speculatively fetch in next cycle

Question 23

What is a RAS (return address stack)

Answer 23

Have a circular buffer where you push the return address (PC + 4) when doing a function call. Pop address upon return.

It is easy to predict function calls, not return address. This is because multiple addresses can call a function - and therefore be a possible return address

If depth of calls exceeds the RAS-size, we will have problems

Question 24

What is speculative execution?

Answer 24

Predict branch target address and start execution along predicted path.

there might be multiple branches in flight along the predicted path - to keep track of this, tags are added to the instructions along the given paths.

Question 25

What happens when a branch is correctly predicted?

Answer 25

Tags are deallocated
instructions become non-speculative

Question 26

What happens when a branch is mispredicted?

Answer 26

Wrong path instructions are nullified
Start fetching instructions along correct path

Question 27

What is the structure of the branch target buffer (BTB)

Answer 27

PC is used as input(tag) to table

If we hit, take the target address and use it speculatively as the next PC to fetch in next cycle

Question 28

How does a BTB/RAS access work in hardware?

Answer 28

On function call, take branch-address + 4 and store into RAS.

In parallell, you access the BTB with the branch address to get the target address.

I the branch is a return, instead of taking the result from the BTB, pop the top most element of the RAS, and use this as the target address.

Question 29

How does return address prediction work in the pipeline?

Answer 29

Fetch stage:
- Use branch address (comes from PC) to access BTB/RAS
- If you hit in the BTB use this as target address, if not, continue fetching continually (PC + 4)
- (BTB hit is used as control signal in mux deciding between target address and PC +4)

Decode stage:
- Perform branch prediction - gives taken/not-taken
- Perform address calculation - gives the actual branch target
- If the branch is taken, and the predicted target address from the fetch stage is wrong - use the calculated address (causes stall for a cycle)

If BTB/RAS address != calculated address - causes stall and will need to insert a bubble

Question 30

What is speculative branch execution?

Answer 30

Predict target address and start fetching and executing along this path.

There might be multiple branches in flight during this.

To keep track of each branch, a tag is added to each speculatively taken execution path

Question 31

What happens when a branch evaluates to correctly predicted

Answer 31

Tags are deallocated
Instructions are set as non-speculative

Question 32

What happens when a branch evaluates to mispredicted

Answer 32

Instructions along the wrong path are nullified.
Start fetching along the correct path.