I have a question about the common course "Computer Architecture".
How is it possible to have a LOCAL Branch Predecitor with 1024 entries, 3 bits for HISTORY but without a TAG.
As I understand,in that way i will get a Global branch predictor because i dont have a way to map a branch to an entry. Am I right? If not,How can it be possible?
The 1024 entries would be indexed by bits from the instruction address, so the history is likely to be for the same branch (especially since there is temporal locality in instruction execution, so the same branch is more likely to be executed nearby in time than some other branch that happens to have the same index in the branch predictor). Without complete tags, there is the possibility of aliasing (where the history at a given index is actually from a different branch than the instruction address being looked up), but since only a prediction is provided even destructive aliasing would only cause a misprediction. With 32-bit addresses and fixed-length 4-byte instructions, 1024 entries would use 20 bits per entry for complete tags, requiring over six times as much storage as an untagged table with 3 bits of history per entry.
(Aliasing can reduce prediction accuracy enough that techniques like agree predictors have been developed to reduce destructive aliasing. In an agree predictor a second source of prediction information [usually static for a per-address predictor, often a dynamic per-address table for a global history based predictor since adding the per-address table also allows tournament prediction] provides a bias for the other predictor; instead of predicting taken or not-taken, the other predictor predicts agree or disagree. Bi-Mode prediction is similar, but uses two tables with table selection based on the branch bias.)
For a local history predictor there can also be aliasing in the table translating the local history into a prediction. If only one table is used one branch's behavior could interfere with predictions for another branch. (This is not a terrible design; the Alpha 21264 used a 1024-entry local history predictor with 10 bits of history and a single shared 1024 entry [indexed by the 10 history bits] predictor with 3 bit saturating counters, along with a global predictor and chooser.)
Using tags (even partial tags) allows the use of associativity and the percentage storage overhead is less if the branch target buffer is merged with the local predictor. (A unified direction predictor and branch target buffer would generally have fewer direction entries than separate predictors and BTB entries for unconditional control flow operations do not need direction prediction.) However, direct-mapped structures are faster (and using tags increases energy use), so there are tradeoffs.
(Similar tagging tradeoffs exist for bimodal [distinct from Bi-Mode] predictors, where a single table indexed by a hash of the branch address provides the prediction, typically using either a two bit saturating counter or a prediction bit and a hysteresis bit.)
