Infrastructure for Branch Prediction Competition

Update: This update to the infrastructure corrects a very small mistake in the traces and adds undocumented source code for the compression engine used to pre-process the traces. This is the infrastructure for the branch prediction competition. There are three directories:

src. This directory contains C++ code for reading traces and driving the branch predictor code. The file my_predictor.h is distributed with a simple example branch predictor. Modify it to implement your predictor. The Makefile in this directory will build a program called predict that will read a trace file and print the number of mispredictions per 1000 instructions on the standard output.
traces. This directory contains the distributed traces in directories named for benchmarks.
doc. This directory contains the documentation including this file.

The csh script run runs the predict program on traces in a directory. Compile the predict program by changing to the src directory and typing make. Then run the program on all the traces by changing to the top-level cbp2 directory and typing run traces.

Writing Your Branch Predictor Simulator

Write your code in my_predictor.h, replacing the simple gshare predictor that comes with this infrastructure.

The code in my_predictor.h defines two classes:

my_update. This class is subclassed from branch_update which is defined in predictor.h. Your branch predictor will return a pointer to branch_update when it makes a prediction. The direction_prediction() method in this object should return true to predict that a branch is taken, or false to predict that a branch is not taken. When the driver code updates the branch predictor with the correct outcome, the same pointer will be sent to your update code. You can expand your my_update class to include state you want to refer to between calls to the prediction code. For example, the distributed my_update class stores the index into the gshare table.
my_predictor. This class is subclassed from the abstract class branch_predictor defined in predictor.h. Classes subclassing from branch_predictor must define a branch_update method with the following signature:
virtual branch_update *predict (branch_info &);
The driver program will call your predict method for every branch trace, giving information from the trace in a branch_info struct that is defined in branch.h. This struct contains fields for the branch address, the x86 branch opcode for a conditional branch, and a set of flags giving information on whether a branch is e.g. a return, a call, a conditional branch, etc. The return value from predict should be an object of (sub)class branch_update that gives the direction prediction for a conditional branch.
In addition to predict, you may define a method with the following signature in your my_predictor class:
virtual void update (branch_update *, bool, unsigned int);
The driver program will call your update method (if any) to give you a chance to update your predictor's state. The parameters are the branch_update pointer your predict method returned, a bool that is false if a conditional branch was not taken, true otherwise, and an unsigned integer target address of the branch.
Note: The driver program reports mispredictions only for conditional and indirect branches, but it calls the branch predictor predict and update methods on every branch. That's because you might want to use the information in a the stream of all branches, not just conditional and indirect branches, to help you predict conditional and indirect branches. You are not required to try to predict these non-conditional branches.

The Traces

Each of the distributed trace files represents the branches encountered during the execution of from 100 million to over 1 billion instructions from the corresponding benchmark. The traces include branches executed during the execution of benchmark code, library code, and system activity such as page faults. After the traces are generated, they are compressed with a crazy scheme I came up with one day when I was procrastinating from doing "real" work. Then they are compressed with xz. The compression scheme is lossless; the traces sent to your predictor are bit-for-bit identical to the traces collected from the running benchmarks.

System Requirements

This infrastructure has been tested on x86 hardware running Fedora Core 4 and Debian 3.1 operating systems as well as the Cygwin environment on Microsoft Windows XP, SPARC hardware running SunOS 5.8, and PowerPC hardware running MacOS X. The code should compile with no modifications with g++ >= 2.95.2. The program requires about 8MB plus whatever your branch predictor requires. On a Pentium D 2.8 GHz system the run script with the unmodified my_predictor.h takes about one minute run.

This infrastructure uses a few commands that are present on most Unix systems. If the pathnames for xz and/or gzip on your system are different from those in trace.h then please customize them.

Disclaimer and Feedback

This is a preliminary version of the infrastructure that has been subjected to testing by several graduate students. I do not claim that it is free of bugs. "Use the Source, Luke." I welcome your comments. Please send them to: djimenez@cse.tamu.edu.

This page was written by Daniel A. Jiménez.