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.