cvut / qtrvsim

RISC-V CPU simulator for education purposes
GNU General Public License v3.0
466 stars 56 forks source link

Branch predictor enhancements,corrections and coexistence with pipelined execution #143

Open ppisa opened 2 months ago

ppisa commented 2 months ago

The pull request https://github.com/cvut/qtrvsim/pull/135 is initial step to provide branch prediction visualization for teaching but there are more issues to solve when pipelined execution is considered.

  1. the BHT update is late for the short loops (body less than three instructions plus branch one) - this is probably hard to solve and can be used to demonstrate interaction of BHT and pipeline and their consequences
  2. the BHT cannot correctly predict the first pass through branch and jump instructions for other initial condition cas then BNT/BSNT/BWNT, because it is not known that instruction is branch before decode - it is solved on real processor by classification branch instructions during fetch into cache and addition of flags to cache - we do not want this for initial educational case because it is complexity much above branch introduction in textbooks.
  3. BHR is delayed if the single one is used and for tightly placed branches it would seriously misbehave
  4. even for single cycle the branch which is never taken is not considered in previous prediction, it should be discussed and resolved
  5. it should be considered that a BHT entry is not allocated for unconditional/jump branches and these branches should be marked in BTB as unconditional type and should not consult BHT during PC computation
  6. even for instructions which are not of branch/jump type the predictor update should be called probably because stalled BHT and or BTB entries for self-modifying code would cause significant misbehave where branch is replaced by non branch instruction.

Input and discussion from community, BHT/BTB visualization author (@jiristefan) and reviewer @jdupak are strongly appreciated.