Pierre Michaud
email: pierre.michaud@inria.fr

An Alternative TAGE-like Conditional Branch Predictor

TAGE is one of the most accurate conditional branch predictors known today. However, TAGE does not exploit its input information perfectly, as it is possible to obtain significant prediction accuracy improvements by complementing TAGE with a statistical corrector using the same input information. This paper proposes an alternative TAGE-like predictor making statistical correction practically superfluous.

Introduction

The branch predictor is the keystone of modern superscalar microarchitectures. Reducing the number of branch mispredictions is a relatively simple way to increase performance and simultaneously decrease energy consumption.

Research in branch prediction has been a decades-long effort, largely focused on predicting the direction of conditional branches, as this is generally the greatest source of mispredictions. Since 2006, research in branch prediction has progressed only slowly. A plausible reason is that modern branch predictors might be close to a prediction accuracy limit. However, this is not certain either, as the only mathematically proven limit is zero misprediction, which is still far from being attained.

Today, a highly accurate conditional branch predictor based on the published state of the art is either TAGE-like [START_REF] Seznec | A case for (partially) tagged geometric history length branch prediction[END_REF], perceptron-based [START_REF] Jiménez | Dynamic branch prediction with perceptrons[END_REF][START_REF] Jiménez | Multiperspective perceptron predictor[END_REF], or a combination of those [START_REF] Seznec | TAGE-SC-L branch predictors again[END_REF][START_REF] Jiménez | Multiperspective perceptron predictor with TAGE[END_REF]. Both types of predictors have distinct advantages: TAGE exploits the limited predictor storage very efficiently, whereas perceptronbased predictors can easily combine different sorts of input information.

This paper focuses on TAGE-like predictors. Except for the first branch prediction championship, which was held in 2004 before TAGE was introduced [START_REF]Championship branch prediction (CBP-1)[END_REF], all four subsequent championships were won by predictors based on TAGE [START_REF]Championship branch prediction (CBP-2)[END_REF][START_REF]Championship branch prediction (CBP-3)[END_REF][START_REF]Championship branch prediction (CBP-4)[END_REF][START_REF]Championship branch prediction (CBP-5)[END_REF]. It is not known with certainty which commercial processors implement a TAGE-like predictor, as this information is rarely disclosed. Admittedly, a PPM-like predictor is implemented in the IBM zEC12 [START_REF] Bonnano | Two level bulk preload branch prediction[END_REF] and a TAGE predictor is implemented in the Phytium Mars [START_REF] Zhang | Mars: a 64-core ARMv8 processor[END_REF] and in the IBM POWER9 [START_REF]POWER9 processor user's manual[END_REF].

Although TAGE is a very accurate predictor, it does not exploit its input information perfectly, as significant prediction accuracy improvements are obtained by complementing TAGE with a statistical corrector using the same input information [START_REF] Seznec | A new case for the TAGE branch predictor[END_REF]. The statistical corrector, even small, makes the whole predictor more complex. More importantly perhaps, this imperfection of TAGE revealed by the statistical corrector is a hint that our understanding of TAGE-like predictors is incomplete. This paper proposes an alternative TAGE-like predictor, called BATAGE, making statistical correction practically superfluous. BATAGE has the same global structure as TAGE but uses a different tagged-entry format and different prediction and update algorithms.

Section 2 provides the historical and technical context for situating the contributions of BATAGE. Section 3 analyzes the cold-counter problem, which is the main cause for TAGE needing statistical correction. Section 4 proposes to replace the conventional up/down counter in TAGE with two counters counting separately the taken and not-taken occurrences. A new method is proposed for estimating prediction confidence using Bayesian probabilities. Section 5 describes the BATAGE predictor and its features, including

• a new prediction automaton called dual-counter,

• prediction and update algorithms exploiting the dual-counter and Bayesian confidence estimation,

• a new method called Controlled Allocation Throttling (CAT) for reducing the allocation frequency.

Finally, Section 6 provides an experimental evaluation of BATAGE.

A short history of conditional branch prediction

BATAGE is derived from TAGE, which is the result of decades of research in branch prediction. This section provides a short history of conditional branch prediction. Its purpose is to furnish the historical and technical context for situating the contributions of BATAGE.

Figure 1 illustrates the improvements in prediction accuracy over the years. It shows the average MPKI (mispredictions per 1000 instructions) over the CBP 2016 traces for various branch predictors since 1993. Appendix A provides a detailed legend of Figure 1.

The eighties

