MET - 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.