CSCE 614 Fall 2022 Project Proposal: Hybrid Branch Prediction

Due September 29, 2022 at 11:59pm as a PDF writeup turned in on Canvas.

This semester, the project for our class will be a branch prediction contest. You may work invididually, or in groups of 2 or 3 students.

The Project

For this project you will write C++ code to simulate a conditional branch predictor. The individual or group with the most accurate branch qualifying predictor will receive a special award to be determined later. You will work within a coding framework provided by the professor. This framework includes your code and tests your predictor against benchmarks traces, measuring accuracy as the number of incorrectly predicted conditional branches per 1000 instructions (MPKI). The entry with the lowest MPKI and code that meets the specifications of the contest will win.

Hybrid Branch Predictor

For this contest, your predictor must be a hybrid branch predictor. That is, it must have three components: a branch predictor, another branch predictor, and a chooser mechanism that combines predictions from the predictors to result in the final branch prediction. You must follow these rules:

Each predictor must implement one main algorithm. It may not combine more than one branch predicion algorithm, but it may use some optimizations.
You may use code you find on the Internet, but if you do so, you must cite this code in your writeup and in comments in your code.
Code you find on the Internet might implement a hybrid predictor already. For example, TAGE-SC-L is a hybrid of TAGE, perceptron, and a loop predictor. Since you are to implement a hybrid predictor, you would have to factor out an individual algorithm from this code to form one predictor.
Each predictor should be coded in a separate file, and the code for the chooser should also be in a separate file. Thus, you would have at least three files.
The total hardware budget of your predictor may not exceed 256KB. That is, the sum of all the memory used by the predictors and chooser should be more than 262,144 bytes. You may count only the bits used by your algorithm and not the bits used in C++. For example, if you have a counter that you know will never exceed values in [-64,+63] then that counter counts as only 6 bits even if you represent it in a 32 bit integer.

How To Choose Predictor

Choose some conditional branch prediction papers from the recent computer architecture literature, i.e. no earlier than 2004, and in a good venue like ISCA, MICRO, HPCA, ASPLOS, PACT, or ICS. Working within the framework provided by the professor, code a simulator for your hybrid branch predictor, i.e. two predictors and a chooser. You may make additional enhancements to the predictor design, but the basic predictor must be recognizable as having come from the paper you have chosen. There will be constraints on your code in terms of resource usage: you may not use more than a certain amount of storage and the code must be reasonably efficient so that we can run it on a large set of traces quickly; more details about this will come soon. For this project, the final product that you will turn in will be a writeup, in your own words, describing in detail the predictor and the steps you took to implement the simulator. You will also turn in your well-documented C++ code, which should compile under the distributed framework. Your code will be tested to determine the accuracy of your predictor. See this page for details of the competition as well as code you can use to get started. If you have an idea for a predictor that is not in the literature, or is a substantial modification of something from the literature, discuss this with the professor; if the idea is reasonable we can work on it and you can submit it to the "real" branch prediction contest.

What Is Due for the Proposal

The proposal should be a writeup giving a brief description of your branch prediction algorithm and any preliminary work you have so far. Include citations to relevant literature; there should be at least three citations (e.g. the citation for the predictor itself and a couple of citations for predecessors of this predictor). For the proposal, make sure to indicate who is in the group. Each student in a group should turn in an identical document describing the proposal to Canvas. The project itself will be due toward the end of the semester, but for the proposal component you should turn in your writeup before midnight on September 29, 2022 through Canvas.