CPSC 330 - Spring 2013
Project 2 - Branch Predictor Analysis
Due on Monday, April 8
Grading Weights
30% each program with correct results
10% results table and graph
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 (4-15) 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.)
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 a printout of your three programs along with 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. If I have questions of concerns
with your submission, I may require you to turn in electronic copies of
your programs and/or ask you to personally demonstrate the compiling and
running of your programs.