2020/4/18 GitHub - prannoy/CSE240A: Initial framework source code for CSE240A branch predictor project
https://github.com/prannoy/CSE240A 1/6
Initial framework source code for CSE240A branch predictor project
This branch is 4 commits ahead, 1 commit behind skinzer:master. Pull request Compare
src Added verbose flag 3 years ago
traces Added more traces 3 years ago
.gitignore Added verbose flag 3 years ago
README.md Update README.md 6 months ago
README.txt Minor 3 years ago
README.md
CSE240A Branch Predictor Project
Table of Contents
Introduction
Code Integrity
Get started
Working with Docker
Traces
Running your predictor
Implementing the predictors
Gshare
Tournament
Custom
Things to note
Grading
Grading the custom predictor
Turn-in Instructions
forked from skinzer/CSE240A
prannoy / CSE240A
Join GitHub today
GitHub is home to over 40 million developers working together to host
and review code, manage projects, and build software together.
Dismiss
Sign up
15 commits 1 branch 0 packages 0 releases 3 contributors
master Branch: New pull request Find file Clone or download
Update README.md Latest commit bc62a71 on 17 Oct 2019prannoy …
2020/4/18 GitHub - prannoy/CSE240A: Initial framework source code for CSE240A branch predictor project
https://github.com/prannoy/CSE240A 2/6
Introduction
As we’ve discussed in class, branch prediction is critical to performance in modern processors. An accurate branch predictor
ensures that the front-end of the machine is capable of feeding the back-end with correct-path instructions. Beyond its criticality
in processor execution, branch prediction is an interesting problem. How do you make accurate predictions on little data using
small, fast hardware structures.
For this Project you will be implementing various branch predictors in a simulated environment. We have provided a starting
framework to help you design your predictors. The framework (main.c) will perform all of the command-line switches as well as
the reading in of the trace files. You will implement your predictors by completing all of the TODOs in the predictor.c file. Note
that this is the only file in which you are able to make changes, as it will be the only file of yours we use for grading.
Code Integrity
Please make sure you do not copy a single line of code from any source. Not from other students, not from the web, not from
anywhere. We have very sophisticated tools to discover if you did. This is a graduate class and we have the very highest
expectations for integrity. You should expect that if you do so, even in very small amounts, you will be caught, you will be asked
to leave the program, and if an international student, required to leave the country.
Get Started
As mentioned, we provide a starting framework to help you design your predictors. The source code (including some traces for
testing) is in github and you can get it with git clone https://github.com/prannoy/CSE240A.git .
Alternatively, you can download it from our github page.
You have the option to write your project in C, C++ or Python. We only provide a framework written in C and we strongly
recommend you use it, primarily to ensure compatibility with our autograder.
If you decide to use some of the other supported languages, you will have to implement everything. You also have to make sure
that running make in the src directory generates an executable named 'predictor'. During grading, our script will run a make
clean , followed by a make command. Make sure that this step is not going to delete your code, especially if you are writing it in
Python. Finally, make sure that your project runs with the exact same commands as this document describes. Python submissions
must run with ./predictor , without requiring python ./predictor . You can submit a custom Makefile to serve the needs of your
code.
Working with Docker
Your projects will be graded using gradescope and an automatic grader based on Docker. The compiler used by the autograder is
gcc-5.4, and runs Ubuntu 16.04. You should be able to develop this project on your own machines, but in case you want to ensure
compatibility with our autograder, we provide a Docker image with the same configuration.
You will first have to install Docker (for simplicity consider Docker a very lightweight VM) on your machine (or in a VM), following
the instructions found here. Once installed, you can pull our image by opening a shell (for Windows machines, powershell seems
to work better than the cmd prompt) and typing:
docker pull prodromou87/ucsd_cse240a
This command will download and build our docker image. It will take a while, but you only have to do this step once. To verify
that you have the image, you can run docker images and check the the image is listed.
Once you have it, you can start an interactive shell in Docker with
docker run --rm -it prodromou87/ucsd_cse240a
The --rm flag will delete the running container once
2020/4/18 GitHub - prannoy/CSE240A: Initial framework source code for CSE240A branch predictor project
https://github.com/prannoy/CSE240A 3/6
you exit it so it doesn't keep consuming resources
from the host machine.
The -it flag will start an interactive session so it's
necessary if you want a shell to work with.
For development purposes, you will want to mount the project directory in Docker so you can see your code, compile and run it.
To do that, you change the previous instruction slightly:
docker run --rm -it -v /path/to/project/directory:/path/
to/mount/point prodromou87/ucsd_cse240a
Windows users will have to write the path as follows (No-
tice the lowercase 'c'):
docker run --rm -it -v //c/path/to/project/directory:/path
/to/mount/point prodromou87/ucsd_cse240a
If necessary, you can mount more directories with multiple -v flags. Once you get a shell, you can confirm the folder has been
mounted with ls /path/to/mount/point . You can now compile and run your project following the instructions provided in this
document. You can also modify the code on your host machine using your preferred editor and only switch to docker for
compiling/running. You don't need to restart docker every time since changes in the mounted directory will immediately be
visible in Docker.
Traces
These predictors will make predictions based on traces of real programs. Each line in the trace file contains the address of a
branch in hex as well as its outcome (Not Taken = 0, Taken = 1):
Sample Trace from int_1:
0x40d7f9 0
0x40d81e 1
0x40d7f9 1
0x40d81e 0
We provide test traces to you to aid in testing your project but we strongly suggest that you create your own custom traces to
use for debugging.
Running your predictor
In order to build your predictor you simply need to run make in the src/ directory of the project. You can then run the program
on an uncompressed trace as follows:
./predictor
[
]
If no trace file is provided then the predictor will read in input from STDIN. Some of the traces we provided are rather large when
uncompressed so we have distributed them compressed with bzip2 (included in the Docker image). If you want to run your
predictor on a compressed trace, then you can do so by doing the following:
bunzip2 -kc trace.bz2 | ./predictor
In either case the
that can be used to change the type of predictor being run are as follows:
--help Print usage message
--verbose Outputs all predictions made by your
mechanism. Will be used for correctness
grading.
2020/4/18 GitHub - prannoy/CSE240A: Initial framework source code for CSE240A branch predictor project
https://github.com/prannoy/CSE240A 4/6
-- Branch prediction scheme. Available
types are:
static
gshare:<# ghistory>
tournament:<# ghistory>:<# lhistory>:<# index>
custom
An example of running a gshare predictor with 10 bits of history would be:
bunzip2 -kc ../traces/int1_bz2 | ./predictor --gshare:10
Implementing the predictors
There are 3 methods which need to be implemented in the predictor.c file. They are: init_predictor, make_prediction, and
train_predictor.
void init_predictor();
This will be run before any predictions are made. This is where you will initialize any data structures or values you need for a
particular branch predictor 'bpType'. All switches will be set prior to this function being called.
uint8_t make_prediction(uint32_t pc);
You will be given the PC of a branch and are required to make a prediction of TAKEN or NOTTAKEN which will then be checked
back in the main execution loop. You may want to break up the implementation of each type of branch predictor into separate
functions to improve readability.
void train_predictor(uint32_t pc, uint8_t outcome);
Once a prediction is made a call to train_predictor will be made so that you can update any relevant data structures based on the
true outcome of the branch. You may want to break up the implementation of each type of branch predictor into separate
functions to improve readability.
Gshare
Configuration:
ghistoryBits // Indicates the length of Global History kept
The Gshare predictor is characterized by XORing the global history register with the lower bits (same length as the global history)
of the branch's address. This XORed value is then used to index into a 1D BHT of 2-bit predictors.
Tournament
Configuration:
ghistoryBits // Indicates the length of Global History kept
lhistoryBits // Indicates the length of Local History kept in the PHT
pcIndexBits // Indicates the number of bits used to index the PHT
You will be implementing the Tournament Predictor popularized by the Alpha 21264. The difference between the Alpha 21264's
predictor and the one you will be implementing is that all of the underlying counters in yours will be 2-bit predictors. You should
NOT use a 3-bit counter as used in one of the structure of the Alpha 21264's predictor. See the Alpha 21264 paper for more
information on the general structure of this predictor. The 'ghistoryBits' will be used to size the global and choice predictors while
the 'lhistoryBits' and 'pcIndexBits' will be used to size the local predictor.
Custom
2020/4/18 GitHub - prannoy/CSE240A: Initial framework source code for CSE240A branch predictor project
https://github.com/prannoy/CSE240A 5/6
Now that you have implemented 3 other predictors with rigid requirements, you now have the opportunity to be creative and
design your own predictor. The only requirement is that the total size of your custom predictor must not exceed (64K + 256) bits
(not bytes) of stored data and that your custom predictor must outperform both the Gshare and Tournament predictors (details
below).
Things to note
All history should be initialized to NOTTAKEN. History registers should be updated by shifting in new history to the least
significant bit position.
Ex. 4 bits of history, outcome of next branch is NT
T NT T NT << NT
Result: NT T NT NT
All 2-bit predictors should be initialized to WN (Weakly Not Taken).
They should also have the following state transitions:
NT NT NT
-----> -----> ----->
ST WT WN SN
<----- <----- <-----
T T T
The Choice Predictor used to select which predictor to use in the Alpha 21264 Tournament predictor should be initialized to
Weakly select the Global Predictor.
Grading
All grading will be done with respect to your predictor's Misprediciton Rate, as well as its correctness (for Gshare and
Tournament) compared to our implementation.
You get 10 points for correctness of the gshare and tournament predictors (20 points max grade for correctness). If your
predictions match the correct output, you get full points. You get 15 points if your custom predictor beats one of the other two
(gshare and tournament), and +15 points (30 total) if you beat both of them.
Finally, the 6 best custom predictors (in terms of misprediction rate), will receive extra points. First place gets 6 points, second
place gets 5, third gets 4 and so on. The maximum grade is 56. If your custom predictor does not rank in the top 6, the
maximum score you can get is 50/56.
If you are ranked in the top 6, we need a clear description (in comments in your code) of the number of bits you are using. For
example, write something like: I implemented [X] as my custom predictor. [Brief description of how it works]. This predictor uses
two structures. The first one is [variable name in code] and the second is [variable name]. Then for each structure present the
math to calculate its size. We will verify its correctness before you receive the bonus points. Adjust the above text as necessary.
You should do most of your development on your own machine. If you face any issues when you submit your project in
gradescope, try to run your project in our Docker image to ensure compatibility with the autograder, or post the error message in
Piazza.
Grading the custom predictor
We will be comparing your custom predictor against a Gshare predictor with 13 bits of global history (--global:13), which is the
largest possible Gshare that fits the 16kb budget. We will also be comparing it against a Tournament predictor of about 14kb.
This predictor uses 9 bits of global history, 10 bits of local history and 10 PC bits (--tournamet:9:10:10). These are the two
predictors you have to outperform.
2020/4/18 GitHub - prannoy/CSE240A: Initial framework source code for CSE240A branch predictor project
https://github.com/prannoy/CSE240A 6/6
For each predictor (gshare:13, tournament:9:10:10 and your custom predictor), we will calculate the average missprediction rate
accross all 12 of our traces. Out of those 12, six are visible to you and provided along with the starter code to use during
development. The remaining six will remain hidden. Your predictor's average missprediction rate must be better (lower) than the
other two to get all the points (minus the bonus points for top ranked predictors).
Turn-in instructions
DUE: Nov 12 2019 - Submissions after 11:59:59 PM are considered late
A project is considered late at 12:00:01 AM (Which is 1 second past Midnight).
To submit your project, compress the 'src' folder in a .zip (not .rar) file and upload it in gradescope. Select only the source files
required for compilation and nothing else (binaries, traces etc should not be submitted). This will trigger our autograder to begin
grading. You are allowed to submit multiple times.
Gradescope has a time limit for autograders. Make sure that your code does not do anything unnecessary. For comparison
purposes, we will announce our implementation's running time as soon as we optimize it.
Our autograder runs two sets of tests:
We first ensure that your code is compatible with our autograder. If your code fails any of these tests, you will be notified
immediately, so don't leave the screen before you see the grading outcome. Specifically, this set of tests checks that:
make produces an executable named predictor
The output produced by your executable has the expected format
Once you pass the compatibility test, we grade the output produced by your code. You will be able to see your score on some of
our test cases, but some will be hidden. Your overall grade will not be visible until after the project's due date.
Note: Gradescope expects pass/fail tests but we will be reporting percentages. If you don't score 100%, Gradescope considers it a
failed tests. Do not be concerned when you see failed tests (but be concerned if your score is low and re-submit)