pencil Use performance impact to reveal cache dimensions.

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

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

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

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.

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…

## Code Submission

Before submitting, disable any diagnostic printing that you added.

1. Make sure you have committed your latest changes.

``````\$ git add ...
\$ git commit ...``````
2. Run the command `cs240 sign` to sign your work and respond to any assignment survey questions.

``\$ cs240 sign``
3. 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.

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