Computer Laboratory

Course pages 2012–13

Advanced Computer Design Exercise - MIPS Branch Predictor

  • Make a personal copy of the /usr/groups/ecad-labs/ACS-ACD-1213/bluespec-examples/BERI directory.
  • Run the test.sh script in the BERI directory.

The test.sh script will:

  • Build the BERI processor.
  • Run a test routine including a bubble sort, a quick sort, a series of quick searches and a series of modulur exponentiations.
  • Run a perl script to analyse the log and produce a performance summary.

The test.sh script should produce the following output: 

Simulation Performance Report
 Each Quanta is 25k instructions.
 Format is Category : Hit Rate ( Total in Thousands )
Quanta  Branch Rate     Jump Rate       Jump Reg Rate   Issued/Retired  Cycles Per Instruction
1       86.348(2.55k)   99.268(0.82k)   99.389(0.82k)   1.086           cpi:1.302
2       85.927(2.95k)   99.147(0.70k)   87.055(0.70k)   1.122           cpi:1.287
3       92.134(2.62k)   99.655(0.87k)   80.552(0.87k)   1.091           cpi:1.288
4       79.710(2.82k)   99.195(0.87k)   78.276(0.87k)   1.184           cpi:1.343
5       92.901(2.58k)   100.000(0.91k)  79.956(0.91k)   1.088           cpi:1.292
6       80.771(5.39k)   99.317(0.29k)   96.587(0.29k)   1.252           cpi:1.385
7       80.888(5.59k)   100.000(0.24k)  100.000(0.24k)  1.256           cpi:1.373
8       69.691(3.30k)   98.693(1.38k)   46.076(1.38k)   1.422           cpi:1.770
9       60.941(2.68k)   99.186(1.72k)   41.720(1.72k)   1.495           cpi:1.900
CPI = 1.45690514677494  Branch Rate:0.807212705913237   Jump Rate:0.992825112107623     Jump Register Rate:0.693490517683239

As stated in the report header, the perl script reports on 9 time quanta, each containing 25,000 cycles. Flow control instructions are broken into 3 categories, branch instructions, jump instructions and jump register instructions, corrosponding to instructions of the same names in the MIPS spec.

The hit rate for each category of instruction is listed for each time quanta along with the total number of instructions of that category in that quanta.

The Issues/Retired column shows the number of instructions that were issued divided by the number that actually committed. This number should be 1.00, but will be greater if the branch unit causes the pipeline to execute instructions which were not needed.

The overall cycles per instruction is listed in the last column. The CPI should also be 1.00 in the ideal case but will be higher, not only because of branch miss-prediction but because of cache misses and multiplies (which are multi-cycle instructions).

The last line gives a summary for the entire test run.

The goal of this exercise will be to improve the performance of the branch predictor implemented in BranchSimple.bsv in the root of the BERI folder.

Goal and Strategy

The goal of this exercise will be to improve the performance of the branch predictor implemented in BranchSimple.bsv in the root of the BERI folder.

The comments in BranchSimple.bsv should be sufficient to understand the operation of the branch predictor well enough to perform optimisations.

The wikipedia article on branch prediction gives a number of approaches which should increase performance.

Enlarging the branch history table isn't likely to be effective in this case because the test size is quite small.

Assessment

Your work will pass when you can demonstrate a branch predictor with at least a hit-rate of .85 for branches and at least .70 for the jump register case.