Due: April 19 via Canvas

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 in a Python file called branchpredictor.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 branchpredictor.py. You should submit your modified discover-bpred.py file via Canvas.

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 branchpredictor.py.

Feel free to change what you need to in discover-bpred.py, but please make sure that the discover() function returns a dictionary in the format indicated there (so our grading scripts will work). 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 the assignment here: hw1-mystery-branch-predictor.tar.gz.

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; it's easy to download and install. Be sure to install Python 2.x; this code will not work with the new syntax 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.

Turnin

You should submit your modified discover-bpred.py file to Canvas.

---

Thank you to Adrian Sampson who designed and created the first version of this assignment.