Branch Prediction

Question 1

What is Not Taken prediction?

Answer 1

Always predict that the branch is not taken - every processor uses at lease this since it is an easy performance gain

Question 2

What is the BTB?

Answer 2

Branch Target Buffer - keeps track of where we went to last time we took this branch. Update this table after we’ve determined if we’ve taken the branch or not. Can be used as a predictor or in coordination with one.

Question 3

What is the structure of the BTB?

Answer 3

Want to keep it small, so maintaining an entry for each instruction is unrealistic. Use least significant bits to index into BTB

Question 4

What is a 1-bit predictor?

Answer 4

Has a branch history table that keeps track of whether we took this branch last time or not. If taken, has BTB to check where we are going.

Question 5

What is a 1-bit predictor good and bad for?

Answer 5

Good for when we always (or almost always) are T or NT. Terrible at random N/NT

Question 6

What is a 2-bit predictor (2BP, 2BC)?

Answer 6

Have a prediction bit and hysteresis (conviction bit). Improvement from 1-bit predictor. Initialization state doesn’t matter much

Question 7

3+ Bit Predictors

Answer 7

More costly than 2BP, and only improve things when ‘anomalous’ decisions come in streaks. Usually better to stay with 2BP

Question 8

What aspect of bit-predictors do history predictors aim to improve upon?

Answer 8

Having a higher performance on pattern based behavior

Question 9

What is a 1-Bit History Predictor?

Answer 9

BHT has 1 bit for the history and 2-2BC. If the history is 0, we look at the first BC, if it’s one, we look at the second. When updating, we update the BC for the history, then change the history to what we observed

Question 10

What is a 2-Bit History Predictor?

Answer 10

BHT has 2 bits for the history and 4-2BC.

Question 11

What is an N-Bit History Predictor? What will is predict correctly? What is the cost?

Answer 11

N Bits of history, 2^N-2BC. Will correctly predict all patterns with length <= N+1. Most counters are not used. Cost is (N+2*2^N) bits for each address

Question 12

What is a PShared predictor?

Answer 12

History with Shared Counters Predictor. P == private history, shared == shared counters. Aims to solve the waste of the n-bit predictor

Question 13

How is a PShared predictor structured?

Answer 13

1. Pattern history table (PHT) - contains just the history bits for each address
2. Use PC to index into PHT, XOR address offset with PHT history -> index into BHT (single 2BP)

Question 14

What are the pros/cons for a PShared predictor?

Answer 14

(+) Allows for many bits in the history table without a counter for each one
(-) possible collisions in BHT
Good for patterns and 8-iteration loop

Question 15

What is a GShared Predictor?

Answer 15

A predictor with global history and shared predictors. Use a single history to predict all branches (XOR PC with global history)

Question 16

What is a GShared predictor good for?

Answer 16

Correlated branches (when one branch depends on the outcome of another)

Question 17

What is a tournament predictor?

Answer 17

Contains two good predictors and a 2BC (meta-predictor). 2BC keeps track of which prediction we should use. Outcome is updated for each predictor, and meta is updated based on which one was right (no change if both were right/wrong)

Question 18

What is a hierarchical predictor?

Answer 18

Contains a good and okay predictors. Update okay predictor for every branch, update good predictor only when the okay one does poorly (don’t want to use the good one if you don’t have to). Better than tournament predictor

Question 19

What is a RAS Predictor?

Answer 19

Return Address Stack. Has a small stack (Return Address Table, “RAT”). When a function is called, its return address is pushed onto the stack. If it becomes full, wrap around to the beginning.

Question 20

How do we know if an instruction is a return instruction (and therefore we should use the RAS predictor)?

Answer 20

1. can use a simple predictor
2. Can use precoding - when processor fetches instruction from memory, it stores it in the cache as well as whether or not it’s a RET