There are four project options. All require that you submit a written proposal by Dec. 1st in class.
You will have to deliver the following:
E-mail the tarball and the report in PDF to moshovos@eecg.toronto.edu by Dec. 20th, 11:59pm using “ACA: BPRED” as your subject line.
This should be an at most two pages. One page is just fine – don't feel that you have to write lots. You should explain in the following order:
1. Topic, i.e., what are you going to do. Start by motivating the particular work. Give a set of reasons why this is relevant (not from an educational perspective but from a computer design perspective).
2. Methodology and Goals. You will be expected to use Simplescalar and the SPEC CPU 2000 benchmarks that will be provided. Here you should explain which experiments you will be performing and why. Try to justify why these experiments are the most relevant given the amount of time you have available. This will be our contract: this is what you promise to do. If you are validating an existing study, say which parts you will validate. You are not expected to go over all results and validate everything. A small subset of important results is good enough. The most important part is picking which results are important. You may also want to discuss other results not found in the paper that you think complement the work and you are willing to try to get.
3. If you are participating in the branch prediction competition part (2) above is obviously given to you. Instead, please suggest what your plans are for improving prediction.
Remember: while these may evolve or change you are required to start with a meaningful plan. No point starting something if you cannot articulate why this might be interesting or doable.
Try to limit this to at most four pages. (Remember: it’s easy to write a lot of text. It’s hard to write concise.) An approximate format is:
1. Introduction: Motivation and Problem statement. BRIEFLY. Also conclude with forecasting what your method and most important results are.
2. Expanded motivation if needed.
3. Related Work. Please emphasize this section if you decide to validate a set of published results. The publications suggested later in this document are not all very recent. It is your responsibility to find and report any related work.
4. If you are proposing a new mechanism describe it.
5. Methodology. Which benchmarks, what simulation method and which simulator, machine configuration and any other relevant parameters. Also a brief summary of your metrics and WHY are you using them
6. Evaluation. One by one the results. Explain the results. Why do they look they way they do? Are they correct? Can you come up with examples that show that the trends exhibited are possible?
7. Conclusions. “I am so good I cannot stand myself. Maybe I should donate my brain to science” put in less obvious terms. Future directions (not left or right).
If for whatever reason you are not able to deliver exactly what your promised, please explain why. Please keep this in mind: I'm more interested to see how you think. It's better to do less and do it well than to do lots and do them poorly.
You will *not* be required to give a presentation at the end of the course.
The simulator source code (modified version of Simplescalar) and the traces are available through the eecg.toronto.edu filesystem under ~moshovos/ACA08/. The simulator code is in the myss directory. The traces are in the spec2k.eio directory.
To use the traces simply append them as the last argument to the simulator you use. For example:
sim-bpred 164.gzip.trace.1Ba1B.eio
The trace contains a complete image of the initial state of memory and registers, plus all data exchanged through system calls. The traces are 1B instructions long.
One program that will definitely be challenging for prediction will be gcc. So, if you are trying things out try it first and may be instruct sim-bpred, sim-safe, sim-cache or sim-outorder to only run a few hundred million instructions (see sim-XYZ -help).
Before you compile the simulator configure it using “make config-pisa”. If you grabbed the simulation sources before Nov. 18 and are having problems compiling, please grab them again. I edited some of the files so that they compile without problems on a linux box. The EIO traces are LITTLEendian so chances are you will not be able to complete this on a BIG endian machine such as an x86 box. If you plan to use the original Simplescalar source code, you'll have to manually uncompress the .eio files using gzip. The original simplescalar supports uncompressed .eio files, while the one provided for the project has built-in support for using compressed .eio files. This saves disk space and bandwidth and may make your simulations run faster, as, chances are, the bottleneck will be the disk.
The goal is to develop an accurate branch direction predictor (taken or not taken). At the very least your predictor should be able to beat the based predictor which will be provided as part of the simulator source code. Ideally, your predictor will beat this base predictor by a significant margin and your predictor will perform the best among all predictors developed as part of the course. Predictor X is better than predictor Y on benchmark Z if the prediction accuracy of predictor X is higher than the predictor accuracy of Y when running benchmark Z. Prediction accuracy is measured as the percentage of direction predictions that are correct.
For this project you will use sim-bpred from the simplescalar source code. Sim-bpred is the sim-safe simulator you used in the homework extended with a branch predictor component. By default sim-bpred reports direction accuracy as bpred_bimod.bpred_dir_rate. When you modify sim-bpred.c introduce a new statistic called mybpred.dir_rate and use it to report the accuracy of your predictor.
We will provide you with traces that can be used with sim-bpred.
You will have to work alone on this project
Modify sim-bped.c to include your predictor. Make sure the existing predictors still work correctly. Introduce two options: -mybpred:r and -mybpred:u. The first should invoke your restricted storage predictor and the second the unrestricted predictor. There should be no other options necessary for running the simulation with your chosen predictor sizes (the ones you selected to compete with).
Option 2: If you do not wish to design a new predictor you could alternatively implement a few existing predictors in Simplescalar. You will have to implement, OGEHL, YAGS, and 2BcgSkew. As a starting point the following two files contain implementations of these predictors in C++ as they were implemented in the SESC simulator: BPred.cpp, BPred.h.
If you choose option 2, you will have to do a design exploration and show how accuracy varies for the three predictors comparing them to the baseline predictors below.
The base predictor that you will have to beat is a combined predictor with:
Sim-bpred implements this directly. Use the following options:
-bpred comb -bpred:2lev 1 65536 10 1 -bpred:bimod 65536 -bpred:comb 65536
Please develop two predictors. The first will have to use at most 64KB of storage (512Kbits). For the second you can use as much storage as you like. In the storage calculations do not include the PC, but do include any other bits your predictor uses. Of course, we are refering to the storage used in an actual hardware implementation. So, a 64K entry bimodal would use 128Kbits (64K entries each using 2 bits for the up-down counter).
Please only consider the bits you use for direction prediction in your storage calculations. Also, assume that there are up to 512 bits for other incidentals such as history registers, etc.
Thank you for submitting your suggestions on what metric to use to judge which predictor is better. As many of you pointed out the real problem is how to decide whether a predictor A is better than predictor B when A performs better than B for some benchmarks while B performs better than A for others. Ultimately, it is performance that matters, but even then the same problem can appear. There were several well justified suggestions. I hope it's clear that there is no single metric that is perfect. To make forward progress we will be using the Average MPKI.
MPKI=Mispredictions per Kilo Instructions, that is how many mispredictions occur every 1000 instructions. This is loosely connect to performance. If we know that average CPI then we can roughly estimate performance with MPKI.
So, we will be using:
X = [ MPKI(1) + … + MPKI(N) ] / N
Where MPKI(i) is the MPKI for benchmark i.