Branch Prediction Techniques and Their Accuracy Quiz Quiz

Explore essential concepts of branch prediction techniques and their accuracy in modern processors with this quiz. Understand static and dynamic predictors, accuracy factors, and real-world examples to solidify your grasp of computer architecture fundamentals.

1. Definition of Branch Prediction

   Which of the following best describes the main purpose of branch prediction in computer processors?

   1. To guess the outcome of conditional branches to improve instruction pipeline efficiency
   2. To reduce the size of compiled programs in memory
   3. To select the fastest register for computations
   4. To control power consumption during idle states

   Explanation: Branch prediction helps processors guess upcoming branch outcomes to keep the instruction pipeline full and efficient, especially in conditional statements. Reducing program size and controlling power consumption are unrelated to branch prediction. Selecting registers pertains to instruction scheduling, not branch prediction.

2. Static vs. Dynamic Prediction

   What is a key difference between static and dynamic branch prediction techniques?

   1. Static prediction uses fixed rules, while dynamic prediction adapts based on runtime behavior
   2. Static prediction requires more hardware than dynamic prediction
   3. Static prediction updates after each program execution, while dynamic remains constant
   4. Static prediction is always faster than dynamic prediction

   Explanation: Static prediction applies set rules, like always predicting branches as taken or not taken, regardless of actual runtime data. Dynamic prediction uses past execution history to adapt its predictions. Whether they are faster or use more hardware depends on the design; dynamic predictors may need more hardware, not static.

3. Example Scenario – Always-Taken Predictor

   An always-taken static branch predictor assumes that every branch will be taken. In a simple loop such as 'for (i = 0; i u003C 10; i++)', how accurately will this predictor behave?

   1. It will never predict correctly
   2. It will be correct most of the time except the last loop iteration
   3. It will be correct only on the first iteration
   4. It will predict all iterations incorrectly

   Explanation: The always-taken predictor will be accurate for all iterations except when the loop finishes and the branch should not be taken. It does not fail every time or only predict one iteration correctly. Thus, most predictions are correct except the last branch evaluation.

4. Two-Bit Saturating Counter Predictor

   What is the main advantage of using a two-bit saturating counter in dynamic branch prediction?

   1. It doubles the speed of instruction execution
   2. It increases branch target buffer size
   3. It removes the need for instruction fetch units
   4. It reduces the chance of misprediction caused by occasional fluctuations in branch behavior

   Explanation: A two-bit counter requires two wrong predictions to switch its direction, filtering out mispredictions due to rare changes. It does not affect execution speed or branch target buffer size directly, nor does it replace fetch units.

5. Branch History Table Purpose

   What is the primary function of a Branch History Table (BHT) in dynamic branch prediction?

   1. To store variable names and function arguments
   2. To keep track of data cache locations
   3. To monitor power usage in the processor
   4. To store the recent outcomes of branches to inform future predictions

   Explanation: A BHT records the history of branch results, enabling more accurate future branch predictions. It is not meant for variable storage, power monitoring, or data cache indexing; those are unrelated to its predictive purpose.

6. Accuracy of Predictors for Simple Patterns

   Which branch prediction method is most accurate for highly predictable, repetitive branch patterns such as simple 'if' conditions always evaluating true?

   1. Static predictor (always-taken or always-not-taken)
   2. Alternating predictor
   3. No prediction (always stall pipeline)
   4. Random guess predictor

   Explanation: For branches that consistently behave the same way, a static predictor set to match the observed behavior gives optimal accuracy. Random guessing and alternating predictors would mispredict frequently, while never predicting and always stalling wastes resources.

7. Bimodal vs. Correlating Predictors

   How does a correlating (or two-level) branch predictor improve over a basic bimodal predictor?

   1. By incorporating the behavior of multiple recent branches, not just the same branch's history
   2. By always selecting not-taken for every branch
   3. By only using static prediction decisions
   4. By removing the need for a branch history table entirely

   Explanation: Correlating predictors factor in the outcomes of several recent branches to make more informed predictions, unlike bimodal predictors which focus on the local history of one branch. They do not eliminate the BHT, strictly use static decisions, or always predict not-taken.

8. Branch Target Buffer (BTB) Role

   What is the main role of the Branch Target Buffer (BTB) in branch prediction systems?

   1. To count the total number of branches in a program
   2. To increase code compilation speed
   3. To store the destination addresses for predicted taken branches
   4. To maintain a list of executed data instructions

   Explanation: A BTB supplies the next instruction address for predicted-taken branches, facilitating quick jumps during execution. It does not affect compilation speed, track data instructions, or count all program branches.

9. Accuracy Influencing Factors

   Which factor most directly increases the accuracy of dynamic branch predictors?

   1. Decreasing clock cycle speed
   2. High correlation and repetition in branch outcomes
   3. Reducing the size of main memory
   4. Using random guess logic

   Explanation: When branches follow consistent patterns, dynamic predictors can learn and predict more accurately. Random guesses reduce accuracy, and main memory size or clock speed do not directly affect branch prediction performance.

10. Performance Impact of Mis-prediction

    What is a likely consequence if a branch predictor frequently mispredicts branches in a pipelined processor?

    1. The instruction set architecture will automatically change
    2. The power supply will be interrupted
    3. The processor pipeline might stall or flush, causing decreased performance
    4. The processor’s physical size will increase

    Explanation: Frequent mispredictions disrupt the instruction flow, requiring pipeline stalls or flushes, which hurt overall performance. They do not alter processor size, power supply, or change the instruction set architecture automatically.