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 first-level caches of a rival chipmaker in order to ensure that his chip performs better. Dr. Signer knows that his rival's caches use the LRU replacement policy, and that some of the caches have a victim buffer (or victim cache, i.e. not a miss cache). In order to understand more about the caches, Dr. Signer wants to determine:

• the block size of the cache (in bytes)
• the total size of the cache (in bytes)
• the associativity of the cache
• the size of the victim buffer (when there is one)

Assignment

Your assignment is to come up with an algorithm to determine the parameters of a series of "mystery" caches. Each cache can be accessed only via the following interface:

• access(address): queries the cache for the byte at the specified address. Returns True if the access is a hit and False for a miss. If a victim buffer is present, True indicates a hit in the cache or the victim buffer; False means the access missed in both. Note that this call updates the cache: on a miss the block containing the requested address is brought into the cache, on a hit the LRU information is updated, the victim buffer (if present) may be updated, etc.

• reset(): reset the state of the cache so that all lines (including those of any victim buffer) are empty.

• has_victim_buffer(): returns True if the cache has a victim buffer and False otherwise. The skeleton code we'll give you uses this, so you shouldn't really need it otherwise.

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

The caches all use a strict LRU policy to manage both lines within sets and entries in the victim buffer. Block sizes are the same for the cache and the victim buffer.

We won't test your code on extremely onerous corner cases, such as fully-associative caches with a victim buffer, or caches where the size of the victim buffer is equal to or larger than the cache itself.

Feel free to examine the cache implementation (caches.py) to gain more insight into how caches work.

The cache size (which does not count the size of the victim buffer), the associativity, and the block size will always be powers of two. The victim buffer size may not always be a power of two, however.

The constants MAX_* at the top of discover_cache_params.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.

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

We recommend following the given order of inferring parameters (first block size, then cache size, then associativity/victim buffer size) 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 50 lines of Python to discover_cache_params.py, and about half of those were for inferring victim buffer size.

Files

Download the files you need for this assignment: hw4-mystery-caches.tar.gz

You can run the code for this assignment with the command python discover_cache_params.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 must fill in the missing function definitions in discover_cache_params.py to infer the parameters of the mystery cache object provided to main().

Turnin

You should submit your modified discover_cache_params.py file to the Catalyst dropbox.

You should ensure your code works for the different cache configurations provided in the comments at the bottom of discover_cache_params.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.

---

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