Cache

Assignment: Cache

• Policy: Individual / pair practice
• Code: cs240 start
• Submit: Upload a PDF written on the cs240-cache-worksheet.pdf submission sheet git commit and git push your completed code.
• Reference:
  • Memory Hierarchy, Cache

Contents

• Assignment: Cache
• Overview
  • Goals
  • Advice
• Paper Cache Exercises
  • Template and Submission
  • Exercises
• Automatic Cache Sleuth
  • Time Reports
  • Setup
  • Tasks
  • Cache Simulator
  • Designing and Testing Access Streams
  • Code Submission
• Grading
• License

Overview

This assignment has two parts.

1. 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.

2. 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.

Goals

• 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.

Advice

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

Template and Submission

Please write your answers on the cs240-cache-worksheet.pdf submission sheet to streamline the grading process. Submit your work by scanning a PDF of all worksheet pages (in order) and uploading it to Gradescope. Remember that this course uses your Gradescope account attached to your Wellesley email address (the variety that matches your username). You can merge accounts across multiple email addresses if helpful.

Exercises

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:

1. Homework Problem 6.26.
2. Homework Problem 6.29. (Note the book may show bits 0-12, which is an error – there are only bits 0-11.)
3. Homework Problem 6.34.
4. 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.

Time Reports

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.

Setup

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
• Cache64KB2Way16B.java, Cache32KB8Way8B.java, Cache16B4Way4B.java – three sample caches with known dimensions
• MysteryCacheA.class, MysteryCacheB.class, MysteryCacheC.class – three mystery caches with unknown dimensions
• SampleCache.java – a class you may extend to implement new caches for testing
• CacheSimImpl.class, CacheSimImpl$Set.class, CacheSimImpl$Slot.class - a cache simulator implementation

Compile the cache sleuth with javac CacheSleuth.java. Run the cache sleuth tests with java CacheSleuth.

Tasks

Implement the following methods in CacheSleuth:

/** 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 cache.

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 CacheSleuth.java.

Cache Simulator

Internally, the CacheSim simulator maintains an abstract representation of the status of its simulated cache. CacheSim has a single method, 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.

Assume that:

• 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.

Code Submission

Submit: The course staff will collect your work directly from your hosted repository. To submit your work:

1. Test your source code files one last time. Make sure that, at a minimum, submitted source code is free of syntax errors and any other static errors (such as static type errors or name/scope errors). In other words: the code does not need to complete the correct computation when invoked, but it must be a valid program. We will not grade files that do not pass this bar.

2. Make sure you have committed your latest changes. (Replace FILES with the files you changed and MESSAGE with your commit message.)

   $ git add FILES
   $ git commit -m "MESSAGE"

3. Run the command cs240 sign to sign your work and respond to any assignment survey questions.

   $ cs240 sign

4. Push your signature and your latest local commits to the hosted repository.

   $ git push

Confirm: All local changes have been submitted if the output of git status shows both:

• Your branch is up to date with 'origin/main', 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.

Grading

Your grade is derived as follows:

• Paper Cache Exercises
• Automatic Cache Sleuth:
  • 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.

License

Cache 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.