CSE378 Spring 2010 Homework 3

Due May 21 at 5pm.

You may use two late days on this assignment.

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- and second-level caches of a rival chipmaker in order to ensure that his chip performs better. Dr. Signer knows that his rival's chips have a shared L1 and an L2 cache, and that these caches use the LRU replacement policy. In order to understand more about the caches, Dr. Signer wants to determine, for each of the caches:

the block size of the cache (in bytes)
the total size of the cache (in bytes)
the associativity of the cache

Assignment

Your 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:

access( address ) - queries the caches for the byte at the specified address.
Returns a tuple of boolean results for each level of the cache:
- ( True, True) if the access is a hit at both levels,
- (False, True) if the access missed in the L1 and hit in the L2,
- ( True, False) if the access hit in the L1 but missed in the L2, and
- (False, False) if the access missed at both levels.
Note that this call updates the caches: on a miss the block containing the requested address is brought into the cache, on a hit the LRU information is updated, etc.
reset() - reset the state of the caches so that all blocks are empty.

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

The cache size, the associativity, and the block size will always be powers of two. The size of the L2 cache will always be larger than the size of the L1. We will always test with an L1 and an L2.

The caches all use 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.

Restrictions

We 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 main() is filled in when main() returns it.

For reference, our solution added about 35 lines of Python to discoverCacheParams.py.

Additional information

We'll test your code by calling your main() with some two-level cache like in the sample tests and verifying that the values returned in the tuples match the parameters we used to create the cache. We expect the first tuple element to be the L1 value and the second element to be the L2 value. For instance, the call

print main( Cache.Cache( bsize=4, assoc=2, size=64,                                   
                         secondLevelCache=Cache.Cache( bsize=8, assoc=4, size=1024 )))

should generate output like

{'block sizes': (4, 8), 'associativities': (2, 4), 'cache sizes': (64, 1024)}

If Python is new to you, you may find it helpful to read and play with this example code: pythonDemo.py.

Files/Turnin

Download the Python files you need for this assignment.

You can run the code for this assignment with the command python discoverCacheParams.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 likely not work with the new semantics of Python 3.x.

You must fill in the missing function definitions in discoverCacheParams.py to infer the parameters of the mystery cache object provided to main(). You should submit your modified discoverCacheParams.py file via Catalyst. Please include your name at the top of this file in a comment.

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 CSE 378 TAs]