Computer Organisation Chapter 6

Speculative Execution

• Speculative execution is required when unrolling loops with conditional branch instructions that have a RAW dependence on the loop iteration.
• It requires more hardware, such as reservation stations and functional units, as well as more complex control and dependencies detection.
• Additional memory is needed to guarantee an eventual correction in case of a prediction error.
• The architecture needs more efficient branch prediction to pay off the new hardware cost with performance.

Control Dependencies

• As the number of executed instructions per clock cycle increases, the potential instructions flow also increases, reducing CPI.
• Delays caused by branches can seriously impact performance.
• A "simple" strategy to minimize this problem is to not stop or reduce speed in branches.

Dynamic Branch Prediction

• Dynamic branch prediction considers the fact that branch instructions can be executed many times during program execution, e.g., inside loops.
• This approach is different from static branch prediction strategies, such as predicted-not-taken and predicted-taken.
• The predicted-not-taken approach may be inefficient in loops, leading to many mispredictions.

Branch-Prediction Buffers

• A possible solution to the problem is to use branch-prediction buffers, which relate one bit to each branch decision.
• The buffer is a small memory indexed by the lower portion of the branch instruction address.
• The memory contains a bit that indicates whether a branch was recently taken or untaken.
• This approach is a hint assumed to be correct, and the next instruction fetch begins in the predicted direction.
• If the hint is wrong, the prediction bit is inverted and stored back.

1-Bit Prediction

• The 1-bit prediction scheme is a simple dynamic branch-prediction scheme.
• It is a 2-state finite-state machine (FSM) with states: TAKEN and UNTAKEN.
• The scheme uses just the low-order address bits to have variations, i.e., different addresses considering the use of just the low-order bits.
• However, there may be an inconvenient or even problematic case regarding these low-order address bits, where two distinct branch instructions end up with the same index.
• The 1-bit prediction scheme has the shortcoming that it may mispredict twice, rather than once, when a branch is not taken in a loop.

Speculative Execution

• Speculative execution is required when unrolling loops with conditional branch instructions that have a RAW dependence on the loop iteration.
• It requires more hardware, such as reservation stations and functional units, as well as more complex control and dependencies detection.
• Additional memory is needed to guarantee an eventual correction in case of a prediction error.
• The architecture needs more efficient branch prediction to pay off the new hardware cost with performance.

Control Dependencies

• As the number of executed instructions per clock cycle increases, the potential instructions flow also increases, reducing CPI.
• Delays caused by branches can seriously impact performance.
• A "simple" strategy to minimize this problem is to not stop or reduce speed in branches.

Dynamic Branch Prediction

• Dynamic branch prediction considers the fact that branch instructions can be executed many times during program execution, e.g., inside loops.
• This approach is different from static branch prediction strategies, such as predicted-not-taken and predicted-taken.
• The predicted-not-taken approach may be inefficient in loops, leading to many mispredictions.

Branch-Prediction Buffers

• A possible solution to the problem is to use branch-prediction buffers, which relate one bit to each branch decision.
• The buffer is a small memory indexed by the lower portion of the branch instruction address.
• The memory contains a bit that indicates whether a branch was recently taken or untaken.
• This approach is a hint assumed to be correct, and the next instruction fetch begins in the predicted direction.
• If the hint is wrong, the prediction bit is inverted and stored back.

1-Bit Prediction

• The 1-bit prediction scheme is a simple dynamic branch-prediction scheme.
• It is a 2-state finite-state machine (FSM) with states: TAKEN and UNTAKEN.
• The scheme uses just the low-order address bits to have variations, i.e., different addresses considering the use of just the low-order bits.
• However, there may be an inconvenient or even problematic case regarding these low-order address bits, where two distinct branch instructions end up with the same index.
• The 1-bit prediction scheme has the shortcoming that it may mispredict twice, rather than once, when a branch is not taken in a loop.

This quiz covers branch prediction and speculative superscalar processors in computer organisation, focusing on loop unrolling and speculative execution.