|
CSE Home | About Us | Search | Contact Info |
|
CSE378 Winter 2011 Homework 3Due Sunday March 6 at 11pm. No late solutions accepted, even if you have late days remaining.Dr. Chip D. Signer has been put in charge of designing a new chip for his employer. Dr. Signer wants to reverse engineer the first-level cache of a rival chipmaker in order to ensure that his chip performs better. Dr. Signer knows that his rival's chips L1 caches use the LRU replacement policy. In order to understand more about the cache, Dr. Signer wants to determine:
AssignmentYour assignment is to come up with an algorithm to determine the parameters of a a series of "mystery" caches. Each cache can be accessed only via the following interface:
reset() (see above).
The cache size, the associativity, and the block size will always be powers of two. The cache uses a strict LRU policy to replace blocks within sets. The constants MAX_* at the top of discoverCacheParams.py list the maximum values (inclusive) for various cache parameters, so your inference algorithm needn't check or handle values outside these ranges. The minimum value for each parameter should be obvious: it doesn't make sense to have 0 associativity, or a block size of 0 bytes, etc. Feel free to examine the cache implementation (Cache.py) to gain more insight into how caches work. RestrictionsWe will be looking over your source code, so don't cheat by using any interface to the cache other than the three functions specified above. You can of course change things to help debug, but your code will be tested against our version of Cache.py.We recommend following the given order of inferring parameters
(first block size, then cache size, then associativity) though you can
solve them in a different order if you wish. All that really matters
is that the dictionary returned by For reference, our solution added about 35 lines of Python to discoverCacheParams.py. Additional informationWe'll test your code by calling your main() with some L1 cache like in the sample tests and verifying that the values returned in the tuples match the parameters we used to create the cache.print main( Cache.Cache(bsize=4, assoc=2, size=64) )should generate output like {'block size': 4, 'associativity': 2, 'cache size': 64} If Python is new to you, you may find it helpful to read and play with this example code: pythonDemo.py. Files/TurninDownload the Python files you need for this assignment.You can run the code for this assignment with the command You must fill in the missing function definitions in
discoverCacheParams.py to infer the parameters of the mystery
cache object provided to You should ensure your code works for the different cache configurations provided in the comments at the bottom of discoverCacheParams.py. We will test your code on other cache configurations, however, so it's a good idea to come up with your own test cases as well. |
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to perkins] |