The Experts below are selected from a list of 12486 Experts worldwide ranked by ideXlab platform
Yale N Patt - One of the best experts on this subject based on the ideXlab platform.
-
author retrospective for increasing the instruction fetch rate via multiple Branch Prediction and a Branch address cache
International Conference on Supercomputing, 2014Co-Authors: Tseyu Yeh, Deborah T Marr, Yale N PattAbstract:"Increasing the Instruction Fetch Rate viaMultiple Branch Prediction and a Branch Address Cache" was the first paper to propose a highly accurate hardware mechanism for predicting and fetching multiple non-contiguous basic blocks using leading-edge aggressive Branch predictors of the time. Prior to this paper, the methods to increase fetch bandwidth relied on software and compiler mechanisms to increase the size of the basic blocks themselves. The publication of our paper inspired an explosion of research to further improve the accuracy of multiple Branch Prediction, reduce complexity of fetching multiple basic blocks, or increase the fetch bandwidth in other ways. Our HPS research group defied conventional wisdom in a 1991 ISCA paper [1] that demonstrated instruction level parallelism (IPC) can be greater than two even for non-scientific workloads. This flew in the face of numerous "proofs" at the time. We showed that there was enough parallelism for an aggressive superscalar out-of-order execution engine to exploit to dramatically improve performance, provided that the penalties caused by incorrect Branch Predictions, cache misses, and TLB misses could be improved.
-
virtual program counter vpc Prediction very low cost indirect Branch Prediction using conditional Branch Prediction hardware
IEEE Transactions on Computers, 2009Co-Authors: Jose A Joao, Yale N Patt, Onur Mutlu, Robert CohnAbstract:Indirect Branches have become increasingly common in modular programs written in modern object-oriented languages and virtual-machine-based runtime systems. Unfortunately, the Prediction accuracy of indirect Branches has not improved as much as that of conditional Branches. Furthermore, previously proposed indirect Branch predictors usually require a significant amount of extra hardware storage and complexity, which makes them less attractive to implement. This paper proposes a new technique for handling indirect Branches, called Virtual Program Counter (VPC) Prediction. The key idea of VPC Prediction is to use the existing conditional Branch Prediction hardware to predict indirect Branch targets, avoiding the need for a separate storage structure. Our comprehensive evaluation shows that VPC Prediction improves average performance by 26.7 percent and reduces average energy consumption by 19 percent compared to a commonly used Branch target buffer based predictor on 12 indirect Branch intensive C/C++ applications. Moreover, VPC Prediction improves the average performance of the full set of object-oriented Java DaCapo applications by 21.9 percent, while reducing their average energy consumption by 22 percent. We show that VPC Prediction can be used with any existing conditional Branch Prediction mechanism and that the accuracy of VPC Prediction improves when a more accurate conditional Branch predictor is used.
-
Improving Branch Prediction accuracy by reducing pattern history table interference
International Journal of Parallel Programming, 1997Co-Authors: Po-yung Chang, Marius Evers, Yale N PattAbstract:A deeply pipelined superscalar processor needs an accurate Branch predictor in order to approach its performance potential. The 2-level Branch predictors have been shown to achieve high Prediction accuracy, yet they still suffer a significant number of misPredictions. It has been shown that a number of these misPredictions are due to interference in the pattern history tables. This paper details a method for reducing the amount of pattern history table interference by dynamically identifying some easily predictable Branches and inhibiting the pattern history table update for these Branches. We show that inhibiting the update in this manner reduces the amount of destructive interference in the global history variation of the 2-level Branch predictor, resulting in significantly improved Branch Prediction accuracy for the SPEC 95 benchmarks. For example, for a 2 K Byte gshare predictor, we eliminate 38% of the misPredictions for the gcc benchmark.
-
Recovery requirements of Branch Prediction storage structures in the presence of mispredicted-path execution
International Journal of Parallel Programming, 1997Co-Authors: Stéphan Jourdan, Jared Stark, Tse-hao Hsing, Yale N PattAbstract:Execution along mispredicted paths may or may not affect the accuracy of subsequent Branch Predictions if recovery mechanisms are not provided to undo the erroneous information that is acquired by the Branch Prediction storage structures. In this paper, we study four elements of the Two-Level Branch Predictor: the Branch Target Buffer (BTB), the Branch History Register (BHR), the Pattern History Tables (PHTs), and the Return Address Stack (RAS). For each we determine whether a recovery mechanism is needed, and, if so, show how to design a cost-effective one. Using five benchmarks from the SPECint92 suite, we show that there is no need to provide recovery mechanisms for the BTB and the PHTs, but that performance is degraded by an average of 30% if recovery mechanisms are not provided for the BHR and RAS.
-
the effects of mispredicted path execution on Branch Prediction structures
International Conference on Parallel Architectures and Compilation Techniques, 1996Co-Authors: Stéphan Jourdan, Jared Stark, Tse-hao Hsing, Yale N PattAbstract:Branch Prediction accuracies determined using trace-driven simulation do not include the effects of executing Branches along a mispredicted path. However, Branches along a mispredicted path will pollute the Branch Prediction structures if no recovery mechanisms are provided. Without recovery mechanisms, Prediction roles will suffer. In this paper, we determine the appropriateness of recovery mechanisms for the four structures of the Two-Level Adaptive Branch Predictor: the Branch Target Buffer (BTB), the Branch History Register (BHR), the Pattern History Tables (PHTs), and the Return Address Stack (RAS). We then propose cost-effective recovery mechanisms for these Branch Prediction structures. Far five benchmarks from the SPECint92 suite we show that performance is not affected if recovery mechanisms are not provided for the BTB and the PHTs. On the other hand, without any recovery mechanisms for the BHR and RAS, performance drops by an average of and 29%.
Daniel A Jimenez - One of the best experts on this subject based on the ideXlab platform.
-
an optimized scaled neural Branch predictor
International Conference on Computer Design, 2011Co-Authors: Daniel A JimenezAbstract:Conditional Branch Prediction remains one of the most important enabling technologies for high-performance microprocessors. A small improvement in accuracy can result in a large improvement in performance as well as a significant reduction in energy wasted on wrong-path instructions. Neural-based Branch predictors have been among the most accurate in the literature. The recently proposed scaled neural analog predictor, or SNAP, builds on piecewise-linear Branch Prediction and relies on a mixed analog/digital implementation to mitigate latency as well as power requirements over previous neural predictors. We present an optimized version of the SNAP predictor, hybridized with two simple two-level adaptive predictors. The resulting optimized predictor, OH-SNAP, delivers very high accuracy compared with other state-of-the-art predictors.
-
piecewise linear Branch Prediction
International Symposium on Computer Architecture, 2005Co-Authors: Daniel A JimenezAbstract:Improved Branch Prediction accuracy is essential to sustaining instruction throughput with todayýs deep pipelines. We introduce piecewise linear Branch Prediction, an idealized Branch predictor that develops a set of linear functions, one for each program path to the Branch to be predicted, that separate predicted taken from predicted not taken Branches. Taken together, all of these linear functions form a piecewise linear decision surface. We present a limit study of this predictor showing its potential to greatly improve predictor accuracy. We then introduce a practical implementable Branch predictor based on piecewise linear Branch Prediction. In making our predictor practical, we show how a parameterized version of it unifies the previously distinct concepts of perceptron Prediction and path-based neural Prediction. Our new Branch predictor has implementation costs comparable to current prominent predictors in the literature while significantly improving accuracy. For a deeply pipelined simulated microarchitecture our predictor with a 256KB hardware budget improves the harmonic mean normalized instructions-per-cycle rate by 8% over both the original path-based neural predictor and 2Bc-gskew. The average misPrediction rate is decreased by 16% over the path-based neural predictor and by 22% over 2Bc-gskew.
-
neural methods for dynamic Branch Prediction
ACM Transactions on Computer Systems, 2002Co-Authors: Daniel A Jimenez, Calvin LinAbstract:This article presents a new and highly accurate method for Branch Prediction. The key idea is to use one of the simplest possible neural methods, the perceptron, as an alternative to the commonly used two-bit counters. The source of our predictor's accuracy is its ability to use long history lengths, because the hardware resources for our method scale linearly, rather than exponentially, with the history length. We describe two versions of perceptron predictors, and we evaluate these predictors with respect to five well-known predictors. We show that for a 4 KB hardware budget, a simple version of our method that uses a global history achieves a misPrediction rate of 4.6p on the SPEC 2000 integer benchmarks, an improvement of 26p over gshare. We also introduce a global/local version of our predictor that is 14p more accurate than the McFarling-style hybrid predictor of the Alpha 21264. We show that for hardware budgets of up to 256 KB, this global/local perceptron predictor is more accurate than Evers' multicomponent predictor, so we conclude that ours is the most accurate dynamic predictor currently available. To explore the feasibility of our ideas, we provide a circuit-level design of the perceptron predictor and describe techniques that allow our complex predictor to operate quickly. Finally, we show how the relatively complex perceptron predictor can be used in modern CPUs by having it override a simpler, quicker Smith predictor, providing IPC improvements of 15.8p over gshare and 5.7p over the McFarling hybrid predictor.
-
boolean formula based Branch Prediction for future technologies
International Conference on Parallel Architectures and Compilation Techniques, 2001Co-Authors: Daniel A Jimenez, Heather Lynn Hanson, Calvin LinAbstract:Abstract: We present a new method for Branch Prediction that encodes in the Branch instruction a formula, chosen by profiling, that is used to perform history-based Prediction. By using a special class of Boolean formulas, our encoding is extremely concise. By replacing the large tables found in current predictors with a small, fast circuit, our scheme is ideally suited to future technologies that will have large wire delays. In a projected 70 nm technology and an aggressive clock rate of about 5 GHz, an implementation of our method that uses an 8-bit formula encoding has a misPrediction rate of 6.0%, 42% lower than that of the best gshare predictor implementable in that same technology. In today's technology, a 16-bit version of our predictor can replace bias bits in an 8K-entry agree predictor to achieve a 2.86% misPrediction rate, which is slightly lower than the 2.93% misPrediction rate of the Alpha 21264 hybrid predictor, even though the Alpha predictor has almost twice the hardware budget. Our predictor also consumes much less power than table-based predictors. This paper describes our predictor, explains our profiling algorithm, and presents experimental results using the SPEC 2000 integer benchmarks.
Po-yung Chang - One of the best experts on this subject based on the ideXlab platform.
-
Improving Branch Prediction accuracy by reducing pattern history table interference
International Journal of Parallel Programming, 1997Co-Authors: Po-yung Chang, Marius Evers, Yale N PattAbstract:A deeply pipelined superscalar processor needs an accurate Branch predictor in order to approach its performance potential. The 2-level Branch predictors have been shown to achieve high Prediction accuracy, yet they still suffer a significant number of misPredictions. It has been shown that a number of these misPredictions are due to interference in the pattern history tables. This paper details a method for reducing the amount of pattern history table interference by dynamically identifying some easily predictable Branches and inhibiting the pattern history table update for these Branches. We show that inhibiting the update in this manner reduces the amount of destructive interference in the global history variation of the 2-level Branch predictor, resulting in significantly improved Branch Prediction accuracy for the SPEC 95 benchmarks. For example, for a 2 K Byte gshare predictor, we eliminate 38% of the misPredictions for the gcc benchmark.
-
improving Branch Prediction accuracy by reducing pattern history table interference
International Conference on Parallel Architectures and Compilation Techniques, 1996Co-Authors: Po-yung Chang, Marius Evers, Yale N PattAbstract:Today's deeply pipelined, superscalar processors rely on accurate Branch Prediction in order to approach their performance potential. Branch misPredictions result in a flushing of the speculative information in the pipeline, thus limiting the amount of useful work that can be done. The 2-level Branch predictors have been shown to achieve high Prediction accuracy. However, it has also been shown that there is a high degree of pattern history table interference in 2-level Branch predictors and that the interference generally has a negative effect on the Prediction accuracy. This paper introduces a method for reducing the pattern history table interference by dynamically identifying some easily predictable Branches and inhibiting the pattern history table update for these Branches. We show how this technique reduces pattern history table interference for two versions of the 2-level Branch predictor and that this significantly improves Branch Prediction accuracy for the SPEC 95 benchmarks. In particular, we eliminate up to 30% of the misPredictions for the gcc benchmark.
-
using hybrid Branch predictors to improve Branch Prediction accuracy in the presence of context switches
International Symposium on Computer Architecture, 1996Co-Authors: Marius Evers, Po-yung Chang, Yale N PattAbstract:Pipeline stalls due to conditional Branches represent one of the most significant impediments to realizing the performance potential of deeply pipelined, superscalar processors. Many Branch predictors have been proposed to help alleviate this problem, including the Two-Level Adaptive Branch Predictor, and more recently, two-component hybrid Branch predictors.In a less idealized environment, such as a time-shared system, code of interest involves context switches. Context switches, even at fairly large intervals, can seriously degrade the performance of many of the most accurate Branch Prediction schemes. In this paper, we introduce a new hybrid Branch predictor and show that it is more accurate (for a given cost) than any previously published scheme, especially if the Branch histories are periodically flushed due to the presence of context switches.
Marius Evers - One of the best experts on this subject based on the ideXlab platform.
-
Improving Branch Prediction accuracy by reducing pattern history table interference
International Journal of Parallel Programming, 1997Co-Authors: Po-yung Chang, Marius Evers, Yale N PattAbstract:A deeply pipelined superscalar processor needs an accurate Branch predictor in order to approach its performance potential. The 2-level Branch predictors have been shown to achieve high Prediction accuracy, yet they still suffer a significant number of misPredictions. It has been shown that a number of these misPredictions are due to interference in the pattern history tables. This paper details a method for reducing the amount of pattern history table interference by dynamically identifying some easily predictable Branches and inhibiting the pattern history table update for these Branches. We show that inhibiting the update in this manner reduces the amount of destructive interference in the global history variation of the 2-level Branch predictor, resulting in significantly improved Branch Prediction accuracy for the SPEC 95 benchmarks. For example, for a 2 K Byte gshare predictor, we eliminate 38% of the misPredictions for the gcc benchmark.
-
improving Branch Prediction accuracy by reducing pattern history table interference
International Conference on Parallel Architectures and Compilation Techniques, 1996Co-Authors: Po-yung Chang, Marius Evers, Yale N PattAbstract:Today's deeply pipelined, superscalar processors rely on accurate Branch Prediction in order to approach their performance potential. Branch misPredictions result in a flushing of the speculative information in the pipeline, thus limiting the amount of useful work that can be done. The 2-level Branch predictors have been shown to achieve high Prediction accuracy. However, it has also been shown that there is a high degree of pattern history table interference in 2-level Branch predictors and that the interference generally has a negative effect on the Prediction accuracy. This paper introduces a method for reducing the pattern history table interference by dynamically identifying some easily predictable Branches and inhibiting the pattern history table update for these Branches. We show how this technique reduces pattern history table interference for two versions of the 2-level Branch predictor and that this significantly improves Branch Prediction accuracy for the SPEC 95 benchmarks. In particular, we eliminate up to 30% of the misPredictions for the gcc benchmark.
-
using hybrid Branch predictors to improve Branch Prediction accuracy in the presence of context switches
International Symposium on Computer Architecture, 1996Co-Authors: Marius Evers, Po-yung Chang, Yale N PattAbstract:Pipeline stalls due to conditional Branches represent one of the most significant impediments to realizing the performance potential of deeply pipelined, superscalar processors. Many Branch predictors have been proposed to help alleviate this problem, including the Two-Level Adaptive Branch Predictor, and more recently, two-component hybrid Branch predictors.In a less idealized environment, such as a time-shared system, code of interest involves context switches. Context switches, even at fairly large intervals, can seriously degrade the performance of many of the most accurate Branch Prediction schemes. In this paper, we introduce a new hybrid Branch predictor and show that it is more accurate (for a given cost) than any previously published scheme, especially if the Branch histories are periodically flushed due to the presence of context switches.
Xu Cheng - One of the best experts on this subject based on the ideXlab platform.
-
SWIP Prediction: Complexity-Effective Indirect-Branch Prediction Using Pointers
计算机科学技术学报英文版, 2012Co-Authors: Xie Zi-chao, Tong Dong, Huang Ming-kai, Shi Qin-qing, Xu ChengAbstract:Predicting indirect-Branch targets has become a performance bottleneck for many applications. Previous high-performance indirect-Branch predictors usually require significant hardware storage or additional compiler support, which increases the complexity of the processor front-end or the compilers. This paper proposes a complexity-effective indirect-Branch Prediction mechanism, called the Set-Way Index Pointing (SWIP) Prediction. It stores multiple indirect-Branch targets in different Branch target buffer (BTB) entries, whose set indices and way locations are treated as set-way index pointers. These pointers are stored in the existing Branch-direction predictor. SWIP Prediction reuses the Branch direction predictor to provide such pointers, and then accesses the pointed BTB entries for the predicted indirect-Branch target. Our evaluation shows that SWIP Prediction could achieve attractive performance improvement without requiring large dedicated storage or additional compiler support. It improves the indirect-Branch Prediction accuracy by 36.5% compared to that of a commonly-used BTB, resulting in average performance improvement of 18.56%. Its energy consumption is also reduced by 14.34% over that of the baseline.Computer Science, Hardware & ArchitectureComputer Science, Software EngineeringSCI(E)EI中国科技核心期刊(ISTIC)中国科学引文数据库(CSCD)1ARTICLE4754-7682
-
tap Prediction reusing conditional Branch predictor for indirect Branches with target address pointers
International Conference on Computer Design, 2011Co-Authors: Zichao Xie, Dong Tong, Mingkai Huang, Xiaoyin Wang, Qinqing Shi, Xu ChengAbstract:Indirect-Branch Prediction is becoming more important for modern processors as more programs are written in object-oriented languages. Previous hardware-based indirect-Branch predictors generally require significant hardware storage or use aggressive algorithms which make the processor front-end more complex. In this paper, we propose a fast and cost-efficient indirect-Branch Prediction strategy, called Target Address Pointer (TAP) Prediction. TAP Prediction reuses the history-based Branch direction predictor to detect occurrences of indirect Branches, and then stores indirect-Branch targets in the Branch Target Buffer (BTB). The key idea of TAP Prediction is to predict the Target Address Pointers, which generate virtual addresses to index the targets stored in the BTB, rather than to predict the indirect-Branch targets directly. TAP Prediction also reuses the Branch direction predictor to construct several small predictors. When fetching an indirect Branch, these small predictors work in parallel to generate the target address pointer. Then TAP Prediction accesses the BTB to fetch the predicted indirect-Branch target using the generated virtual address. This mechanism could achieve time cost comparable to that of dedicated-storage-predictors, without requiring additional large amounts of storage. Our evaluation shows that for three representative direction predictors-Hybrid, Perceptrons, and O-GEHL-TAP schemes improve performance by 18.19%, 21.52%, and 20.59%, respectively, over the baseline processor with the most commonly-used BTB Prediction. Compared with previous hardware-based indirect-Branch predictors, the TAP-Perceptrons scheme achieves performance improvement equivalent to that provided by a 48KB TTC predictor, and it also outperforms the VPC predictor by 14.02%.
-
TAP Prediction: Reusing Conditional Branch Predictor for Indirect Branches with Target Address Pointers
2011Co-Authors: Xie Zichao, Tong Dong, Huang Mingkai, Wang Xiaoyin, Shi Qinqing, Xu ChengAbstract:Indirect-Branch Prediction is becoming more important for modern processors as more programs are written in object-oriented languages. Previous hardware-based indirect-Branch predictors generally require significant hardware storage or use aggressive algorithms which make the processor front-end more complex. In this paper, we propose a fast and cost-efficient indirect-Branch Prediction strategy, called Target Address Pointer (TAP) Prediction. TAP Prediction reuses the history-based Branch direction predictor to detect occurrences of indirect Branches, and then stores indirect-Branch targets in the Branch Target Buffer (BTB). The key idea of TAP Prediction is to predict the Target Address Pointers, which generate virtual addresses to index the targets stored in the BTB, rather than to predict the indirect-Branch targets directly. TAP Prediction also reuses the Branch direction predictor to construct several small predictors. When fetching an indirect Branch, these small predictors work in parallel to generate the target address pointer. Then TAP Prediction accesses the BTB to fetch the predicted indirect-Branch target using the generated virtual address. This mechanism could achieve time cost comparable to that of dedicated-storage-predictors, without requiring additional large amounts of storage. Our evaluation shows that for three representative direction predictors-Hybrid, Perceptrons, and O-GEHL-TAP schemes improve performance by 18.19%, 21.52%, and 20.59%, respectively, over the baseline processor with the most commonly-used BTB Prediction. Compared with previous hardware-based indirect-Branch predictors, the TAP-Perceptrons scheme achieves performance improvement equivalent to that provided by a 48KB TTC predictor, and it also outperforms the VPC predictor by 14.02%.Computer Science, Hardware & ArchitectureEngineering, Electrical & ElectronicEICPCI-S(ISTP)