2nd JILP Championship Branch Prediction Competition (CBP-2) Contest Rules

This page details the rules for the competition including requirements for submission and use of the simulation infrastructure. Click here for an 8MB tar file that contains the infrastructure for the branch prediction competition. Browse the contents of the infrastructure here. That link also contains information about how to use the infrastructure e.g. how to run the simulator, system requirements, etc. Update: The simulation infrastructure has been updated to remove extraneous traces and provide additional software.

Discussion of these rules is welcome on the cbp2 Google group.

Rules Common to Both Tracks

These rules are common to both realistic and idealistic tracks:

Entry into the Competition

No person may take part in more than 3 submissions regardless of track. Co-authors may not be added after the initial submission. Program committee members who do not have access to the undistributed traces may participate in the competition. Of course, anyone else in the world is also free to enter the competition.

Submission Requirements

Your submission will include the following items:

Abstract: Submit an abstract summarizing your submission. Please specify whether you are submitting to the idealistic or realistic track. The abstract should not be longer than about 300 words.
Paper: This will be a conference-quality writeup of the predictor with references to relevant related work. This paper must be no longer than 2500 words and describe how the predictor works and how it conforms to the contest rules. The paper must be written in English. Although predictor accuracy and implementability is the primary means of judging the contest, the paper must clearly describe the predictor or the submission may be disqualified. Additional requirements for the individual tracks are discussed below.
Predictor code: A single C++ header file that can be included in the provided infrastructure must be submitted along with the paper as a separate file. This code must be well-commented so that it can be understood and evaluated; inscrutable code will be grounds for rejection. The file my_predictor.h from the infrastructure is distributed with a gshare predictor. Replace it with your own predictor's code. Additional requirements for the individual tracks are discussed below.
Predictor output: An ASCII file containing the result of running the run command from the infrastructure should be provided so that we can tell whether your code behaves the same on our system as it does on your system.

The abstract must be submitted before September 29, 2006, 11:59pm EDT (UTC-4). Send the abstract as an ASCII attachment to Daniel A. Jiménez at djimenez@cs.rutgers.edu.

The other items must all be submitted before October 6, 2006, 11:59pm EDT (UTC-4). Send them as attachments to Daniel A. Jiménez, ideally in a single message. Do not send executable code; send only the paper, the C++ header file, and the ASCII predictor output.

Behavior of Your Code

Your code must work within the infrastructure without changing any of the code or Makefile in the infrastructure; the only change should be to the header file called my_predictor.h. Your code must be C++.
Your code may not perform any input or output. The output of your code will be processed by scripts so it is essential that there be no extraneous output.
Do not assume the existence of any library code that is not part of the C++ language.
Your code should be deterministic. That is, it should make exactly the same predictions each time it is executed on the same trace. It should not rely on values from outside the simulator (e.g. time, PID, network, etc.).

Traces

Your predictor will be evaluated on a set of traces that have not been distributed. That is, you will design your predictor with the distributed traces on this web site, but a different set will be used to rank the traces and determine the winner. This is to avoid having your algorithm be tuned too precisely to a given set of traces so that it will be a more general branch predictor. The non-distributed traces will be similar in nature to the distributed traces.

Rules for the Realistic Track

These rules are specific to the realistic track. The purpose of this track is to evaluate predictors that might reasonably be implemented in a future processor. Thus, part of the evaluation of your predictor will be qualitative. Your predictor should strive to be as accurate as possible but maintaining a reasonable cost. Take into account the latency, complexity, area, and power of your proposed predictor.

Your predictor may use no more than 32 kilobytes of state plus 256 extra bits, i.e. 262,400 bits. Only the storage that would actually be required by an implementation of your algorithm must be counted. For example, a 2-bit counter implemented with a 32-bit integer counts as only 2 bits. However, try to avoid using STL, e.g. an associative array implemented with std::map would require a description of the hardware mechanism behind implementing the array, with all the storage required.
In your code as well as in your paper, you must make a clear accounting of all the bits of state used in your predictor.
In your paper, you must convincingly argue that your predictor is reasonbly implementable. You must say why the latency, complexity, area, and power of your predictor are reasonable.
If a feature of a proposed design might have an impact on accuracy, then this feature must be reflected in the code. For example, an ahead-pipelined predictor might be less accurate but more implementable than an all-at-once predictor, so the impact of ahead-pipelining should be reflected in the code.
If a feature of a proposed design might be considered unfamiliar to the branch prediction community, please take the time to familiarize us with it and argue that it is sufficiently implementable.

Rules for the Idealistic Track

These rules are specific to the idealistic track. The purpose of this track is to push the limit of branch prediction accuracy. Given an almost unlimited budget, how accurately can we predict branches using only control-flow information? You should feel free to use your imagination with this track; we would prefer new ideas over tweaking of previous work. The winner for this track will be selected based only on accuracy; implementability is not a concern. Although "anything goes" for this track, there are a few rules we must set so that we can be sure that it will be possible to evaluate all of the submissions:

The run script from the infrastructure when invoked on the traces directory should take no longer than about 2 hours to finish on a 3.06GHz Pentium 4-based computer. Entries that consume more time are subject to disqualification.
The simulator must be able to run on a computer with no more than 1GB of RAM.

Please feel free to comment on these rules on the cbp2 Google group.

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