skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Combining Branch History and Value History For Improved Value Prediction
State-of-the-art value predictors either use control-flow context or data context to predict values. Predictors based on control-flow context use branch histories to remember past values, but these predictors require lengthy histories to predict anything other than constant and strided values. Predictors that use data context---also known as Finite Context Method (FCM) predictors---use a history of past values to predict a broader class of values, but such predictors achieve low coverage due to long training times, and they can become complex due to speculative value histories. We observe that the combination of branch and value history provides better predictability than the use of each history separately because it can predict values in control-dependent sequences of values. Furthermore, the combination improves training time by enabling accurate predictions to be made with shorter history, and it simplifies the hardware design by removing the need for speculative value histories. Based on these observations, we propose a new unlimited budget value predictor, Heterogeneous-Context Value Predictor (HCVP), that when hybridized with E-Stride, achieves a geometric mean IPC of 3.88 on the 135 public traces, as compared to 3.81 for the current leader of the Championship Value Prediction.  more » « less
Award ID(s):
1823546
PAR ID:
10201812
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
Second Championship Value Prediction
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, 53rd Annual IEEE/ACM International Symposium on Microarchitecture)
    null (Ed.)
    Abstract—The state-of-the-art branch predictor, TAGE, re- mains inefficient at identifying correlated branches deep in a noisy global branch history. We argue this inefficiency is a fundamental limitation of runtime branch prediction and not a coincidental artifact due to the design of TAGE. To further improve branch prediction, we need to relax the constraint of runtime only training and adopt more sophisticated prediction mechanisms. To this end, Tarsa et al. proposed using convo- lutional neural networks (CNNs) that are trained at compile- time to accurately predict branches that TAGE cannot. Given enough profiling coverage, CNNs learn input-independent branch correlations that can accurately predict branches when running a program with unseen inputs. We build on their work and introduce BranchNet, a CNN with a practical on-chip inference engine tailored to the needs of branch prediction. At runtime, BranchNet predicts a few hard-to-predict branches, while TAGE- SC-L predicts the remaining branches. This hybrid approach reduces the MPKI of SPEC2017 Integer benchmarks by 7.6% (and up to 15.7%) when compared to a very large (impractical) MTAGE-SC baseline, demonstrating a fundamental advantage in the prediction capabilities of BranchNet compared to TAGE- like predictors. We also propose a practical resource-constrained variant of BranchNet that improves the MPKI by 9.6% (and up to 17.7%) compared to a 64KB TAGE-SC-L without increasing the prediction latency. 
    more » « less
  2. ; ; ; ; ; ; ; ; ; (, 2020 IEEE Symposium on Security and Privacy)
    null (Ed.)
    The recent Spectre attack first showed how to inject incorrect branch targets into a victim domain by poisoning microarchitectural branch prediction history. In this paper, we generalize injection-based methodologies to the memory hierarchy by directly injecting incorrect, attacker-controlled values into a victim's transient execution. We propose Load Value Injection (LVI) as an innovative technique to reversely exploit Meltdown-type microarchitectural data leakage. LVI abuses that faulting or assisted loads, executed by a legitimate victim program, may transiently use dummy values or poisoned data from various microarchitectural buffers, before eventually being re-issued by the processor. We show how LVI gadgets allow to expose victim secrets and hijack transient control flow. We practically demonstrate LVI in several proof-of-concept attacks against Intel SGX enclaves, and we discuss implications for traditional user process and kernel isolation. State-of-the-art Meltdown and Spectre defenses, including widespread silicon-level and microcode mitigations, are orthogonal to our novel LVI techniques. LVI drastically widens the spectrum of incorrect transient paths. Fully mitigating our attacks requires serializing the processor pipeline with lfence instructions after possibly every memory load. Additionally and even worse, due to implicit loads, certain instructions have to be blacklisted, including the ubiquitous x86 ret instruction. Intel plans compiler and assembler-based full mitigations that will allow at least SGX enclave programs to remain secure on LVI-vulnerable systems. Depending on the application and optimization strategy, we observe extensive overheads of factor 2 to 19 for prototype implementations of the full mitigation. 
    more » « less
  3. ; ; ; ; (, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences)
    Dynamic topography refers to vertical deflections of Earth’s surface from viscous flow within the mantle. Here we investigate how past subduction history affects present dynamic topography. We assimilate two plate reconstructions into TERRA forward mantle convection models to calculate past mantle states and predict Earth’s present dynamic topography; a comparison is made with a database of observed oceanic residual topography. The two assimilated plate reconstructions ‘Earthbyte’ and ‘Tomopac’ show divergent subduction histories across an extensive deep-time interval within Pacific-Panthalassa. We find that introducing an alternative subduction history perturbs our modelled present-day dynamic topography on the same order as the choice of radial viscosity. Additional circum-Pacific intra-oceanic subduction in Tomopac consistently produces higher correlations to the geoid (more than 20% improvement). At spherical harmonic degrees 1–40, dynamic topography models with intra-oceanic subduction produce universally higher correlations with observations and improve fit by up to 37%. In northeast Asia, Tomopac models show higher correlations (0.46 versus 0.18) to observed residual topography and more accurately predict approximately 1 km of dynamic subsidence within the Philippine Sea plate. We demonstrate that regional deep-time changes in subduction history have widespread impacts on the spatial distribution and magnitude of present-day dynamic topography. Specifically, we find that local changes to plate motion histories can induce dynamic topography changes in faraway regions located thousands of kilometres away. Our results affirm that present-day residual topography observations provide a powerful, additional constraint for reconstructing ancient subduction histories. 
    more » « less
  4. ; ; (, Royal Society Open Science)
    Rapid urbanization has prompted considerable interest in understanding which species thrive or fail in these novel environments. Because half of the human population resides in coastal areas, studies that explicitly examine urban tolerances among coastal species are needed. Here, we sought to explain variation in coastal bird tolerances to urban habitats with species life history, diet, nest, social, sensory and sexual selection traits using phylogenetically informed models and three urban-tolerance indexes. We found that nest site height was the strongest predictor, with species nesting in elevated locations exhibiting greater urban tolerance, probably due to reduced anthropogenic disturbances and risk of predation. Life-history traits, including larger clutch sizes and lower brood value, reflecting more lifetime breeding attempts, also predicted urban tolerance, suggesting that fast reproductive strategies buffer against urban-associated risks. Contrary to our prediction, species with altricial young displayed higher urban tolerance, potentially due to shorter incubation and fledging times. Collectively, our results suggest that many of the predictors related to urban tolerance in songbirds also predict tolerances among a broader swath of avian diversity. Such knowledge should help researchers forecast the composition of coastal, urban bird communities in the future and will inform efforts to conserve functionally diverse coastal ecosystems. 
    more » « less
  5. ; ; (, Machine Learning for Computer Architecture and Systems)
    null (Ed.)
    Abstract—Multi-layer neural networks show promise in im- proving branch prediction accuracy. Tarsa et al. have shown that convolutional neural networks (CNNs) can accurately predict many branches that state-of-the-art branch predictors cannot. Yet, strict latency and storage constraints make naive adoption of typical neural network architectures impractical. Thus, it is necessary to understand the unique characteristics of branch prediction to design constraint-aware neural networks. This paper studies why CNNs are so effective for two hard-to- predict branches from the SPEC benchmark suite. We identify custom prediction algorithms for these branches that are more accurate and cost-efficient than CNNs. Finally, we discuss why out-of-the-box machine learning techniques do not find optimal solutions and propose research directions aimed at solving these inefficiencies. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email