Out of Order Pipelines (Control)

Question 1

What 3 factors do speculative execution consist of?

Answer 1

1. Target prediction
2. Condition prediction (i.e. taken or not taken)
3. Validation and recovery

Question 2

What does a Branch Target Buffer do?

Answer 2

Stores the target addresses of previously taken branches/jumps

Question 3

How does a branch target buffer work?

Answer 3

1. An entry is added to the BTB when a branch/jump is first taken
2. For subsequent branches/jumps, the entry is used early in the pipeline to fetch the predicted path
3. Branch/jump is resolved in the EXECUTE stage to verify target and update entry

Question 4

What is the drawback of target prediction using a branch target buffer?

Answer 4

Indirect jumps - the same jump instruction can have multiple targets which leads to mispredictions

Question 5

Explain the Return Address Stack (RAS).

Answer 5

The RAS is used to store return addresses from jalr instructions, which are in itself used in function calls. When we reach a function call, push the return address on the stack. If we have a function return, pop the return address from the stack

Question 6

Describe a drawback of the RAS

Answer 6

Mispredicted calls or returns could potentially corrupt the RAS

Question 7

How do we integrate RAS with checkpointing?

Answer 7

The RAS top-of-stack-pointer and top-of-stack-content can be added to the branch checkpoint structure

Question 8

What is a target cache (TC) with reference to target prediction?

Answer 8

A target cache (TC) is a separate branch target buffer used for indirect jumps. It remembers multiple targets per jr instruction.

Question 9

How does a target cache (with reference to target prediction) work?

Answer 9

The target cache remembers multiple targets per jr instruction. It uses the branch target history to distinguish between likely targets. A Target History Register (THR) shifts in the low-order bits of the last n jump targets. The THR contents is then XOR’d with the PC. The lower bits of the result of the XOR is used to index the TC with the upper bits acting as the tag

Question 10

List 2 static methods for condition prediction.

Answer 10

1. Predict taken if pc-relative offset is negative (since it might be the bottom of a loop); predict not-taken otherwise
2. Compiler inserts hint into instruction (maybe in the form of a bit)

Question 11

What binary values represent strongly not taken, weakly not taken, weakly taken and strongly taken in the pattern history table?

Answer 11

00, 01, 10, 11

Question 12

If I have a pattern history as follows:
1110 1110 1110…
where 1 indicates taken and 0 indicates not-taken, what will be the 2-bit value stored in the
a. 7th index
b. 11th index
c. 14th index
Assume it has already “warmed up” (run enough times to stabilize and not change)

Answer 12

a. 00
b. 11
c. 11
Explanation: 7 = 4’b0111. We have a 0 after the 3 1’s so we predict SNT = 00

Question 13

List 2 drawbacks of local predictors.
(Hint: Local predictors store the result of the last n iterations of a branch condition)

Answer 13

1. Aliasing can occur based on low-order PC bits
2. Aliasing can occur based on same history patterns

Question 14

What are global branch predictors and how do they differ from local predictors?

Answer 14

Global predictors detect correlated branch behavior (behavior influenced by other branch decisions). They save the last n branch decisions (of any branch instr) which differs from local predictors since those are PC specific

Question 15

What is the “history table” equivalent in a global branch predictor?

Answer 15

Global history register

Question 16

What is gShare?

Answer 16

A prediction concept that XOR’s the global history register value (GR) and the PC to index the pattern history table

Question 17

In a perception predictor, state the equation that dictates the prediction (y) and takes into account weights of the inputs.

Answer 17

y = w_0 + sum(x_i * w_i)
where x_i is the history bit i from GR

Question 18

What is the purpose of w_0 in the perception prediction equation?

Answer 18

Used for strongly biased branches that are not correlated to the prior branches