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. / text
| Identifer | oai:union.ndltd.org:UTEXAS/oai:repositories.lib.utexas.edu:2152/23191 |
| Date | 17 February 2014 |
| Creators | Farooq, Muhammad Umar, active 2013 |
| Source Sets | University of Texas |
| Language | en_US |
| Detected Language | English |
| Format | application/pdf |
Page generated in 0.0016 seconds