- Assign: Friday, 19 April
- Due: 11:59pm Tuesday, 23 April
- Policy: Individual / pair graded synthesis assignment
cs240 start cache
A neat paper copy of the cs240-cache-worksheet.pdf submission sheet
cs240 sign, and
git pushyour completed code.
- Paper Cache Exercises
- Automatic Cache Sleuth
This assignment has two parts.
You will complete a set of paper cache exercises to illustrate several aspects of cache geometry and its interaction with memory access patterns. This part follows the individual team policy.
You will use a cache simulator and attempt to automatically discover the dimensions of mystery caches based only on observations of cache hits and misses for a stream of memory accesses. This removes the “noise” of real-world performance measurement and lets you inspect cache behavior directly to make decisions.
You will start (and could finish) this task as a lab activity. This part follows the pair team policy. Complete it with your lab partner.
- To become familiar with cache geometry and the ways in which cache block size, capacity, and associativity affect cache behavior.
- Understand how access patterns interact with caches and affect performance, based on geometry.
- To practice reverse engineering a system through simulated performance behavior.
- To cache in on egregious pun opportunities.
Construct your desired access patterns concretely using pencil and paper before you start coding. Once you have a good grasp on what pattern you are trying to produce, writing code to produce it of course much easier and less error-prone!
Paper Cache Exercises
Please write your answers on the cs240-cache-worksheet.pdf submission sheet to streamline the grading process.
This part follows the individual team policy. Prepare and submit your own individual paper solutions to the following problems from the CSAPP (3rd edition) textbook. A copy of the text is available in the microfocus.
Practice Problems 6.13 - 6.21 are great practice. (Do not submit solutions to the practice problems. You can find their solutions at the end of the chapter.)
Submit solutions for the following problems:
- Homework Problem 6.26.
- Homework Problem 6.29. (Note the book may show bits 0-12, which is an error – there are only bits 0-11.)
- Homework Problem 6.34.
- Homework Problem 6.36.
Automatic Cache Sleuth
This part follows the pair team policy. Complete the Cache Sleuth from lab this week with your lab partner.
According to self-reported times on this (code) part of the assignment from Fall 2018:
- 25% of students spent <= 1.5 hours.
- 50% of students spent <= 2 hours.
- 75% of students spent <= 3 hours.
Your Gumshoe Cache Sleuth Kit contains the following files:
CacheSleuth.java– a template for a cache sleuth that you will implement to automatically discover dimensions of a simulated cache
CacheSim.java– an interface describing the visible functionality of the simulated cache
Cache16B4Way4B.java– three sample caches with known dimensions
MysteryCacheC.class– three mystery caches with unknown dimensions
SampleCache.java– a class you may extend to implement new caches for testing
CacheSimImpl$Slot.class- a cache simulator implementation
Compile the cache sleuth with
javac CacheSleuth.java. Run
the cache sleuth tests with
Implement the following methods in
/** Determine the line (block) size of the cache in bytes. */ int getLineSize(CacheSim c); /** Determine the total capacity of the cache in bytes. */ int getCapacity(CacheSim c, int lineSize); /** Determine the associativity of the cache (in ways). */ int getAssociatvity(CacheSim c, int capacity);
Each of these methods takes a simulated cache (an object of type
CacheSim) and should determine a dimension of that cache by issuing
a series of memory accesses and inspecting whether they hit or miss in
The provided test harness includes three known caches and three
mystery caches. Use your completed
CacheSleuth implementation to
determine the dimensions of mystery caches A, B, and C. Write the
dimensions in a comment at the top of
CacheSim simulator maintains an abstract
representation of the status of its simulated cache.
CacheSim has a
boolean access(int address), which simulates an
access to an
address (represented as an
int) based on the current
simulated cache state, including updating that state in response to
the access. The return value is
true if the access hit in the
simulated cache and
false if it missed.
- All caches use a true LRU (least recently used) replacement policy.
- All caches are empty (cold) to start.
- There is only one level of cache.
Designing and Testing Access Streams
Think carefully about the puzzles we have considered, the locality examples we ran in class, as well as the results of our previous hardware cache performance experiments. Determine whether any patterns can be generalized and applied to the simulated caches given here. Do some pencil + paper design and think through the sleuth problems before writing code.
The provided tests will apply your sleuth to the three provided caches with known dimensions and the three provided mystery caches.
Watch the units!
Take careful note of the units used in the specifications of the sleuth methods as well as the test output. If you think your answers seem off by about 1000 (say, 1024?), check for a K in the output…
Before submitting, disable any diagnostic printing that you added.
Submit: The course staff will collect your work directly from your hosted repository as of the deadline. To submit your work:
Make sure you have committed your latest changes.
$ git add ... $ git commit ...
Run the command
cs240 signto sign your work and respond to any assignment survey questions.
$ cs240 sign
Push your signature and your latest local commits to the hosted repository.
$ git push
Confirm: After pushing, all local changes have been submitted if the output of
git status shows both:
Your branch is up to date with 'origin/master', meaning all local commits have been pushed
nothing to commit, meaning all local changes have been committed
Resubmit: If you realize you need to change something later, just repeat this process.
Your grade is derived as follows:
- Paper Cache Exercises (30 points)
- Automatic Cache Sleuth (30 points):
- Functional Correctness:
- When called on the provided Mystery Caches A, B, and C, as well as additional caches not provided to you, your three reverse engineering methods must correctly reveal the cache dimensions.
- Design, style, and documentation:
- Your code must be clean, easily readable, and documented with comments describing how your approach to each dimension works.
- Functional Correctness:
Cache Divination by Benjamin P. Wood at Wellesley College is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Source code and evaluation infrastructure for the Cache Sleuth are available upon request for reuse by instructors in other courses or institutions. The Cache Sleuth is inspired by a similar assignment in UW CSE 351.