The Journal of Instruction-Level Parallelism

Championship Branch Prediction

website: http://www.jilp.org/cbp

Objective: The goal of the Journal of Instruction-Level Parallelism's (JILP) Championship Branch Prediction (CBP) competition is to evaluate and compare branch prediction algorithms in a common framework.  The competition’s simple and transparent evaluation process enables dissemination of results and techniques to the larger computer design community and allows independent verification of the competition’s results.  The performance and cost metrics are selected to be as simple and quantitative as possible.

Administration: CBP is administered by a selection committee and a steering committee.  The selection committee (with the assistance of outside referees) is used in the initial round of the contest to evaluate the submitted predictors and choose the finalists.  The steering committee administers the final round of the contest, ranking the finalists and crowning the champion.  The steering committee is also responsible for providing the rules for the competition.

Framework: A common evaluation framework, which includes a short set of traces and a driver that reads the traces and calls the branch predictor, will be distributed through the CBP website.

Traces: The traces will be approximately 30 million instructions long and will include both user and system activity.  There are two types of traces, those in the distributed trace list and those in the evaluation trace list.  Those in the distributed trace list will be provided to contestants, and will be used in the initial round of the contest to select the finalists.  Those in the evaluation trace list will not be provided to contestants, and will be used in the final round of the contest to rank the finalists and crown the champion.

Each trace list will contain 21 traces, classified into 7 categories, with 3 per category.  The categories are SPECfp, SPECint, Internet, Multimedia, Productivity, Server, and Workstation.  We cannot provide training and reference traces, so, unfortunately, profile-based predictors are excluded from this year's competition.

Driver: The driver will read a trace and call the branch predictor through a standard interface.  For each conditional branch, the predictor will return its prediction.  The driver will record whether the predictor was correct, and, at the end of the run, provide prediction accuracy statistics.  The framework will include an example predictor to help guide contestants.

The driver will provide the predictor with both static and dynamic information about the instructions in the trace.  For each instruction, static information—the instruction’s program counter, type (CALL, COND_BR, ALU, LD, …), and register source and destination specifiers—will be passed to the predictor.  Dynamic information—results, load and store addresses, and branch outcomes—will be made available on a delayed basis.  That is, for each instruction, the predictor will be passed the dynamic information about preceding instructions that have completed execution.

The steering committee believes that this framework allows the implementation of most published predictor algorithms in addition to providing some room for innovation.  We cannot provide training and reference traces needed for profile-based predictors and the traces do not contain wrong path information, which, unfortunately, excludes some predictors.  In the future, an attempt will be made to remedy this situation.

Contest: Predictors must be implemented within a fixed budget, and will be judged on performance.  The contest has two rounds: an initial and a final round.

Budget: Quantitatively assessing the cost/complexity of predictors is difficult.  To simplify the review process, maximize transparency, and minimize the role of subjectivity in selecting a champion, CBP will make no attempt to assess the cost/complexity of predictor algorithms.  Instead contestants will be given a storage budget of (64K + 256) bits.  All predictors must be implemented within the constraints of this budget.  And clear documentation must be provided to assure that this is the case.

Performance: Predictors will be scored on Taken/Not-Taken prediction accuracy only.  Accuracy will be measured in mispredicts per 1000 instructions, measured over the entire trace.

Initial Round: All predictors will be evaluated by selection committee members and referees using a blind review process. The selection committee will choose five finalists based on performance on the distributed trace list and the predictor writeup.

Final Round: The final round will be held at MICRO-37 in December. The five finalists will give a short presentation on their predictor at a workshop. Then, the performance of the five finalists will be evaluated using the evaluation trace list, and a champion will be declared based solely on the performance on the evaluation trace list.

Prizes:

Finalists: JILP will publish the predictor writeups of selected finalists (including the champion) in a special issue of the journal.  In addition, all finalists' source code, writeups, and performance results will be made publicly available through the CBP website.  Finalists may not opt-out of making this information public.

Champion: The champion will receive a trophy (details not yet determined).  In addition, the champion will receive glory and the adoration of the microarchitecture community.

Submissions: Submissions are to a special issue of JILP covering the competition.  They should be sent through the CBP website and must include the following:

1. An abstract, which must be submitted one week before the predictor submission deadline.
2. A writeup of the prediction algorithm including references to published work directly relevant to the implemented algorithm.  It should be single-spaced, in 11-point font or larger, on letter-size paper, and should not exceed 4 pages.  It should be in PDF viewable with Adobe Acrobat Reader version 3.0 or higher.
3. A table giving performance for the distributed trace list.
4. The driver code containing the predictor.  All code should be in ANSI C/C++ and POSIX conformant.  We will compile the code using GCC/G++ version 3.3.3 (or higher) on an IA-32 GNU/Linux system, and if we can't compile and run the code, we can't evaluate the predictor.

The abstract; writeup; and comments, variables names, etc. in the code; should be in English.

To prevent minor variations of a predictor, no person may be part of more than one submission.

Important Dates: