The Experts below are selected from a list of 4884 Experts worldwide ranked by ideXlab platform
Lieven Eeckhout - One of the best experts on this subject based on the ideXlab platform.
-
Branch Predictor Warmup for Sampled Simulation through Branch History Matching
Transactions on High-Performance Embedded Architectures and Compilers II, 2009Co-Authors: Simon Kluyskens, Lieven EeckhoutAbstract:Computer architects and designers rely heavily on simulation. The downside of simulation is that it is very time-consuming -- simulating an industry-standard benchmark on today's fastest machines and simulators takes several weeks. A practical solution to the simulation problem is sampling. Sampled simulation selects a number of sampling units out of a complete program execution and only simulates those sampling units in detail. An important problem with sampling however is the microarchitecture state at the beginning of each sampling unit. Large hardware structures such as caches and Branch Predictors suffer most from unknown hardware state. Although a great body of work exists on cache state warmup, very little work has been done on Branch Predictor warmup. This paper proposes Branch History Matching (BHM) for accurate Branch Predictor warmup during sampled simulation. The idea is to build a distribution for each sampling unit of how far one needs to go in the pre-sampling unit in order to find the same static Branch with a similar global and local history as the Branch instance appearing in the sampling unit. Those distributions are then used to determine where to start the warmup phase for each sampling unit for a given total warmup length budget. Using SPEC CPU2000 integer benchmarks, we show that BHM is substantially more efficient than fixed-length warmup in terms of warmup length for the same accuracy. Or reverse, BHM is substantially more accurate than fixed-length warmup for the same warmup budget.
-
Branch history matching: Branch Predictor warmup for sampled simulation
Lecture Notes in Computer Science, 2007Co-Authors: Simon Kluyskens, Lieven EeckhoutAbstract:Computer architects and designers rely heavily on simulation. The downside of simulation is that it is very time-consuming - simulating an industry-standard benchmark on today's fastest machines and simulators takes several weeks. A practical solution to the simulation problem is sampling. Sampled simulation selects a number of sampling units out of a complete program execution and only simulates those sampling units in detail. An important problem with sampling however is the microarchitecture state at the beginning of each sampling unit. Large hardware structures such as caches and Branch Predictors suffer most from unknown hardware state. Although a great body of work exists on cache state warmup, very little work has been done on Branch Predictor warmup. This paper proposes Branch History Matching (BHM) for accurate Branch Predictor warmup during sampled simulation. The idea is to build a distribution for each sampling unit of how far one needs to go in the pre-sampling unit in order to find the same static Branch with a similar global and local history as the Branch instance appearing in the sampling unit. Those distributions are then used to determine where to start the warmup phase for each sampling unit for a given total warmup length budget. Using SPEC CPU2000 integer benchmarks, we show that BHM is substantially more efficient than fixed-length warmup in terms of warmup length for the same accuracy. Or reverse, BHM is substantially more accurate than fixed-length warmup for the same warmup budget.
-
HiPEAC - Branch history matching: Branch Predictor warmup for sampled simulation
High Performance Embedded Architectures and Compilers, 2007Co-Authors: Simon Kluyskens, Lieven EeckhoutAbstract:Computer architects and designers rely heavily on simulation. The downside of simulation is that it is very time-consuming -- simulating an industry-standard benchmark on today's fastest machines and simulators takes several weeks. A practical solution to the simulation problem is sampling. Sampled simulation selects a number of sampling units out of a complete program execution and only simulates those sampling units in detail. An important problem with sampling however is the microarchitecture state at the beginning of each sampling unit. Large hardware structures such as caches and Branch Predictors suffer most from unknown hardware state. Although a great body of work exists on cache state warmup, very little work has been done on Branch Predictor warmup. This paper proposes Branch History Matching (BHM) for accurate Branch Predictor warmup during sampled simulation. The idea is to build a distribution for each sampling unit of how far one needs to go in the pre-sampling unit in order to find the same static Branch with a similar global and local history as the Branch instance appearing in the sampling unit. Those distributions are then used to determine where to start the warmup phase for each sampling unit for a given total warmup length budget. Using SPEC CPU2000 integer benchmarks, we show that BHM is substantially more efficient than fixed-length warmup in terms of warmup length for the same accuracy. Or reverse, BHM is substantially more accurate than fixed-length warmup for the same warmup budget.
-
Improved composite confidence mechanisms for a perceptron Branch Predictor
Journal of Systems Architecture, 2006Co-Authors: Veerle Desmet, Lieven Eeckhout, Koen De BosschereAbstract:In 2001, Jimenez and Lin [Dynamic Branch prediction with perceptrons, Proceedings of the 7th International Symposium on High Performance Computer Architecture, 2001, pp. 197-206] introduced the perceptron Branch Predictor, the first dynamic Branch Predictor to successfully use neural networks. This simple neural network achieves higher accuracies (95% at a 4 KiB hardware budget) compared to other existing Branch Predictors and provides a free confidence level. In this paper, we first gain insight into this inherent confidence mechanism of the perceptron Predictor and explain why (additional) counter based confidence strategies can complement it. Second, we evaluate several composite confidence estimation strategies and compare them to the described technique by Jimenez and Lin [Composite confidence estimators for enhanced speculation control, Tech. rep., Department of Computer Sciences, The University of Texas at Austin, 2002]. We conclude that our overruling AND-combination of perceptron confidence and resetting counter mechanism outperforms the previously proposed confidence scheme.
André Seznec - One of the best experts on this subject based on the ideXlab platform.
-
A New Case for the TAGE Branch Predictor
2011Co-Authors: André SeznecAbstract:The TAGE Predictor is often considered as state-of-the-art in conditional Branch Predictors proposed by academy. In this paper, we first present directions to reduce the hardware implementation cost of TAGE. Second we show how to further reduce the misprediction rate of TAGE through augmenting it with small side Predictors. On a hardware implementation of a conditional Branch Predictor, the Predictor tables are updated at retire time. A retired Branch normally induces three accesses to the Branch Predictor tables : read at prediction time, read at retire time and write for the update. We show that in practice, the TAGE Predictor accuracy would not be significantly impaired by avoiding a systematic second read of the prediction tables at retire time for correct prediction. Combined with the elimination of silent updates, this significantly reduces the number of accesses to the Predictor. Furthermore, we present a technique allowing to implement the TAGE Predictor tables as bank-interleaved structures using single-port memory components. This significantly reduces the silicon footprint of the Predictor as well as its energy consumption without significantly impairing its accuracy. In the last few years, progress in Branch prediction accuracy has relied on associating a main state-of-the-art single scheme Branch Predictor with specialized side Predictors. As a second contribution of the paper, we develop this side Predictor approach for TAGE. At the recent 3rd Championship Branch Prediction, it was shown that the TAGE Predictor can be augmented with several side Predictors, each one addressing a category of predictions that is not optimally addressed by TAGE. The Immediate Update Mimicker tracks the inflight already executed but not retired Branches and use their result for correcting the predictions. Sometimes TAGE fails to predict when the control flow path inside the loop body is irregular. TAGE can be augmented with a loop Predictor to predict loops with constant iteration numbers, TAGE also sometimes fails to predict Branches that are not strongly biased but that are only statistically biased. The Statistical Corrector Predictor is introduced to track these statistically correlated Branches. These side Predictors allow to increase the prediction accuracy of TAGE. Building on top of these proposals, we further show that the Statistical Corrector Predictor can be used to leverage local history to further improve the potential of the TAGE Predictor. Furthermore, we show that the use of a Statistical Corrector Predictor based on local history, LSC, dwarfs the benefits of the loop Predictor and the global history Statistical Corrector. Finally, we present a cost-effective implementation of the TAGE-LSC Predictor using single-port memory components and a reduced number of accesses per prediction.
-
A 64 Kbytes ISL-TAGE Branch Predictor
2011Co-Authors: André SeznecAbstract:Description of a ISL-TAGE Branch Predictor
-
A 64-Kbytes ITTAGE indirect Branch Predictor
2011Co-Authors: André SeznecAbstract:The ITTAGE, Indirect Target TAgged GEometric length Predictor, was introduced in [5] at the same time as the TAGE conditional Branch Predictor. ITTAGE relies on the same principles as the TAGE Predictor several Predictor tables in- dexed through independent functions of the global Branch/path history and the Branch address. Like the TAGE Predictor, ITTAGE uses (partially) tagged components as the PPM-like Predictor [2]. It relies on (partial) match to select the predicted target of an indirect jump. TAGE also uses GEometric history length as the O-GEHL Predictor [3], i.e. , the set of used global history lengths forms a geometric series. This allows to e ciently capture correlation on recent Branch outcomes as well as on very old Branches. Due to the huge storage budget available for the ChampionShip, we propose an ITTAGE Predictor fea- turing 16 prediction tables. On the distributed set of traces, using a path history vector recording only in- formation from indirect jumps and calls was found to be (slightly) more e cient than using a path/Branch history vector combining information from all kind of Branches.
-
MICRO - A new case for the TAGE Branch Predictor
Proceedings of the 44th Annual IEEE ACM International Symposium on Microarchitecture - MICRO-44 '11, 2011Co-Authors: André SeznecAbstract:The TAGE Predictor is often considered as state-of-the-art in conditional Branch Predictors proposed by academy. In this paper, we first present directions to reduce the hardware implementation cost of TAGE. Second we show how to further reduce the misprediction rate of TAGE through augmenting it with small side Predictors. On a hardware implementation of a conditional Branch Predictor, the Predictor tables are updated at retire time. A retired Branch normally induces three accesses to the Branch Predictor tables: read at prediction time, read at retire time and write for the update. We show that in practice, the TAGE Predictor accuracy would not be significantly impaired by avoiding a systematic second read of the prediction tables at retire time for correct prediction. Combined with the elimination of silent updates, this significantly reduces the number of accesses to the Predictor. Furthermore, we present a technique allowing to implement the TAGE Predictor tables as bank-interleaved structures using single-port memory components. This significantly reduces the silicon footprint of the Predictor as well as its energy consumption without significantly impairing its accuracy. In the last few years, progress in Branch prediction accuracy has relied on associating a main state-of-the-art single scheme Branch Predictor with specialized side Predictors. As a second contribution of the paper, we develop this side Predictor approach for TAGE. At the recent 3rd Championship Branch Prediction, it was shown that the TAGE Predictor can be augmented with several side Predictors, each one addressing a category of predictions that is not optimally addressed by TAGE. The Immediate Update Mimicker tracks the inflight already executed but not retired Branches and use their result for correcting the predictions. Sometimes TAGE fails to predict when the control flow path inside the loop body is irregular. TAGE can be augmented with a loop Predictor to predict loops with constant iteration numbers, TAGE also sometimes fails to predict Branches that are not strongly biased but that are only statistically biased. The Statistical Corrector Predictor is introduced to track these statistically correlated Branches. These side Predictors allow to increase the prediction accuracy of TAGE. Building on top of these proposals, we further show that the Statistical Corrector Predictor can be used to leverage local history to further improve the potential of the TAGE Predictor. Furthermore, we show that the use of a Statistical Corrector Predictor based on local history, LSC, dwarfs the benefits of the loop Predictor and the global history Statistical Corrector. Finally, we present a cost-effective implementation of the TAGE-LSC Predictor using single-port memory components and a reduced number of accesses per prediction.
-
Storage Free Confidence Estimation for the TAGE Branch Predictor
2010Co-Authors: André SeznecAbstract:For the past 15 years, it has been shown that confidence estimation of Branch prediction can be used for various usages such as fetch gating or throttling for power saving or for controlling resource allocation policies in a SMT processor. In many proposals, using extra hardware and particularly storage tables for Branch confidence estimators has been considered as a worthwhile silicon investment. The TAGE Predictor presented in 2006 is so far considered as the state-of-the-art conditional Branch Predictor. In this paper, we show that very accurate confidence estimations can be done for the Branch predictions realized by the TAGE Predictor by simply observing the outputs of the Predictor tables. Many confidence estimators proposed in the literature only discriminate between high confidence predictions and low confidence estimations. It has been recently pointed out that a more selective confidence discrimination could useful. We show that the observation of the outputs of the Predictor tables is sufficient to grade the confidence in the Branch predictions with a very good granularity. Moreover a slight modification of the Predictor automaton allows to discriminate the prediction in three classes, low-confidence (with a misprediction rate in the 30 \% range), medium confidence (with a misprediction rate in 8-12\% range) and high confidence (with a misprediction rate lower than 1 \%).
Kevin Skadron - One of the best experts on this subject based on the ideXlab platform.
-
Implementing Branch-Predictor decay using quasi-static memory cells
ACM Transactions on Architecture and Code Optimization, 2004Co-Authors: Philo Juang, Kevin Skadron, Margaret Martonosi, Douglas W. Clark, Philip W. Diodato, Stefanos KaxirasAbstract:With semiconductor technology advancing toward deep submicron, leakage energy is of increasing concern, especially for large on-chip array structures such as caches and Branch Predictors. Recent work has suggested that larger, aggressive Branch Predictors can and should be used in order to improve microprocessor performance. A further consideration is that more aggressive Branch Predictors, especially multiported Predictors for multiple Branch prediction, may be thermal hot spots, thus further increasing leakage. Moreover, as the Branch Predictor holds state that is transient and predictive, elements can be discarded without adverse effect. For these reasons, it is natural to consider applying decay techniques---already shown to reduce leakage energy for caches---to Branch-prediction structures.Due to the structural difference between caches and Branch Predictors, applying decay techniques to Branch Predictors is not straightforward. This paper explores the strategies for exploiting spatial and temporal locality to make decay effective for bimodal, gshare, and hybrid Predictors, as well as the Branch target buffer (BTB). Furthermore, the predictive behavior of Branch Predictors steers them towards decay based not on state-preserving, static storage cells, but rather quasi-static, dynamic storage cells. This paper will examine the results of implementing decaying Branch-Predictor structures with dynamic---appropriately, decaying---cells rather than the standard static SRAM cell.Overall, this paper demonstrates that decay techniques can apply to more than just caches, with the Branch Predictor and BTB as an example. We show decay can either be implemented at the architectural level, or with a wholesale replacement of static storage cells with quasi-static storage cells, which naturally implement decay. More importantly, decay techniques can be applied and should be applied to other such transient and/or predictive structures.
-
ISPASS - Memory reference reuse latency: Accelerated warmup for sampled microarchitecture simulation
2003 IEEE International Symposium on Performance Analysis of Systems and Software. ISPASS 2003., 2003Co-Authors: Jonathan W Haskins, Kevin SkadronAbstract:This paper proposes to speedup sampled microprocessor simulations by reducing warmup times without sacrificing simulation accuracy. It exploiting the observation that of the memory references that precede a sample cluster, references that occur nearest to the cluster are more likely to be germane to the execution of the cluster itself. Hence, while modeling all cache and Branch Predictor interactions that precede a sample cluster would reliably establish their state, this is overkill and leads to long-running simulations. Instead, accurately establishing simulated cache and Branch Predictor state can be accomplished quickly by only modeling a subset of the memory references and control-flow instructions immediately preceding a sample cluster. Our technique measures memory reference reuse latencies (MRRLs) - the number of completed instructions between consecutive references to each unique memory location - and uses these data to choose a point prior to each cluster to engage cache hierarchy and Branch Predictor modeling. By starting cache and Branch Predictor modeling late in the pre-cluster instruction stream, we were able to reduce overall simulation running times by an average of 90.62% of the maximum potential speedup (accomplished by performing no pre-cluster warmup at all), while generating an average error in IPC of less than 1%, both relative to the IPC generated by warming up all pre-cluster cache and Branch Predictor interactions.
-
memory reference reuse latency accelerated warmup for sampled microarchitecture simulation
International Symposium on Performance Analysis of Systems and Software, 2003Co-Authors: Jonathan W Haskins, Kevin SkadronAbstract:This paper proposes to speedup sampled microprocessor simulations by reducing warmup times without sacrificing simulation accuracy. It exploiting the observation that of the memory references that precede a sample cluster, references that occur nearest to the cluster are more likely to be germane to the execution of the cluster itself. Hence, while modeling all cache and Branch Predictor interactions that precede a sample cluster would reliably establish their state, this is overkill and leads to long-running simulations. Instead, accurately establishing simulated cache and Branch Predictor state can be accomplished quickly by only modeling a subset of the memory references and control-flow instructions immediately preceding a sample cluster. Our technique measures memory reference reuse latencies (MRRLs) - the number of completed instructions between consecutive references to each unique memory location - and uses these data to choose a point prior to each cluster to engage cache hierarchy and Branch Predictor modeling. By starting cache and Branch Predictor modeling late in the pre-cluster instruction stream, we were able to reduce overall simulation running times by an average of 90.62% of the maximum potential speedup (accomplished by performing no pre-cluster warmup at all), while generating an average error in IPC of less than 1%, both relative to the IPC generated by warming up all pre-cluster cache and Branch Predictor interactions.
-
memory reference reuse latency accelerated sampled microarchitecture simulation
2002Co-Authors: Jonathan W Haskins, Kevin SkadronAbstract:This paper explores techniques for speeding up sampled microprocessor simulations by exploiting the observation that of the memory references that precede a sample, references that occur nearest to the sample are more likely to be germane during the sample itself. This means that accurately warming up simulated cache and Branch Predictor state only requires that a subset of the memory references and control-flow instructions immediately preceding a simulation sample need to be modeled. Our technique takes measurements of the memory reference reuse latencies (MRRLs) and uses these data to choose a point prior to each sample to engage cache hierarchy and Branch Predictor modeling. By starting cache and Branch Predictor modeling late in the pre-sample instruction stream, rather than modeling cache and Branch Predictor interactions for all pre-sample instructions we are able to save the time cost of modeling them. This savings reduces overall simulation running times by an average of 25%, while generating an average error in IPC of less than 0.7%.
Anthony Saporito - One of the best experts on this subject based on the ideXlab platform.
-
the ibm z15 high frequency mainframe Branch Predictor industrial product
International Symposium on Computer Architecture, 2020Co-Authors: Narasimha R Adiga, James J Bonanno, Adam B Collura, Matthias D Heizmann, Brian R Prasky, Anthony SaporitoAbstract:The design of the modern, enterprise-class IBM z15 Branch Predictor is described. Implemented as a multilevel look-ahead structure, the Branch Predictor is capable of predicting Branch direction and target addresses, augmented with multiple auxiliary direction, target, and power Predictors. Predictions are made asynchronously, and later integrated into the processor pipeline. The design is optimized for the unique workloads executed on these enterprise-class systems, including compute intensive and both large instruction and data footprint workloads. This paper highlights the major operations and functions of the IBM z15 Branch Predictor, including its pipeline, prediction structures and verification methodology. Explanations as to how the design matured to its current state are also provided.
-
ISCA - The IBM z15 High Frequency Mainframe Branch Predictor Industrial Product
2020 ACM IEEE 47th Annual International Symposium on Computer Architecture (ISCA), 2020Co-Authors: Narasimha R Adiga, James J Bonanno, Adam B Collura, Matthias D Heizmann, Brian R Prasky, Anthony SaporitoAbstract:The design of the modern, enterprise-class IBM z15 Branch Predictor is described. Implemented as a multilevel look-ahead structure, the Branch Predictor is capable of predicting Branch direction and target addresses, augmented with multiple auxiliary direction, target, and power Predictors. Predictions are made asynchronously, and later integrated into the processor pipeline. The design is optimized for the unique workloads executed on these enterprise-class systems, including compute intensive and both large instruction and data footprint workloads. This paper highlights the major operations and functions of the IBM z15 Branch Predictor, including its pipeline, prediction structures and verification methodology. Explanations as to how the design matured to its current state are also provided.
Simon Kluyskens - One of the best experts on this subject based on the ideXlab platform.
-
Branch Predictor Warmup for Sampled Simulation through Branch History Matching
Transactions on High-Performance Embedded Architectures and Compilers II, 2009Co-Authors: Simon Kluyskens, Lieven EeckhoutAbstract:Computer architects and designers rely heavily on simulation. The downside of simulation is that it is very time-consuming -- simulating an industry-standard benchmark on today's fastest machines and simulators takes several weeks. A practical solution to the simulation problem is sampling. Sampled simulation selects a number of sampling units out of a complete program execution and only simulates those sampling units in detail. An important problem with sampling however is the microarchitecture state at the beginning of each sampling unit. Large hardware structures such as caches and Branch Predictors suffer most from unknown hardware state. Although a great body of work exists on cache state warmup, very little work has been done on Branch Predictor warmup. This paper proposes Branch History Matching (BHM) for accurate Branch Predictor warmup during sampled simulation. The idea is to build a distribution for each sampling unit of how far one needs to go in the pre-sampling unit in order to find the same static Branch with a similar global and local history as the Branch instance appearing in the sampling unit. Those distributions are then used to determine where to start the warmup phase for each sampling unit for a given total warmup length budget. Using SPEC CPU2000 integer benchmarks, we show that BHM is substantially more efficient than fixed-length warmup in terms of warmup length for the same accuracy. Or reverse, BHM is substantially more accurate than fixed-length warmup for the same warmup budget.
-
Branch history matching: Branch Predictor warmup for sampled simulation
Lecture Notes in Computer Science, 2007Co-Authors: Simon Kluyskens, Lieven EeckhoutAbstract:Computer architects and designers rely heavily on simulation. The downside of simulation is that it is very time-consuming - simulating an industry-standard benchmark on today's fastest machines and simulators takes several weeks. A practical solution to the simulation problem is sampling. Sampled simulation selects a number of sampling units out of a complete program execution and only simulates those sampling units in detail. An important problem with sampling however is the microarchitecture state at the beginning of each sampling unit. Large hardware structures such as caches and Branch Predictors suffer most from unknown hardware state. Although a great body of work exists on cache state warmup, very little work has been done on Branch Predictor warmup. This paper proposes Branch History Matching (BHM) for accurate Branch Predictor warmup during sampled simulation. The idea is to build a distribution for each sampling unit of how far one needs to go in the pre-sampling unit in order to find the same static Branch with a similar global and local history as the Branch instance appearing in the sampling unit. Those distributions are then used to determine where to start the warmup phase for each sampling unit for a given total warmup length budget. Using SPEC CPU2000 integer benchmarks, we show that BHM is substantially more efficient than fixed-length warmup in terms of warmup length for the same accuracy. Or reverse, BHM is substantially more accurate than fixed-length warmup for the same warmup budget.
-
HiPEAC - Branch history matching: Branch Predictor warmup for sampled simulation
High Performance Embedded Architectures and Compilers, 2007Co-Authors: Simon Kluyskens, Lieven EeckhoutAbstract:Computer architects and designers rely heavily on simulation. The downside of simulation is that it is very time-consuming -- simulating an industry-standard benchmark on today's fastest machines and simulators takes several weeks. A practical solution to the simulation problem is sampling. Sampled simulation selects a number of sampling units out of a complete program execution and only simulates those sampling units in detail. An important problem with sampling however is the microarchitecture state at the beginning of each sampling unit. Large hardware structures such as caches and Branch Predictors suffer most from unknown hardware state. Although a great body of work exists on cache state warmup, very little work has been done on Branch Predictor warmup. This paper proposes Branch History Matching (BHM) for accurate Branch Predictor warmup during sampled simulation. The idea is to build a distribution for each sampling unit of how far one needs to go in the pre-sampling unit in order to find the same static Branch with a similar global and local history as the Branch instance appearing in the sampling unit. Those distributions are then used to determine where to start the warmup phase for each sampling unit for a given total warmup length budget. Using SPEC CPU2000 integer benchmarks, we show that BHM is substantially more efficient than fixed-length warmup in terms of warmup length for the same accuracy. Or reverse, BHM is substantially more accurate than fixed-length warmup for the same warmup budget.