Retro prof in the lab University of Washington Computer Science & Engineering
 CSE 378 Winter 2011
  CSE Home   About Us    Search    Contact Info 

 Academic Misconduct
 Homework 0
 Homework 1
   (strcmp.s) (atoi.s)
 Homework 2
 Homework 3
 Homework 4 Due 3/12
 Lab 1 SW + HW Due 1/21
 Lab 2 SW + HW Due 2/4
 Lab 3 SW Due 2/22
 Lab 4 SW + HW Due 3/11
 Lab Wiki
 Lab Info
 Green Sheet (PDF)
 Green Sheet Magic
 MIPS Resources
 Discussion Board
 Mail List Archives

CSE378 Winter 2011 Homework 3

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

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


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 boolean result for the cache:

    • True if the access is a hit,
    • False if the access missed.

    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, etc.

  • reset() - reset the state of the cache so that all blocks are empty and invalid.
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 cache uses a strict LRU policy to replace blocks within sets.

The constants MAX_* at the top of 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 ( to gain more insight into how caches work.


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) 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

Additional information

We'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:


Download the Python files you need for this assignment.

You can run the code for this assignment with the command python 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 to infer the parameters of the mystery cache object provided to main(). You should submit your modified 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 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.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to perkins]