Improving prediction accuracy of hard-to-predict branches using data value correlation
MetadataShow full item record
Performance of modern pipelined processor depends on steady flow of useful instructions for processing. Branch instruction disrupts sequential flow of instructions by presenting multiple paths through which a program can proceed. By predicting branch outcome early, branch predictors allow processor to continue fetching instructions from the predicted path. History-based dynamic branch predictors have shown to reach high prediction accuracy, yet certain branch types continue to mispredict. These are multitarget indirect branches and data-dependent direct and indirect branches. These are hard-to-predict branches since their outcome do not always exhibit repeatable patterns. This thesis describes branch prediction schemes for improving prediction accuracy of hard-to-predict branches using data value correlation. In these schemes, instead of relying on branch history information, compiler identifies program instructions whose output value strongly correlates with branch outcome. These correlated instructions are tracked at run-time, and their output is used for making branch predictions. Specifically, this thesis proposes following two branch prediction schemes: (i) Value-based BTB indexing (VBBI) is a low cost, compiler-guided scheme for predicting multi-target indirect branches. For every indirect branch, compiler identifies an instruction whose output strongly correlates with targets taken by the indirect branch. At run-time, multiple branch targets are stored and subsequently accessed from BTB using index formed by hashing indirect branch PC with output of the correlated instruction. (ii) Store-Load-Branch (SLB) predictor is a compiler-assisted branch prediction scheme for data-dependent branches. Typically, data-dependent branches are associated with program data structures such as arrays, linked list etc., and follow store-load-branch execution sequence. A set of memory locations is written at an earlier point in a program. Later, these locations are read, and used for evaluating branch condition. Branch outcome depends on values stored in data structure, which, normally do not have repeatable patterns. In SLB scheme, compiler identifies all program points where data structure associated with a data-dependent branch is modified. These marked store instructions are tracked at run-time, and stored values are used for computing branch flags ahead of time. Later, when branch instruction is fetched, pre-computed flags are read, and used for making predictions. This thesis introduces new branch prediction schemes, describes hardware structures and compiler analysis for implementing these schemes, evaluates their performance impact, and estimates their area, power and timing overhead.
Showing items related by title, author, creator and subject.
The functional network in predictive biology : predicting phenotype from genotype and predicting human disease from fungal phenotype McGary, Kriston Lyle (2008-12)The ability to predict is one of the hallmarks of successful theories. Historically, the predictive power of biology has lagged behind disciplines like physics because the biological world is complex, challenging to quantify, ...
The "Science" of Prediction: A Battery of Blind Back-Dated Validation Tests of PredictionWorks' New Venture Assessment System Butler, John Sibley; Cadenhead, Gary M. (McCombs School of Business, The University of Texas at AustinIC² Institute, The University of Texas at Austin, 2016-11-01)This report examines the results of a research partnership between PredictionWorks, a private firm, and The University of Texas at Austin (McCombs School of Business and the IC² Institute). PredictionWorks' New Venture ...
Prediction and verification of microRNA targets by MovingTargets, a highly adaptable prediction method Burgler, Craig; Macdonald, Paul M. (BMC Genomics, 2005-06-08)Background: MicroRNAs (miRNAs) mediate a form of translational regulation in animals. Hundreds of animal miRNAs have been identified, but only a few of their targets are known. Prediction of miRNA targets for translational ...