Homework 1: Mystery Branch Predictors

Questions about this assignment should go to Brandon (blucia0a@cs).

Background

Dr. Chip D. Signer has been put in charge of designing a new chip for his employer. Dr. Signer wants to reverse engineer the branch predictor of a rival chipmaker in order to ensure that his chip performs better. All Dr. Signer knows is that the rival's chip uses a correlating (2-level) branch predictor that uses global history. In order to understand more about the branch predictor, Dr. Signer wants to determine:

the number of entries in the branch history register (BHR)

the number of bits used for the saturating counters in the branch history table (BHT)

the number of entries in the branch history table (BHT)

Assignment

Your assignment is to come up with an algorithm to determine the parameters of a a series of "mystery" branch predictors. Conveniently, these mystery predictors are provided as the Python modules MysteryBranchPredictor*.py. Each branch predictor can be accessed via the following interface:

predict( pc ) - ask the branch predictor to predict the direction of a branch at the specified PC. Returns True if the branch is predicted taken, False if not taken. Note that calls to predict() do not update the predictor's internal state.

actual( pc, direction ) - updates the branch predictor's state with the outcome of a branch at the specified PC going in the specified direction (True means taken, False means not taken). This method does not return anything.

reset() - reset the state of the branch predictor. All entries in the

BHR are reset to not taken. Each saturating counter in the BHT is set to a value such that it currently reads not taken, but with 1 increment will read "taken".

The initial state of the branch predictor is the same as after a call to reset() (see above).

The constants MAX_* in discover-bpred.py list the maximum values (inclusive) for various branch predictor parameters, so your inference algorithm needn't check or handle values outside these ranges. The minimum value for each parameter is 1.

The indexing function for the BHT uses the bits of the BHR concatenated with the bits from the PC in the following manner: {BHR bits}{PC bits}, i.e. the PC bits are the low-order bits.

You must fill in the missing function definitions in discover-bpred.py to infer the parameters of the branch predictors implemented by MysteryBranchPredictor*.py. You should submit your modified discover-bpred.py file via Catalyst.

Restrictions

We will be looking over your source code, so don't cheat by using any interface to the branch predictor other than the two functions specified above. You can of course change things to help debug, but your code will be tested against our versions of MysteryBranchPredictor*.py.

The formatting of the output of discover-bpred.py should be kept intact so our grading scripts will work, though you can otherwise change the code to your heart's content. We recommend following the given order of inferring parameters (first BHR size, then saturating counter size, then BHT entries) though you can solve them in a different order if you wish.

Files

Download the Python files you need for this assignment.

You can run the code for this assignment with the command python discover-bpred.py in your Windows, Mac or Linux command terminal. You may need to install Python first, go here to download it. Be sure to install Python 2.x; this code will not work with the new integer-division rules of Python 3.x.

You should ensure your code works for the included mystery branch predictors. We will test your code against other mystery branch predictors, too, so feel free to come up with other test cases yourself.


	Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to blucia0a]