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.




Tools in MET

The MET includes:

  • Aria, an execution-simulation library
  • Turandot, a parameterized processor model
  • Rondo, a branch prediction exploration tool
  • LeProf, a profiling and cache analysis tool
  • eOak, a system-level PowerPC 403GCX simulator
  • PavaRotti, a collection of tools for performance analysis and validation.
  • Trace tools for various trace formats.

PowerPC 7xx Chips