The following trace represents the actual outcome of a single branch instruction

Question

The following trace represents the actual outcome of a single branch instruction for a certain program. (a) Fill in the table showing updated predictions and hits/misses for a 1 bit and 2 bit non-correlating predictors. The default predictions are given below. (b) The following trace was generated for a program in which you want to evaluate a (1, 1) branch prediction scheme. The program loops such that the branches are executed in order and continue repeating (i.e., br1 rightarrow br2 rightarrow br3 rightarrow b1 rightarrow br2..). The default prediction value NT/NT for the first branch implies a prior branch was not taken. Fill in the Table below.

Explanation / Answer

Memory indexed by the lower bits of the address of a branch
instruction during the fetch stage
• contains a prediction
(which path the last branch to index to this BPB location took)
• do what the prediction says to do
• if the prediction is taken & it is correct
• only incur a one-cycle penalty why?
• if the prediction is not taken & it is correct
• incur no penalty why?
• if the prediction is incorrect
• change the prediction
• also flush the pipeline why?
• penalty is the same as if there were no branch prediction why?
A single prediction bit does not work well with loops
• mispredicts the first & last iterations of a nested loop
Conditional branches still comprise about 20% of instructions
Correct predictions are more important today why?
• pipelines deeper
branch not resolved until more cycles from fetching
therefore the misprediction penalty greater
• cycle times smaller: more emphasis on throughput
(performance)
• more functionality between fetch & execute
• multiple instruction issue (superscalars & VLIW)
branch occurs almost every cycle
• flushing & refetching more instructions
• object-oriented programming
more indirect branches which harder to predict
• dual of Amdahl’s Law
other forms of pipeline stalling are being addressed so the portion
of CPI due to branch delays is relatively larger
All this means that the potential stalling due to branches is greater

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.