Course pages 2015–16
Advanced Computer Design
Exercise 5 - MIPS Branch Predictor
- Make a personal copy of the /usr/groups/ecad-labs/ACS-ACD/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.