Due: Nov 9 via the Catalyst dropbox
Questions about this assignment should go to the Discussion Board.
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:
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:
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
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 the state of the cache so that all lines
(including those of any victim buffer) are empty.
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.
MAX_* at the top of
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.
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
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
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.
Download the files you need for this assignment: hw3-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
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.