Rondo Rondo is a trace-driven environment for simultaneously exploring the prediction accuracy of a
collection of branch prediction algorithms. Those algorithms are described in terms of basic parameters (size of tables, size of counters, table indexing function), and tools in the environment generate C
source code modeling the predictors. The resulting model is fed an instruction trace generated by Aria or some other tool external to The MET.Rondo is capable of modeling
- Single-table predictors, based on instruction addresses or on history information.
- Multiple-table predictors, wherein each of the component tables uses any of the techniques applicable to the case of single-table predictors; these are augmented with a selection function, for
choosing whenever two or more tables provide a valid prediction.
Rondo consists of
- make_model
, a tool that builds the branch predictors model based on a parameterized specification of the predictors;
- instr_bc
, an instrumentation tool for generating an execution trace of a program containing only information relative to conditional branch instructions;
- make_trace
, a tool that allows the synthetic generation of branch instruction traces based on strings of "branch taken" and "branch not taken" tokens.
For the case of single-table predictors, the results generated by Rondo indicate the number of correct predictions (i.e., prediction accuracy). For the case of multiple-table predictors, the results
include the overall accuracy of the predictor, as well as the accuracy of the individual components, and the quantification of missed opportunities (selection of a wrong prediction when there was a correct
one). See the Publications and Presentations for further information regarding Rondo. |
