Jordan University of Science and Technology

A Shadow Dynamic Finite State Machine for Branch Prediction: An Alternative for the 2-bit Saturating Counter.

Authors:  Abdel-Hafeez, Saleh; Albosul, Asem; Shatnawi, Ahmad; Gordon-Ross, Ann; Harb, Shadi

We propose an adaptive learning machine-based branch predictor -- the shadow dynamic finite state machine (SDFSM) -- that enables more accurate branch predictions by learning unique branching patterns through a self-modifying technique. SDFSM states represent branch pattern bits. If a state mispredicts a branch, the state is swapped with its shadow state, which represents the correct branching pattern bit. Therefore, the prediction accuracy can reach 100% if the number of states matches a branch's pattern length. When compared to a 2-bit saturating counter using bimodal branch predictors, the SDFSM decreases average misprediction rates by 18.3%, with individual decreases as high as 55%.