Partial Resolution in Branch Target Buffers

Barry Fagin, Kathryn Russell


Branch target buffers, or BTB's, are small caches for recently accessed program branching information. Like data caches, the set of intercepted addresses is divided into equivalence classes based on the low order bits of an address. Unlike data caches, however, complete resolution of a single address from within an equivalence class is not required for correct program execution. Substantial savings are therefore possible by employing *partial resolution*, using fewer tag bits than necessary to uniquely identify an address.

We present our analysis of the relationship between the number of tag bits in a branch target buffer and prediction accuracy, based on dynamic simulations of the SPECINT92 benchmark suite. For a 512 entry BTB, our results indicate that, on average, only 2 tag bits are necessary to obtain 99.9% of the accuracy obtainable with a full tag. This suggests that existing and future microprocessors can achieve substantial area savings in their BTB tag stores by employing partial resolution.


branch target buffer, branch prediction, trace driven simulation

Talk Overheads (182757 bytes)