Explain branch prediction logic.
pipelining • 10k  views
  1. Performance gain through pipelining can be reduced by the presence of program transfer instructions (such as JMP, CALL, RET and conditional jumps).
  2. They change the sequence causing all the instructions that entered the pipeline after program transfer instruction invalid.
  3. Suppose instruction I3 is a conditional jump to I50 at some other address (target address), then the instructions that entered after I3 is invalid and new sequence beginning with I50 need to be loaded in.
  4. This causes bubbles in pipeline, where no work is done as the pipeline stages are reloaded.
  5. To avoid this problem, the Pentium uses a scheme called Dynamic Branch Prediction.
  6. In this scheme, a prediction is made concerning the branch instruction currently in pipeline.
  7. Prediction will be either taken or not taken.
  8. If the prediction turns out to be true, the pipeline will not be flushed and no clock cycles will be lost. If the prediction turns out to be false, the pipeline is flushed and started over with the correct instruction.
  9. It results in a 3 cycle penalty if the branch is executed in the u-pipeline and 4 cycle penalty in v-pipeline.
  10. It is implemented using a 4-way set associative cache with 256 entries. This is referred to as the Branch Target Buffer (BTB).
  11. The directory entry for each line contains the following information:
  12. Valid Bit : Indicates whether or not the entry is in use.
  13. History Bits: track how often the branch has been taken.
  14. Source memory address that the branch instruction was fetched from (address of I3).
  15. If its directory entry is valid, the target address of the branch is stored in corresponding data entry in BTB.
Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more