The bimodal predictor, that is, a table of up/down saturating counters accessed with a hash of the branch address, was introduced by James E. Smith in the early eighties [START_REF] Smith | A study of branch prediction strategies[END_REF]. 1In 1984, Johnny Lee and Alan Jay Smith proposed a branch prediction method consisting of branch history bit vectors stored in the Branch Target Buffer (BTB) entries and used for accessing a prediction table trained offline with representative workloads [START_REF] Lee | Branch prediction strategies and branch target buffer design[END_REF]. They were focusing on understanding the prediction accuracy limits of this method. They did not describe a hardware implementation. Although Lee and Smith mentioned in passing the possibility of having a global branch history (using today's terminology), their study focused on per-branch history bit vectors.

Two-level prediction

In a seminal paper published in 1991, Yeh and Patt proposed a branch predictor derived from Lee and Smith's method but using online instead of offline training [START_REF] Yeh | Two-level adaptive training branch prediction[END_REF]. They introduced the Pattern History Table (PHT), a prediction table holding 2-bit up/down counters and accessed with the history bit vector of the branch being predicted. They called this predictor Two-Level Adaptive. In the 1991 paper, Yeh and Patt considered only per-branch (aka local) history bit vectors. The first papers describing a global-history predictor were published in 1992 by Yeh and Patt [START_REF] Yeh | Alternative implementations of two-level adaptive branch prediction[END_REF] and by Pan, So and Rameh [START_REF] Pan | Improving the accuracy of dynamic branch prediction using branch correlation[END_REF]. In a global-history predictor, there is a global history register shared by all the branches. Yeh and Patt generalized the label "Two Level", including global-history predictors as a special case [START_REF] Yeh | Alternative implementations of two-level adaptive branch prediction[END_REF][START_REF] Yeh | A comparison of dynamic branch predictors that use two levels of branch history[END_REF]. This first wave of two-level schemes culminated with the gshare global-history predictor introduced by McFarling [START_REF] Mcfarling | Combining branch predictors[END_REF]. For several years, gshare was the reference conditional branch predictor for its simplicity and high prediction accuracy. 2

Meta-prediction and de-aliasing techniques

In 1993, McFarling introduced meta-prediction, a method for combining several different prediction methods, leading to hybrid predictors more accurate than gshare [START_REF] Mcfarling | Combining branch predictors[END_REF]. As Figure 1 shows, the bimodal/gshare hybrid predictor of 1993, and the improved version of 1994 [START_REF] Mcfarling | Trainable apparatus for predicting instruction outcomes in pipelined processors[END_REF], have an MPKI significantly lower than gshare. More research on hybrid predictors was published in the following years [START_REF] Chang | Branch classification: a new mechanism for improving branch predictor performance[END_REF][START_REF] Chang | Alternative implementations of hybrid branch predictors[END_REF][START_REF] Evers | Using hybrid branch predictors to improve branch prediction accuracy in the presence of context switches[END_REF][START_REF] Evers | Improving branch prediction by understanding branch behavior[END_REF][START_REF] Loh | Predicting conditional branches with fusion-based hybrid predictors[END_REF].

During the same period, some papers studied the aliasing problem stemming from the limited branch predictor size [START_REF] Talcott | The influence of branch prediction table interference on branch prediction scheme performance[END_REF][START_REF] Young | A comparative analysis of schemes for correlated branch prediction[END_REF][START_REF] Sechrest | Correlation and aliasing in dynamic branch predictors[END_REF]. There was a wave of studies trying to overcome the aliasing problem [START_REF] Chang | Improving branch prediction accuracy by reducing pattern history table interference[END_REF][START_REF] Sprangle | The agree predictor: a mechanism for reducing negative branch history interference[END_REF][START_REF] Michaud | Trading conflict and capacity aliasing in conditional branch predictors[END_REF][START_REF] Lee | The bi-mode branch predictor[END_REF][START_REF] Eden | The YAGS branch prediction scheme[END_REF]. This line of research culminated with the branch predictor of the Alpha EV8 processor [START_REF] Seznec | Design tradeoffs for the Alpha EV8 conditional branch predictor[END_REF], derived from Seznec's 2bc-gskew predictor [START_REF] Seznec | De-aliased hybrid branch predictors[END_REF].

The MPKIs of some emblematic "de-aliased" predictors are shown in Figure 1 (1997)(1998)(1999). These predictors are indeed more accurate than gshare. But compared against a well-tuned bimodal/gshare hybrid, the accuracy of de-aliased predictors is not much better, if better at all. The discrepancy between Figure 1 and the progresses claimed in the original papers is perhaps due, in part, to the CBP 2016 traces having different characteristics from the benchmarks used at the time. Still, the use of McFarling's meta-predictor as a de-aliasing technique was certainly overlooked back then. Nevertheless, research on de-aliased predictors improved our understanding of branch prediction. Eventually, the lessons from de-aliased predictors led to significant accuracy gains with the branch predictor of the Alpha EV8 processor (2bc-gskew-EV8 in Figure 1).

The Perceptron

In 1999-2000, two research teams, independently, started exploring the use of artificial neural networks for branch prediction [START_REF] Vintan | Towards a high performance neural branch predictor[END_REF][START_REF] Jiménez | Dynamic branch prediction with perceptrons[END_REF]. In particular, Jiménez and Lin's perceptron predictor had an important impact, not so much for the demonstrated prediction accuracy as for the completely different, thought-provoking branch prediction algorithm [START_REF] Jiménez | Dynamic branch prediction with perceptrons[END_REF][START_REF] Jiménez | Neural methods for dynamic branch prediction[END_REF]. Remarkably, the perceptron was the first branch predictor that could take advantage of a global history longer than 60 branches. It started the trend toward very long global histories. 3 In their 2001 paper, Jiménez and Lin emphasized a limitation of the original perceptron: linear separability. In the following years, several studies tackled linear separability [START_REF] Jiménez | Fast path-based neural branch prediction[END_REF][START_REF] Seznec | Redundant history skewed perceptron predictors: pushing limits on global history branch predictors[END_REF][START_REF] Seznec | Revisiting the perceptron predictor[END_REF][START_REF] Jiménez | Piecewise linear branch prediction[END_REF]. In particular, Seznec's RHSP was the first perceptron-based predictor to demonstrate a prediction accuracy substantially better than that of de-aliased predictors [START_REF] Seznec | Redundant history skewed perceptron predictors: pushing limits on global history branch predictors[END_REF][START_REF] Seznec | Revisiting the perceptron predictor[END_REF]. The hardware complexity of perceptron-based predictors was greatly reduced in 2004 when, inspired from Seznec's MAC-RHSP [START_REF] Seznec | Revisiting the perceptron predictor[END_REF], Tarjan and Skadron with the Hashed Perceptron [START_REF] Tarjan | Revisiting the perceptron predictor again[END_REF][START_REF] Tarjan | Merging path and gshare indexing in perceptron branch prediction[END_REF] and Seznec with the GEHL predictor [START_REF] Seznec | The O-GEHL branch predictor[END_REF][START_REF] Seznec | Analysis of the O-geometric history length branch predictor[END_REF], decoupled the perceptron width from the global history length.

TAGE

In 1996, Chen et al. considered adapting Prediction by Partial Matching (PPM), a data compression technique [START_REF] Cleary | Data compression using adaptive coding and partial string matching[END_REF], to branch prediction [START_REF] Chen | Analysis of branch prediction via data compression[END_REF]. More specifically, they applied PPM to local-history two-level prediction, assuming a PHT with as many entries as the number of distinct local-history values of all possible lengths up to a maximum length. Extra bits were stored in the PHT to detect cold PHT entries [START_REF] Chen | Enhancing the instruction fetching mechanism using data compresssion[END_REF]. Another research team confirmed the potential of PPM for branch prediction, but without considering hardware implementation constraints [START_REF] Federovsky | Branch prediction based on universal data compression algorithms[END_REF]. PPM was also proposed for indirect jump prediction [START_REF] Kalamatianos | Predicting indirect branches via data compression[END_REF].

Conventional BTBs feature tags [START_REF] Smotherman | The IBM ACS project[END_REF][START_REF] Ibbett | The MU5 instruction pipeline[END_REF][START_REF] Lee | Branch prediction strategies and branch target buffer design[END_REF], and in 1997-1998, when researchers started exploring more sophisticated indirect jump predictors, the use of tags was an obvious option [START_REF] Chang | Target prediction for indirect jumps[END_REF][START_REF] Driesen | The cascaded predictor: economical and adaptive branch target prediction[END_REF][START_REF] Driesen | Accurate indirect branch prediction[END_REF]. However, the use of tags in conditional branch predictors was counterintuitive, as this meant much fewer 2-bit up/down counters at equal storage. The fact that tags are a cost-effective option for conditional branch prediction was discovered by McFarling with the serial-BLG predictor [START_REF] Mcfarling | Branch predictor with serially connected predictor stages for improving branch prediction accuracy[END_REF] and by Eden and Mudge with the YAGS predictor [START_REF] Eden | The YAGS branch prediction scheme[END_REF].

In 2001, I introduced gtags, an approximation of PPM consisting of several cascaded YAGS using increasing global history lengths4 [START_REF] Michaud | A comprehensive study of dynamic global history branch prediction[END_REF], somewhat similar to Driesen and Hölzle's multi-cascaded indirect jump predictor [START_REF] Driesen | Multi-stage cascaded prediction[END_REF], but for conditional branches. I observed that prediction accuracy increases with the number of distinct global history lengths. However, at the time, it seemed difficult to implement a costeffective gtags with more than three tables. In particular, I noticed that freshly allocated entries sometimes generated many mispredictions, a problem that I call today the cold-counter problem (see Section 3). In 2004, I submitted to the first branch prediction championship a predictor called PPM-like [START_REF] Michaud | A PPM-like, tag-based predictor[END_REF], which was a 5-table gtags but with two key improvements (Figure 2). The first improvement was the introduction of a u bit in each tagged entry for estimating the usefulness of that entry, in order to better manage the limited predictor storage. The second improvement was the introduction of an m bit in tagless entries for controlling the initialization of the up/down prediction counter upon allocation of a tagged entry, in order to mitigate the cold counter problem. The PPM-like predictor was the first predictor not derived from the perceptron with a prediction accuracy substantially better than that of de-aliased predictors (Figure 1, 8KB budget).

In 2005, Seznec improved the PPM-like predictor quite substantially, which led to TAGE [START_REF] Seznec | A case for (partially) tagged geometric history length branch prediction[END_REF]. Unlike the PPM-like predictor, which uses a global history of branch directions, TAGE uses a path history [START_REF] Young | A comparative analysis of schemes for correlated branch prediction[END_REF][START_REF] Nair | Dynamic path-based branch correlation[END_REF].

The key features distinguishing TAGE from PPM-like are:

• TAGE considers not only the longest matching path (pred), but also the second-longest matching one (altpred).

• A tiny meta-predictor selects the final prediction between pred and altpred depending on the state of the pred up/down counter. This is for tackling the cold counter problem. Upon tagged entry allocation, the up/down counter is always initialized according to the branch outcome (TAGE has no m bit).

• Each tagged entry contains a u counter (generalization of the u bit).

• The pred entry is considered useful when it prevents the occurrence of a misprediction.

• The u counters are periodically decremented en masse so that dead entries are not locked forever.

• TAGE allocates a single entry per misprediction. All four branch prediction championships between 2006 and 2016 were won by André Seznec with a TAGE based predictor. Figure 1 shows two TAGE versions, the original 2006 version, and the latest 2016 version (see Appendix A). Seznec did a few changes over the years (in particular, he improved the management of u counters in 2011 [START_REF] Seznec | A new case for the TAGE branch predictor[END_REF]), sometimes depending on the storage budget considered. Nevertheless, the fundamentals of TAGE have not changed. The better accuracy of TAGE 2016 over TAGE 2006 is largely due to TAGE 2016 having more banks (and path lengths) and using bank interleaving, where a tagged bank is shared by several path lengths [START_REF] Seznec | A 64 Kbytes ISL-TAGE branch predictor[END_REF][START_REF] Seznec | TAGE-SC-L branch predictors again[END_REF].

Statistical correction

Gao and Zhou noticed that, in a PPM-like predictor, the longest match is not always the most accurate [START_REF] Gao | PMPM: prediction by combining multiple partial matches[END_REF], corroborating and generalizing what Seznec observed for TAGE [START_REF] Seznec | A case for (partially) tagged geometric history length branch prediction[END_REF]. The PMPM predictor they submitted to CBP 2006 combined some GEHL features (geometric path lengths, perceptron algorithm, adaptive threshold) with some TAGE features (tags, u counters) [START_REF] Gao | PMPM: prediction by combining multiple partial matches[END_REF]. However, they did not succeed in outperforming a well-tuned TAGE [START_REF]Championship branch prediction (CBP-2)[END_REF][START_REF] Seznec | The L-TAGE branch predictor[END_REF].

In 2006, Seznec noticed that, for huge storage budgets, and using the same input information, GEHL outperforms TAGE [START_REF] Seznec | The idealistic GTL predictor[END_REF]. Later, he found that this was due to TAGE behaving suboptimally on hard-to-predict branches, that is, weakly-biased branches with little or no global correlation. He proposed to complement TAGE with a statistical corrector, and found that a perceptron-inspired predictor such as GEHL is a costeffective statistical corrector for TAGE [START_REF] Seznec | A new case for the TAGE branch predictor[END_REF]. Seznec won the last three championships with this kind of predictor, called TAGE-SC [START_REF] Seznec | A 64 Kbytes ISL-TAGE branch predictor[END_REF][START_REF] Seznec | TAGE-SC-L branch predictors[END_REF][START_REF] Seznec | TAGE-SC-L branch predictors again[END_REF].

Prediction accuracy has improved a lot since gshare: as shown in Figure 1, the 64KB TAGE-SC-L of CBP 2016 has an average MPKI 43% lower than a 64KB gshare. 5

The cold counter problem

The cold counter problem is specific to PPM/TAGE-like predictors. Yet, although some features were introduced in the PPM-like predictor and in TAGE to reduce it, the cold-counter problem was neither named nor emphasized. I briefly mentioned some aspects of the problem in 2001 [START_REF] Michaud | A comprehensive study of dynamic global history branch prediction[END_REF], and it was only implicit in subsequent papers [START_REF] Michaud | A PPM-like, tag-based predictor[END_REF][START_REF] Seznec | A case for (partially) tagged geometric history length branch prediction[END_REF]. The paper that introduced statistical correction seems to downplay the importance of the meta-predictor in TAGE (called USE ALT ON NA) but does not explain that it is the statistical corrector that renders the meta-predictor practically superfluous [START_REF] Seznec | A new case for the TAGE branch predictor[END_REF]. The importance of the meta-predictor, which is real without the statistical corrector, is stated explicitly only in the source code of TAGE-SC-L in 2016 [START_REF]Championship branch prediction (CBP-5)[END_REF]. It is safe to say that the cold-counter problem has long been underestimated and did not receive the attention it deserves. This section provides a mathematical analysis of the cold-counter problem.

Initially, an up/down counter has no information about the branch (or path) it is trying to predict. After one occurrence of the branch, the up/down counter provides a prediction which is generally better than a random guess. In fact, if the branch is biased very strongly toward one direction, an up/down counter trained with a single occurrence of the branch is close to an ideal predictor for that branch. However, if the branch is weakly biased, it may take many occurrences of the branch for the counter to guess the branch bias with high confidence (assuming the counter is wide enough to record that amount of branch history). The number of occurrences necessary to train a wide-enough counter can be surprisingly large, as can be seen by modeling a single branch as a Bernoulli process, with probability q for the branch to be taken: the probability M (n) to mispredict the branch with a (wide-enough) up/down counter previously trained with n occurrences of the branch is

for n odd, M (n) = M (n + 1) = n-1 2 k=0 n k q k+1 (1 -q) n-k + n k= n+1 2 n k q k (1 -q) n-k+1
where it is assumed that the counter is initialized in state 0 when the first occurrence is taken, in state -1 when it is not taken. 6Figure 3 shows M (n) as a function of n, for q = 0.1 and for q = 0.3. The misprediction probability decreases as we accumulate knowledge about the branch and, in the limit, approaches the optimal misprediction probability min(q, 1 -q). However, convergence is slow. For prediction accuracy to be within 5% of the optimal accuracy, it takes 8 occurrences of the branch with q = 0.1, and 20 occurrences with q = 0.3.

PPM/TAGE-like predictors suffer from the cold counter problem because they allocate tagged entries on mispredictions, resetting the up/down counter of newly allocated entries. Worse, if there is no global correlation, the up/down counter tends to be initialized in the wrong direction. In the PPM-like predictor, the cold counter problem was somewhat mitigated by trying to initialize the up/down counter intelligently. TAGE provided a more effective solution to the cold counter problem with the meta-predictor selecting between the longest and second-longest matching paths. Nevertheless, TAGE does not solve the cold counter problem completely. This is why Seznec obtained significant accuracy gains by combining TAGE with a GEHL statistical corrector, as perceptron-based predictors such as GEHL barely suffer from the cold-counter problem.

Bayesian confidence estimation

While complementing TAGE with a statistical corrector is a possible solution to the cold-counter problem, it increases the branch predictor complexity and the branch prediction delay. In this paper, I propose to solve the cold-counter problem without a statistical corrector.

There are two fundamental reasons why the cold-counter problem exists in TAGE:

1. TAGE allocates tagged entries on nearly every branch misprediction.

2. TAGE cannot estimate precisely the "temperature" of an up/down counter.

This section addresses the second point (the first point is addressed in Section 5.6). Upon a tagged entry allocation, the counter is initialized in state 0 if the branch is taken, in state -1 if the branch is not taken. Subsequently, every time this entry is used to make a prediction, the counter is incremented or decremented depending on the branch direction. If we find the counter in state -4, we are sure that the counter has been updated at least 3 times after the initialization, so we know that the counter is relatively warm. However, if we find the counter is state -1, we do not know if the counter has just been initialized or has been updated multiple times. That is, we cannot distinguish between a cold counter and a weakly biased branch.

Therefore, I propose to replace the up/down counter with two counters n 1 and n 0 counting respectively the number of taken and not-taken occurrences. This way, the "temperature" of a tagged entry can be estimated precisely. Incidentally, the introduction of n 1 and n 0 also permits removing the u counter (explanation in Section 5.3). This change of tagged entry format, shown in Figure 4, is the foundation of BATAGE. Upon a tagged entry allocation, n 1 and n 0 are both reset, and either n 1 or n 0 is incremented according to the branch direction. On subsequent updates, n 1 or n 0 increase depending on the branch direction (ignoring for the moment the limited counter width). The prediction is given by the sign of n 0 -n 1 .

I propose to tackle the cold counter problem by associating prediction confidence levels with values of n 1 and n 0 . This way, when a tagged entry gives a low-confidence prediction, we can choose to ignore it and go to the next hitting tagged entry. The payload of a TAGE entry consists of an up/down counter (typically, 3 bits) and a u counter (1 or 2 bits). The payload of a BATAGE entry consists of two counters n 1 and n 0 (typically, 3 bits each) counting respectively the number of taken and not-taken occurrences.

Estimating branch predictability

In 1981, Smith observed that, when an up/down counter is saturated, this is an indication that the branch prediction provided by that counter is likely to be correct [START_REF] Smith | A study of branch prediction strategies[END_REF]. Smith's method can be generalized as follows. Let x ∈ [-2 c , 2 c -1] be the value of the up/down counter. A fine-grained confidence level can be obtained as |2x + 1|: the higher |2x + 1|, the more confident the prediction [START_REF] Seznec | Storage free confidence estimation for the TAGE branch predictor[END_REF]. A coarse-grained confidence level can obtained by comparing |2x + 1| with a threshold [START_REF] Jiménez | Composite confidence estimators for enhanced speculation control[END_REF].

Defining confidence levels from two counters n 1 and n 0 is not as straightforward. Obviously, there exists many different possibilities. Defining the confidence level as |n 1 -n 0 | is definitely not what we want, as this would be practically equivalent to having an up/down counter. Instead, we would like to exploit the information that n 1 and n 0 provide and that is not available from an up/down counter.

For example, let us consider two predictors giving different predictions:

• predictor A: n 1 = 2, n 0 = 0 (predict taken)

• predictor B:

n 1 = 3, n 0 = 6 (predict not-taken)
Given that sole information, which predictor is the most reliable? If we were using |n 1 -n 0 | as confidence level, we would select prediction B. However, there is nothing obvious here. Maybe we should trust predictor A instead, even though it is colder. In fact, the question is not well defined. To answer it, we must make some assumptions. I propose to assume that a branch has a constant but unknown probability q to be taken for a given path, with q uniformly distributed in [0, 1]. This assumption is somewhat arbitrary. Nevertheless it does not introduce any bias toward taken or not-taken and it is consistent with the fact that we know nothing about branches but what we learn through n 1 and n 0 . With this assumption, and using a Bayesian reasoning, it is possible to define confidence levels. Let us start from a uniform prior distribution P 0 (q) = 1, and let us apply Bayes' theorem to obtain a posterior distribution P (q|n 1 , n 0 ):

P (q|n 1 , n 0 ) = P (n 1 , n 0 |q) × P 0 (q) 1 0 P (n 1 , n 0 |t)P 0 (t)dt = P (n 1 , n 0 |q) 1 0 P (n 1 , n 0 |t)dt As P (n 1 , n 0 |q) = n 1 +n 0 n 1
q n 1 (1 -q) n 0 , we obtain

P (q|n 1 , n 0 ) = q n 1 (1 -q) n 0 B(n 1 + 1, n 0 + 1)
where B(x, y) = 1 0 t x-1 (1 -t) y-1 dt is the beta function. With the posterior distribution, we can obtain an estimate of the misprediction probability, which we denote m. If n 1 < n 0 , the prediction is not-taken, and the misprediction probability is q, hence m = If n 1 > n 0 , the prediction is taken, the misprediction probability is 1 -q, and we obtain a formula for m similar to the one above but with n 1 and n 0 permuted. Using the properties of the beta function, more precisely B(x + 1, y) = x x+y B(x, y) and B(x, y) = B(y, x), we obtain the following simple formula:

1 0 qP (q|n 1 , n 0 )dq = B(n 1 + 2, n 0 + 1) B(n 1 + 1, n 0 + 1)
m = 1 + min(n 1 , n 0 ) 2 + n 1 + n 0 (1)
Formula ( 1) is known as Laplace's rule of succession. Notice that m = 1/2 when n 0 = n 1 . Table 1 gives the value of m for n 1 and n 0 in [0, [START_REF] Chang | Improving branch prediction accuracy by reducing pattern history table interference[END_REF].

Estimator m provides an estimation of branch predictability, with low m meaning high confidence in the prediction. Going back to the previous example, prediction A gives m(2, 0) = 0.25, prediction B gives m(3, 6) ≈ 0.36. Hence prediction A is deemed more reliable than prediction B.

It must be emphasized that m is an estimate of the misprediction probability, not the actual misprediction probability, which is unknown to us. Moreover, there is no reason for q to be uniformly distributed in [0, 1]. The actual distribution of q is an empirical property depending on the application and on the path length. In particular, m ignores global correlations, which tend to push q away from 1/2. Nevertheless, I observed in my experiments the practical efficacy of estimator m, which is the basis of the BATAGE (Bayesian TAGE) predictor described in the following sections.

Defining confidence levels

BATAGE does not use the full spectrum of m values, but coarsens it into a few confidence levels: high, medium and low. In this paper, medium confidence is synonymous with unknown predictability. Notice that a single occurrence of a branch gives no information about its predictability. Therefore, the case n 1 +n 0 = 1 is a situation where predictability is unknown. This corresponds to m = 1/3, which is the natural threshold to use here. This leads to the following confidence levels:

m < 1/3 -→ high m = 1/3 -→ medium m > 1/3 -→ low
Table 1 uses a color code for the confidence levels: red for high confidence, orange for medium confidence and black for low confidence.

A hardware implementation does not need to compute m explicitly. It is sufficient to compute a value counter width 2 bits 3 bits 4 bits 5 bits predictor size 8KB 12KB 16KB 20KB average MPKI 10.47 10.07 10.12 10.29 m ∈ {0, 1, 2} directly from n 1 and n 0 :

m = 0 -→ high m = 1 -→ medium m = 2 -→ low
The 2-bit value m is obtained with simple combinational logic as follows. Define

medium = (n 1 = (2n 0 + 1)) ∨ (n 0 = (2n 1 + 1)) low = (n 1 < (2n 0 + 1)) ∧ (n 0 < (2n 1 + 1))
then m is the concatenation of bits low and medium:

m = 2 × low + medium

BATAGE

Like TAGE, BATAGE does not name one particular predictor configuration but a predictor family based on some common principles. This section describes those principles, focusing on what distinguishes BATAGE from TAGE. The parts of the predictor that are not described are essentially similar to TAGE.

The dual-counter

So far, we have assumed that n 1 and n 0 can increase indefinitely. In practice however, the n 1 and n 0 counters in a BATAGE entry are narrow (typically, 3 bits each), for the same reasons that TAGE has narrow prediction counters: under limited storage, the statistical benefit of using wide counters is not high enough to justify using storage for this, and using wide counters actually hurts prediction accuracy for certain branches not behaving like a Bernoulli process. For instance, Table 2 gives the average MPKI of a large bimodal predictor for different widths of the up/down counter. On the CBP 2016 traces, a large bimodal predictor is optimal with 3-bit up/down counters. 5-bit counters are significantly worse than 3-bit counters because of non-Bernoulli branch behaviors. So we must deal with the fact that n 1 and n 0 cannot exceed a limit nmax (with 3-bit counters, nmax = 7). BATAGE uses the following update method (C language): i f ( t a k e n ) { / / b r a n c h i s t a k e n i f ( n1 < nmax ) n1 ++; e l s e i f ( n0 >0) n0--; } e l s e { / / b r a n c h i s n o t t a k e n i f ( n0 < nmax ) n0 ++; e l s e i f ( n1 >0) n1--; } In other words, the counter corresponding to the branch direction is incremented, unless that counter equals nmax, in which case the other counter is decremented if not null. I call (n 1 , n 0 ) and the algorithm above the dual-counter automaton.

It should be noted that, after having hit the limit nmax once, the dual-counter behaves like an up/down counter with 2 × nmax + 1 states. Although formula (1) was established assuming unlimited n 0 and n 1 , BATAGE always uses the confidence levels shown in Table 1.

The dual-counter is used only in tagged entries, not in the tagless table, where this would be a waste of storage. The tagless table of BATAGE contains conventional up/down counters, like TAGE.

BATAGE prediction algorithm

Let L 1 , L 2 , • • • , L G denote the path lengths from shortest to longest, where G is the number of predefined path lengths. Similar to TAGE, a BATAGE prediction starts by reading simultaneously the tagless entry and the G tagged entries.

BATAGE computes the 2-bit confidence level m i for all tagged entries i ∈ [1, G], as described in Section 4.2. This computation is done in parallel with tag comparisons. When there is a tag miss at L i , we set m i = 3.

We also define a confidence level m 0 ∈ {0, 1, 2} for the tagless entry, as follows. The tagless entry of BATAGE contains a 3-bit up/down counter x ∈ [-4, 3]. The value m 0 is set according to the following equivalence:

x -4 -3 -2 -1 0 1 2 3 n 1 1 1 1 1 2 3 4 5 n 0 5 4 3 2 1 1 1 1 m 0 0 0 1 2 2 1 0 0
The BATAGE prediction algorithm is (C-like pseudo-code):

j = G f o r ( i =G-1; i >=0; i --) { i f ( m i < m j ) j = i ; } / / e n t

r y j p r o v i d e s t h e f i n a l p r e d i c t i o n

In other words, the final prediction is provided by the entry with the smallest m value, with priority to the longest path in case of equality. The prediction selection circuit of BATAGE is no more complex than that of TAGE. A divide-and-conquer approach is possible, allowing a tree structure, as illustrated in Figure 5. Other implementations are possible. In some implementations, it might be advantageous to use a 3-bit thermometer code for m (0 → 000, 1 → 001, 2 → 011, 3 → 111), which allows to compute the minimum of multiple m values with a bitwise AND.

Decay mechanism

In TAGE, the u counter is for protecting useful entries against eviction. There are no u counters in BATAGE. Instead, we use the confidence level as an indication of utility: a high confidence prediction is more likely to be useful than a medium or low confidence one. More precisely, the following rule is used in BATAGE: a tagged entry giving a high confidence prediction cannot be evicted.

Yet, a high confidence entry that is no longer used should not be locked forever. For such entry to become evictable, there must be a way to decay it. We define the action of decaying an entry as follows (C language) : The circuit for TAGE takes as input the hit/miss bit, the prediction bit, and the low-confidence bit (needed for the final selection between pred and altpred). The circuit for BATAGE takes as input the m value (2 bits) and the prediction bit. This example assumes 7 tagged banks. The path lengths increase from left to right. The leftmost input is the bimodal entry. 3: Updating the hitting entries. L 0 is the tagless entry. L p is the path length that provided the BATAGE prediction. Hitting entries are denoted L h (L 0 is one of them). When L p > L 0 , L n denotes the longest L h such that L h < L p .

In other words, we decay an entry by decrementing its highest count, n 1 or n 0 . Decay leaves the numerator in formula (1) unchanged but decreases the denominator. Hence decay increases m. In particular, decaying a high confidence dual-counter multiple times eventually leads to a medium confidence state (see Table 1). In practice, it is unnecessary to decay a dual-counter further than medium confidence.

Updating the hitting entries

Predictor update is done at the in-order retirement pipeline stage [START_REF] Seznec | A new case for the TAGE branch predictor[END_REF]. We define L 1 , L 2 , • • • , L G as in Section 5.2. Moreover, let L 0 denote the tagless entry. At update, BATAGE needs the following information: which path length L p provided the BATAGE prediction (Section 5.2), and all the path lengths L h corresponding to a tag hit (including L 0 ). Table 3 describes how the hitting entries are updated. When L p > L 0 , L n denotes the longest L h such that L h < L p . That is, L n is the next hitting entry after the entry that provided the BATAGE prediction. Entries L h < L n are not updated. Entries L h > L p are always updated with the branch direction, as described in Section 5.1. Those entries exist because shorter path lengths could not deliver 100% accuracy, but they were skipped probably because they are cold. By being updated, they can warm up and become useful. The dual-counter in entry L p is decayed when that entry is deemed useless, that is, when L p > L 0 and the prediction from L n is correct and L p and L n are both high confidence.

Allocating new entries

TAGE-like predictors allocate tagged entries on branch mispredictions because it is hoped that longer paths will provide more accurate predictions. Allocating a tagged entry means setting the tag and initializing the dual-counter according to the branch outcome (n 0 + n 1 = 1). Like TAGE, BATAGE allocates entries only upon mispredictions, at retirement. BATAGE allocates at most one entry per misprediction, like the original 2006 TAGE.

Let L m be the longest hitting path length (L m = L 0 when there are no hits), and s ≥ 1 a small random number. The allocation algorithm selects the entry corresponding to the shortest path length L r ≥ L m+s such that the entry at L r is not high confidence (m = 0). If such L r does not exist, no allocation is done, and we set r = G + 1. Then, independent of allocation's success, the entries L i ∈ [L m+s , L r-1 ] (which are all high confidence) are decayed with probability PDEC, as described in Section 5.3. The best value of PDEC is determined empirically. PDEC=1/4 works well on the CBP 2016 traces.

Controlled allocation throttling (CAT)

While Bayesian confidence estimation helps mitigate the cold-counter problem, it does not solve the root cause, which is the allocation of tagged entries on every branch misprediction.

I observed that, on traces with hard-to-predict branches, prediction accuracy improves when the allocation probability is set to a value less than one, which I call allocation throttling. This observation is valid both for TAGE and BATAGE. The problem is that allocation throttling degrades prediction accuracy severely on some traces. In fact, an allocation probability of one, as in TAGE, is the best fixed allocation probability on average.

The problem is to find the best allocation probability automatically. That is, we are looking for an effective controlled allocation throttling (CAT) method. After trying several methods that did not work, I made progress toward a solution when I conjectured that one could tell whether there are too many or too few allocations by looking at the global predictor state, more precisely the distribution of dual-counter states. I noticed that, when entries are allocated too aggressively, many entries are in medium or low confidence state, either because allocated entries are not reused, or because these entries are useless and kept in medium/low confidence state by the update rules (Table 3). Conversely, medium/low confidence entries are very few when the allocated entries are quickly reused and converted into high confidence entries. However, my attempts to adjust allocation throttling to obtain a fixed number of medium/low confidence entries did not produce good results. Then, I realized that what matters is not the absolute number of medium/low confidence entries but their proportion with respect to the number of moderately high confidence entries. The rest of this section provides a detailed description of the CAT method I found.

The main idea is to compare the amount of entries in a medium/low confidence state, denoted NHC (for not high confidence), and the amount of entries in a moderately high confidence state, denoted MHC, where MHC states are the states such that 0.17 < m < 1/3. That is, the MHC states are the high confidence states from which are excluded n 0 = 0, n 1 ≥ 4 and n 1 = 0, n 0 ≥ 4 (see Table 1). MHC states are generally transient states. Besides statistical fluctuations due to random branch behavior, allocation and decay are two major causes for the existence of MHC entries. When NHC entries significantly outnumber MHC entries, this is generally because allocation is easy (little decay) but allocated entries stay in a medium or low confidence state, hence allocation is probably too aggressive. Conversely, when MHC entries outnumber NHC entries, this is an indication that allocation is difficult (much decay) and allocated entries quickly evolve toward a high confidence state, so allocation can be more aggressive.

i f ( m i s p r e d i c t i o n ) { r = random i n [ 0 , MINAP-1]; i f ( r >= ( ( c a t * MINAP) / (CATMAX+ 1 ) ) ) { mhc = 0 ; s = random i n [ 1 , SKIPMAX ] ; f o r ( i =m+ s ; i ≤ G ; i ++) { i f ( m[i] < 1/3 ) { / / h i g h c o n f i d e n c
A possible implementation of CAT would be to monitor the fractions F n and F m of NHC and MHC entries respectively. In practice though, we just want to know the ratio F m /F n . This ratio can be estimated as follows. Upon an allocation attempt, the average number of skipped entries is 1/F n -1, neglecting the fact that the number G of tagged banks is finite. The fraction of high confidence entries that are MHC is F m /(1 -F n ). Hence the average number of skipped MHC entries is

1 F n -1 × F m 1 -F n = F m F n
which is the quantity we are looking for.

When the average number of skipped MHC entries is below a certain threshold CATR, the allocation probability is decreased if possible. The allocation probability cannot fall below a value 1/MINAP. When the average number of skipped MHC entries is greater than CATR, the allocation probability is increased if possible. Typically, the optimal CATR value lies between 1/4 and 3/4 and it tends to increase with G.

Figure 6 describes the BATAGE allocation algorithm. The cat counter controls the allocation probability. The allocation probability is 1 when cat is small, it is 1/MINAP when cat is close to CATMAX. The maximum cat value, CATMAX, is typically much larger than the total number of tagged entries. The predictor can warm up more quickly if cat is reset to zero when an application starts running.

Experimental evaluation

I evaluated BATAGE with the CBP 2016 simulation infrastructure, which provides a set of 220 traces for tuning predictors and a distinct set of 440 traces for evaluating them [START_REF]Championship branch prediction (CBP-5)[END_REF]. Figure 7: MPKI difference to 7KB TAGE for BATAGE, TAGE-GSC and BATAGE-GSC (higher is better). The traces are sorted for each curve separately so that the curve is non-decreasing.

The average MPKIs of TAGE and BATAGE are shown in Figure 1 (2016 and 2017) for 8KB, 32KB and 64KB storage budgets. To obtain a stand-alone 8KB TAGE, I started from the 7KB TAGE embedded in the 8KB TAGE-SC-L that won CBP 2016 [START_REF] Seznec | TAGE-SC-L branch predictors again[END_REF], and I tuned it without the statistical corrector. In particular, I replaced 3-bit counters in tagged entries with 4-bit counters (this improves the average prediction accuracy) and I scaled the predictor up to 8KB by increasing the number of banks and the number of path lengths. For the 32KB and 64KB TAGE, I proceeded similarly but starting from the 56KB TAGE embedded in the winning 64KB TAGE-SC-L.

The prediction accuracy gain of BATAGE over TAGE is modest on average, but tangible: it is roughly equivalent to the accuracy gain that the 2001 perceptron brought over an e-gskew. The 8KB BATAGE even matches the MPKI of the CBP 2016 winner, despite being simpler (no statistical corrector, no local history, no loop predictor).

The rest of this section provides a detailed evaluation of BATAGE, focusing on a 7KB storage budget. The 7KB TAGE component embedded in the 8KB TAGE-SC-L of CBP 2016 features two u bits per tagged entry. After replacing the 3-bit up/down counter in the tagged entry of TAGE with a 4-bit counter, the tagged entries of TAGE and BATAGE have the same payload size (6 bits). This way, the 7KB TAGE and BATAGE configurations can be compared with equal tag size and equal number of entries and banks. 4 compare TAGE and BATAGE with and without a global-history statistical corrector (GSC). The GSC is the 1KB statistical corrector implemented in the 8KB TAGE-SC-L of CBP 2016, but with the local-history components disabled so that the effect is pure statistical correction. Figure 7 shows the MPKI difference to the 7KB TAGE (higher is better) for the 440 traces. Table 4 provides the average MPKI (arithmetic mean over the 440 traces).

BATAGE does not need statistical correction

BATAGE outperforms TAGE significantly on several tens of traces (rightmost part of the red curve). The statistical corrector helps TAGE significantly, as expected [START_REF] Seznec | A new case for the TAGE branch predictor[END_REF]. The average MPKI of the 8KB TAGE-GSC is very close to that of the 7KB BATAGE. However, the 8KB BATAGE-GSC is only marginally better than the 7KB BATAGE. In practice, BATAGE does not need statistical correction.

= G + 1 k = 2 k = 1 k = G + 1 k = 2 k = 1 MPKI 4.

Controlled allocation throttling is an essential feature of BATAGE

Two features of BATAGE contribute to solve the cold-counter problem:

• Bayesian confidence estimation takes into account the "temperature" of tagged entries,

• Controlled allocation throttling decreases the number of allocations hence the number of cold entries.

The impact of the BATAGE prediction algorithm can be evaluated by restricting the selection of the final prediction among the first k hitting entries. The case k = G + 1 is the BATAGE prediction algorithm. The case k = 1 corresponds to selecting the prediction from the longest hitting path, as in the PPM-like predictor [START_REF] Michaud | A PPM-like, tag-based predictor[END_REF]. The case k = 2 corresponds to selecting between the longest and second longest hitting paths, as in TAGE (but without a meta-predictor).

The impact of CAT can be evaluated by disabling it, that is, by setting the allocation probability equal to one. When CAT is disabled and k is small, the use of decay in the update policy (Table 3) hurts prediction accuracy because the safety net provided by the BATAGE prediction algorithm has been removed. In these cases (no CAT, small k), the update policy must be modified so that the entry providing the final prediction is always updated. 7Table 5 gives the average MPKI for the 7KB BATAGE and for configurations with CAT disabled and/or a small k. Both disabling CAT and limiting k hurt prediction accuracy. Figure 8 shows, for each trace, the MPKI degradation from disabling CAT. Several tens of traces benefit substantially from CAT (leftmost part of the curve), and a few traces experience a degradation, yet barely noticeable (rightmost part of the curve).

CAT is an essential feature of BATAGE: without it, BATAGE would be no better than TAGE (compare tables 4 and 5). The management of u counters in TAGE is very effective at preserving useful entries. BATAGE has no u counter and instead relies on dual-counter decay. However, without CAT, dual-counters are decayed too aggressively on certain traces. CAT is effective not only at reducing the number of allocations but also at adjusting decay intensity.

Figure 9 compares the number of allocations per 1000 instructions (APKI) of TAGE and BATAGE, showing also the impact of disabling CAT. Without CAT, BATAGE would do more allocations than TAGE on average. This is because TAGE does not allocate entries when the overall prediction is incorrect but the prediction from the longest matching path is correct. 8 However, with CAT enabled, the number of allocations is reduced dramatically on many traces (Figure 9, right part of the red curve).

TAGE prediction CAT counter BATAGE

CAT on TAGE?

Given the benefit brought by CAT on BATAGE, it would be satisfying to find a CAT method for TAGE. 9 The dashed curves in Figure 10 show the prediction accuracy change when the allocation probability in TAGE is set to a fixed value, here 1/2 and 1/4. Allocation throttling with a fixed allocation probability improves prediction accuracy on certain traces but degrades it on other traces. In TAGE as in BATAGE, allocation throttling must be controlled. However, the CAT method described in Section 5.6 relies on specificities of BATAGE. It is not clear how TAGE could imitate BATAGE. This is a question for future research.

Nevertheless, it is possible to evaluate the potential prediction accuracy improvements that a hypothetical CAT method would bring to TAGE. Figure 11 depicts the experiment I did. I simulated a BATAGE in lockstep with TAGE, the cat counter of BATAGE being communicated to TAGE continuously so that TAGE can set its allocation probability like BATAGE at every instant. The result of this experiment is shown in Figure 10 as the solid red curve. The rightmost part of the curve shows that there is a potential for significant improvement on several tens of traces, motivating future research on CAT for TAGE.

Conclusion

The dual-counter is central to BATAGE. It permits solving the cold-counter problem by allowing Bayesian confidence estimation and by providing a way to control allocation throttling. My original motivation for getting rid of the u counter of TAGE was that the dual-counter needs more bits than a conventional up/down counter, and keeping the u counter would have made the tagged entry larger. Although dual-counter decay allows to recover some of the benefit of the u counter, the two mechanisms work differently, and perhaps they provide distinct advantages. Maybe future advances on TAGE-like prediction will come from a better understanding of the differences between TAGE and BATAGE. Nevertheless, dual-counter decay seems to be essential for CAT to work on BATAGE. Finding a CAT method for TAGE is a topic for future research.

A Legend for Figure 1 Figure 1 shows the average MPKI (arithmetic mean over the CBP 2016 traces) of various conditional branch predictors over the years, at 8KB, 32KB and 64KB storage budgets. The predictors are gshare [START_REF] Mcfarling | Combining branch predictors[END_REF], the 1993 bimodal/gshare hybrid [START_REF] Mcfarling | Combining branch predictors[END_REF], a bimodal/gshare where the meta-prediction table is accessed by hashing together the branch address and the global branch history [START_REF] Mcfarling | Trainable apparatus for predicting instruction outcomes in pipelined processors[END_REF][START_REF] Chang | Alternative implementations of hybrid branch predictors[END_REF], e-gskew [START_REF] Michaud | Trading conflict and capacity aliasing in conditional branch predictors[END_REF], bimode [START_REF] Lee | The bi-mode branch predictor[END_REF], YAGS [START_REF] Eden | The YAGS branch prediction scheme[END_REF], the original 2bc-gskew [START_REF] Seznec | De-aliased hybrid branch predictors[END_REF], a 2bc-gskew tuned along the lines of the Alpha EV8 predictor [START_REF] Seznec | Design tradeoffs for the Alpha EV8 conditional branch predictor[END_REF][START_REF] Seznec | An optimized 2bcgskew branch predictor[END_REF], the original global-history perceptron [START_REF] Jiménez | Dynamic branch prediction with perceptrons[END_REF], PBNP, [START_REF] Jiménez | Fast path-based neural branch prediction[END_REF], MAC-RHSP [START_REF] Seznec | Revisiting the perceptron predictor[END_REF], PWL [START_REF] Jiménez | Piecewise linear branch prediction[END_REF], O-GEHL [START_REF] Seznec | Analysis of the O-geometric history length branch predictor[END_REF], the PPMlike predictor [START_REF] Michaud | A PPM-like, tag-based predictor[END_REF], TAGE [START_REF] Seznec | A case for (partially) tagged geometric history length branch prediction[END_REF], L-TAGE [START_REF] Seznec | The L-TAGE branch predictor[END_REF], PMPM [START_REF] Gao | PMPM: prediction by combining multiple partial matches[END_REF], FTL [START_REF] Ishii | Fused two-level branch prediction with ahead calculation[END_REF], ISL-TAGE [START_REF] Seznec | A 64 Kbytes ISL-TAGE branch predictor[END_REF][START_REF] Seznec | A new case for the TAGE branch predictor[END_REF], FTL++ [START_REF] Ishii | Revisiting local history for improving fused twolevel branch prediction[END_REF], OH-SNAP [START_REF] Jiménez | OH-SNAP: optimized hybrid scaled neural analog predictor[END_REF][START_REF] St | Low-power, high-performance analog neural branch prediction[END_REF], TAGE-SC-L [START_REF] Seznec | TAGE-SC-L branch predictors[END_REF][START_REF] Seznec | TAGE-SC-L branch predictors again[END_REF], SSHP [START_REF] Jiménez | Strided sampling hashed perceptron predictor[END_REF], BFN [START_REF] Gope | Bias-free neural predictor[END_REF][START_REF] Gope | Bias-free branch predictor[END_REF], MPP [START_REF] Jiménez | Multiperspective perceptron predictor[END_REF], and BATAGE (this paper).

All the predictors were evaluated on the 440 CBP 2016 traces [START_REF]Championship branch prediction (CBP-5)[END_REF]. Predictors whose name is followed by the mention "CBP" in parentheses participated in a branch prediction championship. For these predictors, I used the original source code written by the authors, downloaded from the championship's web site. I did not modify the source code except for the minimal modifications necessary to simulate the predictor under the CBP 2016 simulation infrastructure. 10 I could not simulate the winning predictor of CBP 2004 [START_REF] Gao | Adaptive information processing: an effective way to improve perceptron predictors[END_REF], as it uses information not available in the CBP 2016 traces. Also, some CBP predictors are omitted for clarity.

For the 2bc-gskew-EV8, MAC-RHSP and TAGE 2006 predictors, I used the source code downloaded from André Seznec's website [START_REF] Seznec | [END_REF]. I obtained the TAGE 2016 predictor by disabling the statistical corrector in Seznec's CBP 2016 source code and by tuning TAGE parameters to fit the storage budget considered. I implemented the other predictors from the descriptions provided in the original papers.

I tuned the non-CBP predictors using the 223 training traces of CBP 2016. This tuning was done by varying the explicit parameters (for instance, the path length). I did not modify the original algorithms except for the bimode and YAGS predictors, which I made slightly more accurate with algorithm modifications simple enough to be considered part of the tuning.

All the non-CBP predictors and five CBP predictors (PPM-like, O-GEHL, L-TAGE, ISL-TAGE, BFN) use only a global branch or path history as first history level. The predictors using the perceptron algorithm are shown in red, those not using it in blue (the statistical corrector in ISL-TAGE and TAGE-SC-L is GEHLlike).

Figure 1 :

 1 Figure 1: Average number of mispredictions per 1000 instructions (MPKI) for various conditional branch predictors on the CBP 2016 traces for 8KB, 32KB and 64KB storage budgets (see Appendix A).

Figure 2 :

 2 Figure 2: The PPM-like predictor of CBP 2004 [2, 45].

Figure 3 :

 3 Figure3: Illustration of the cold counter problem: misprediction probability for a wide-enough up/down counter on a branch having probability q to be taken, as a function of the number of past occurrences.

Figure 4 :

 4 Figure 4: Tagged entry in TAGE (left) vs. BATAGE (right). The payload of a TAGE entry consists of an up/down

Figure 5 :

 5 Figure 5: Divide-and-conquer implementation of the prediction selection circuit for TAGE (left) and BATAGE (right).

  0 or Lp not high confidence or Ln not high confidence or incorrect prediction from Ln decay Lp > L 0 and Lp high confidence and Ln high confidence and correct prediction from Ln entry is probably useless Ln update with branch direction Lp > L 0 and Lp not high confidence improves prediction accuracy only slightly Table

Figure 6 :

 6 Figure 6: BATAGE allocation algorithm (C-like pseudo-code). L m is the longest hitting path length, m[i] is the m estimator for the entry at L i . The cat counter is initially set to zero.

Figure 7

 7 Figure 7 and Table4compare TAGE and BATAGE with and without a global-history statistical corrector (GSC). The GSC is the 1KB statistical corrector implemented in the 8KB TAGE-SC-L of CBP 2016, but with the local-history components disabled so that the effect is pure statistical correction. Figure7shows the MPKI difference to the 7KB TAGE (higher is better) for the 440 traces. Table4provides the average MPKI (arithmetic mean over the 440 traces).BATAGE outperforms TAGE significantly on several tens of traces (rightmost part of the red curve). The statistical corrector helps TAGE significantly, as expected[START_REF] Seznec | A new case for the TAGE branch predictor[END_REF]. The average MPKI of the 8KB TAGE-GSC

Figure 8 :

 8 Figure 8: Impact of disabling controlled allocation throttling on a 7KB BATAGE.

Figure 9 :

 9 Figure 9: APKI difference to TAGE (higher means fewer allocations).

Figure 10 :

 10 Figure 10: Allocation throttling on TAGE. The dashed curves are for a fixed allocation probability. The curve labeled "magic CAT" is for TAGE with a CAT counter provided by BATAGE.

Figure 11 :

 11 Figure 11: Doing CAT "magically" on TAGE.

Table 1 :

 1 Estimator m as a function of n 1 and n 0 (formula (1)).

					n 1
		0	1	2	3	4	5	6	7
		0 0.50 0.33 0.25 0.20 0.17 0.14 0.12 0.11
		1 0.33 0.50 0.40 0.33 0.29 0.25 0.22 0.20
		2 0.25 0.40 0.50 0.43 0.38 0.33 0.30 0.27
	n 0	3 0.20 0.33 0.43 0.50 0.44 0.40 0.36 0.33 4 0.17 0.29 0.38 0.44 0.50 0.45 0.42 0.38
		5 0.14 0.25 0.33 0.40 0.45 0.50 0.46 0.43
		6 0.12 0.22 0.30 0.36 0.42 0.46 0.50 0.47
		7 0.11 0.20 0.27 0.33 0.38 0.43 0.47 0.50

Table 2 :

 2 MPKI of a 32k-entry bimodal predictor on the CBP 2016 traces.

Table 4 :

 4 Average MPKI of TAGE and BATAGE with and without statistical correction.

	predictor TAGE TAGE-GSC BATAGE BATAGE-GSC
	size	7KB	8KB	7KB	8KB
	MPKI	4.42	4.27	4.29	4.24
	CAT		enabled		disabled
	prediction selection k

Table 5 :

 5 BATAGE: impact of disabling CAT and restricting the prediction algorithm.

	29	4.38	4.62	4.43	4.58	4.77

The

2-bit automaton used in the branch predictor of the S-1 computer built at the Lawrence Livermore Laboratory during the seventies was not an up/down counter[START_REF] Lee | Branch prediction strategies and branch target buffer design[END_REF]. The S-1 automaton is generally less accurate than the 2-bit up/down counter[START_REF] Ponder | An information-theoretic look at branch-prediction[END_REF][START_REF] Yeh | Two-level adaptive training branch prediction[END_REF][START_REF] Nair | Optimal 2-bit branch predictors[END_REF].

On the CPB 2016 traces, the average MPKI of an 8KB gshare is about

35% lower than that of a large bimodal predictor.[START_REF]Championship branch prediction (CBP-2)[END_REF] A recent study explains in detail how to implement a long global history[START_REF] Schlais | BADGR: a practical GHR implementation for TAGE branch predictors[END_REF].

In 2001, I quickly discarded the use of arithmetic progressions for the global history lengths and used a geometric progression instead[START_REF] Chang | Target prediction for indirect jumps[END_REF][START_REF] Driesen | Multi-stage cascaded prediction[END_REF][START_REF] Jiménez | Piecewise linear branch prediction[END_REF][START_REF] Seznec | Storage free confidence estimation for the TAGE branch predictor[END_REF] [START_REF] Michaud | A comprehensive study of dynamic global history branch prediction[END_REF]. The fact that a geometric progression is often close to optimal was discovered and emphasized by Seznec a few years later[START_REF] Seznec | Analysis of the O-geometric history length branch predictor[END_REF][START_REF] Seznec | A case for (partially) tagged geometric history length branch prediction[END_REF].

It should be recalled that the CBP rules do not limit predictor complexity besides a fixed storage budget. The

64KB TAGE-SC-L of CBP 2016 features a TAGE with 30 interleaved tagged banks and a statistical corrector with 20 weight tables and 3 local-history tables[START_REF] Seznec | TAGE-SC-L branch predictors again[END_REF].

The fact that M (n) decreases only on odd values of n can be understood intuitively as follows. The prediction from the counter is a majority vote over the past n occurrences. When n is odd, the counter cannot change its prediction upon the n+1-th occurrence unless the number of taken and not-take occurrences becomes equal, in which case the prediction is no better than a random guess.

i f ( n1 > n0 ) n1--; i f ( n0 > n1 ) n0--;

However the use of decay is important for CAT, as it is one of the mechanisms allowing to detect useless allocations by keeping useless entries in a medium confidence state.

This feature of TAGE decreases the number of allocations and brings modest MPKI reductions.

In a private discussion I had with André Seznec in july 2017, he told me that he was aware of the potential benefit of allocation throttling but had not found a way to control it.

The CBP 2016 traces are based on the ARM architecture, while previous championships were based on the Intel x86 architecture. Hence, for the old CBP predictors, I right-shifted every branch address by 2 bits.