CPSC 3300 - Fall 2014 - Project 2 - Branch Predictor Analysis
Due date: Wednesday, November 5, by midnight
Submission: handin.cs.clemson.edu
(three programs and one document)
Grading Weights: 30% each program with correct results
10% results table and graph
This is to be an individual or team of two assignment. If you work in
a team, I encourage you to use en.wikipedia.org/wiki/Pair_programming.
Write three programs to simulate the predicted branch direction, taken or
untaken, for three types of predictors. Note that you are not predicting
the branch target address, only the direction.
The first two programs should be parameterized to easily allow you to
gather statistics for a design parameter sweep across BHT/PHT sizes.
1) 2-bit saturating counter BHT, from 16 entries to 32768 entries, indexed
using a corresponding number of bits (from 4 to 15 bits) taken from the
least-significant bits in the instruction address
2) gshare with 2-bit saturating counter PHT, with the PHT from 16 entries
to 32768 entries, indexed by a BHSR of corresponding width (4-15 bits)
xor'ed with that number of bits taken from the least-significant bits
in the instruction address (remember that xor operation in C is ^)
3) SAs scheme somewhat similar to P6 BTB with 512 entries (i.e., a fixed
size, no parameter sweep), indexed using least-significant 9 bits in
the instruction address, each entry containing a 4-bit BHSR and a
16-entry PHT (note that the P6 BTB is actually a PAs scheme)
All 2-bit saturating counters should be initialized to zero, with the 0
and 1 states predicting untaken and the 2 and 3 states predicting taken.
For input, use the following trace file
http://www.cs.clemson.edu/~mark/server_trace_1_4M.txt.gz
This file contains four million records of branch address (in hexadecimal)
and taken/untaken (encoded as 1/0) from the first server trace file in the
championship branch prediction competition. (Calls and returns have been
removed; you are seeing conditional and unconditional branches, some of
which may be indirect. These are x86 traces, so the instruction addresses
are unaligned.)
The first twenty records can be displayed using
zcat server_trace_1_4M.txt.gz | head -20
and should display
0ffd7a66 0
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 1
0ffd7a78 0
0ffd769e 0
0ffd76a5 0
0ffd76ac 1
You will notice what appears to be a loop with a trip count of 16.
Please avoid uncompressing the file. Instead run your program with zcat
zcat server_trace_1_4M.txt.gz | ./a.out
For the 2-bit counter BHT, you should get the following statistics for
these three test cases (these are outside the range of the ones you will
turn in):
4 entries (2-bit index): mispredicts = 857737, rate = 21.44%
8 entries (3-bit index): mispredicts = 773926, rate = 19.35%
65536 entries (16-bit index): mispredicts = 179125, rate = 4.48%
For gshare, you should get:
4 entries (2-bit index): mispredicts = 951012, rate = 23.78%
8 entries (3-bit index): mispredicts = 857826, rate = 21.45%
65536 entries (16-bit index): mispredicts = 141862, rate = 3.55%
For SAs, you should get:
4 entries (2-bit index): mispredicts = 750812, rate = 18.77%
8 entries (3-bit index): mispredicts = 719630, rate = 17.99%
65536 entries (16-bit index): mispredicts = 125691, rate = 3.14%
Please turn in your three programs along with a single document (.docx or
.pdf) containing a table of missprediction rates and a graph of the two
result columns.
misprediction rates
size BHT gshare
16 ___ ____
32 ___ ____
64 ___ ____
128 ___ ____
256 ___ ____
512 ___ ____
1024 ___ ____
2048 ___ ____
4096 ___ ____
8192 ___ ____
16384 ___ ____
32768 ___ ____
512-entry SAs scheme ___
You may use whatever language you wish.