Pipeline Hazards and Branch Prediction

Question 1

DEFINE: Pipeline Hazard.

Answer 1

A consideration that we need to take into account with pipelining, preventing data or processing mismatches.

Question 2

There are four read/write hazards to consider. In-order processors only need to deal with which one?

Answer 2

Read-after-Write hazards.

Question 3

DEFINE: Read-after-write (RaW) hazards.

Answer 3

When data is accessed after a change is made to the register but before that change is applied in the Writeback step.

Question 4

TRUE/FALSE: Stalling is the only major way to resolve read-after-write hazards.

Answer 4

FALSE. You can also use Forwarding/Bypassing.

Question 5

DEFINE: Stalling.

Answer 5

Waiting for the previous cycle to complete before continuing, usually because of dependencies. Creates pipeline bubbles.

Question 6

In an in-order processor that implements Stalling to resolve read-after-write hazards, how are potential hazards detected?

Answer 6

In the Decode stage, source registers in the upcoming instructions are checked against destination registers further in the pipeline. If a dependency is detected, the new instruction is stalled.

Question 7

DEFINE: Forwarding/Bypassing.

Answer 7

Intercepting the new value of a destination register after the Execute stage to immediately pull back to the Register file, so as to prevent read-after-write stalling.

Question 8

If forwarding adds to the Decode stage’s critical path, why is it often implemented anyway?

Answer 8

Performance benchmarking.

Question 9

What’s the tradeoff for adding forwarding/bypassing paths back to the register file?

Answer 9

More multiplexers, and in turn more chip space.

Question 10

DEFINE: Load-Use Data Hazard.

Answer 10

When a value being loaded from memory into a register is used before the Writeback stage is completed.

Question 11

TRUE/FALSE: An in-order processor’s only solution to a Load-Use Data Hazard is through stalling until the value is written back.

Answer 11

TRUE. The compiler or software developer can often change their code to avoid this, however.

Question 12

What hazards are contained in the following list of instructions? These are ran in-order, with all registers initially filled with valid values:

1. ADD s0, s1, s2
2. SUB s3, s0, s4
3. LW s5, 0(s3)
4. ADD s6, s5, s7
5. ADD s8, s6, s9

Answer 12

There are 3 read-after-write hazards and 1 load-use hazard:
- Instruction 2 tries to read s0 immediately after it’s written (but not yet written back). RaW.
- Instruction 3 uses s3’s value before it’s written back to load a memory address. RaW.
- Instruction 4 uses s5’s value before the memory has loaded it and written back. LU
- Instruction 5 uses s6’s values before Writeback. RaW.

Question 13

DEFINE: Control Hazard.

Answer 13

Conditional branching sending us down a set of instructions, but potentially the wrong one thanks to the conditions.

Question 14

What’s the main way we deal with Control Hazards?

Answer 14

Branch Prediction

Question 15

TRUE/FALSE: The best way to handle branch prediction is to stall.

Answer 15

FALSE, as shown through benchmarking.

Question 16

TRUE/FALSE: When a branch mis-prediction happens, we simply need to cancel all currently pipelined instructions associated with that branch.

Answer 16

FALSE, we also need to undo any work done by those future instructions.

Question 17

How could we use “epochs” to handle branch mispredictions?

Answer 17

We assign each instruction an incrementing epoch, then when a mis-predict occurs, ignore any greater than that mis-predict.

Question 18

If branch mis-predictions are rare, why do we still care about them?

Answer 18

The miss penalty is disproportionately large.

Question 19

DEFINE: Static branch prediction.

Answer 19

Branch prediction based only on the current situation. An example is a not-taken policy, where the assumption will always be that the branch is not taken, or BTFNT (Backwards-Taken, Forward Not Taken), where backwards branches (such as in loops) are taken and forward branches aren’t.

Question 20

DEFINE: Dynamic branch prediction.

Answer 20

Branch prediction based on the history of that instruction.

Question 21

After which pipeline stage does a mis-prediction cause a bubble?

Answer 21

The Execute stage.

Question 22

When considering branch prediction, what 2 questions must we answer?

Answer 22

1) Will this instruction cause a branch?
2) Where will that branch lead?

Question 23

What entity is commonly used to decide whether a branch was taken?

Answer 23

The Branch History Table (BHT).

Question 24

What entity is commonly used to decide where a branch leads to?

Answer 24

The Branch Target Buffer (BTB).

Question 25

What is missing in the blanks for the following pseudocode, describing the base Branch Predictor logic. 1) Word next_pc = pc + 4 2) Bit[10] lsb = truncate(pc) 3) if (___[lsb]): 4) next_pc = ___(lsb) 5) return next_pc

Answer 25

1. bht or Branch History Table 2. btb or Branch Target Buffer

Question 26

TRUE/FALSE: The optimal branch predictor without time travel can't ever be perfect, but can be very accurate.

Answer 26

TRUE.

Question 27

I run the following function in C: const char* getCountry(int cc) { if (cc == 0) return "A0"; if (cc == 1) return "A1"; if (cc == 2) return "A2"; ... if (cc == 256) return "A256" } It's running very slowly, but when I remove the first line, it improves dramatically. Why might that be?

Answer 27

The branch prediction tables (entities) likely can't store more than 256 instructions. As such, mispredictions are very common.

Question 28

Describe a 1-bit predictor.

Answer 28

A branch predictor that only stores the latest result from an instruction. For example, if that instruction branched last time, it predicts it will branch this time as well, with no further complexity.

Question 29

Describe a programming concept that works very well with 1-bit predictors.

Answer 29

Loops. They are very likely to loop back.

Question 30

Describe a 2-bit predictor.

Answer 30

A branch predictor that stores two bits and therefore four possible values for prediction, with every result ticking that value up or down by 1.

Question 31

What concept can we use to avoid branch prediction altogether?

Answer 31

Branchless programming.

Question 32

DEFINE: Loop Unrolling.

Answer 32

For static loops (for i = 0 to 15 do this), simply writing each line of i to avoid loop checking in branch prediction.

Question 33

What two coding situations will prevent loop unrolling from making significant improvements?

Answer 33

Dynamic loops (for i = 0 to n-1 do this) and complex logic in the logic within the loop.