|
CSE Home | About Us | Search | Contact Info |
|
Homework 1: Mystery Branch PredictorsDue: February 11, 2011 via Catalyst Questions about this assignment should go to Adrian the TA (asampson@cs). BackgroundDr. 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:
AssignmentYour 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:
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 Catalyst. RestrictionsWe 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. FilesDownload 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; 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. |
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX |