The need for increased prediction accuracy of branch instructions is well-known if the art of processor design. The need has grown even greater with the increase of processor pipeline lengths, cache memory latencies, and superscalar instruction issue widths. Branch instruction prediction involves predicting the target address and, in the case of a conditional branch instruction, the direction, i.e., taken or not taken.
One popular conditional branch instruction direction predictor is commonly referred to as a TAGE predictor, which is an acronym for TAgged GEometric length predictor, which has been described in various papers authored by Andre Seznec. The TAGE predictor include multiple memory banks used to store branch prediction information. Each bank of the predictor is indexed with a hash of the program counter and a length of the branch history pattern except one default bank that is indexed by only the program counter. To generate the index for each of the non-default banks, a different length of the branch history pattern is hashed; hence Geometric length. Additionally, each entry in each bank includes a tag that is compared with tag bits of the program counter to determine whether a hit occurred in the bank; hence TAgged.
As the papers describe, the TAGE predictors designed by Seznec have been entered in various branch prediction contests with significant success. The contests are based on software simulation of the branch predictors. The TAGE papers describe various ways the banks are updated in a probabilistic fashion.