Understanding Cache Memories

Due: 11/16, 11:59PM

Logistics

This is an individual project. This lab must be completed on the machines in the Asprey Lab or the machines in SP 309. Any clarifications and revisions to the assignment will be posted to the class website.

Overview

For this lab you will complete a small C program that simulates the behavior of a cache memory.

Downloading the assignment

Start by downing the lab starter code from the class website and extract this tarfile to a directory in which you plan to do your work.

cd cs224
wget --no-check-certificate https://cs224.cs.vassar.edu/assignments/cachelab.tar
tar xvf cachelab.tar
cd cachelab

You will be doing all of your work inside this directory. You will be modifying the file: csim.c. To compile this file and build the simulator, type:

make

Description

For this lab you will implement a cache simulator.

Reference Trace Files

The traces subdirectory contains a collection of reference trace files that we will use to evaluate the correctness of the cache simulator you write. The memory traces have the following form:

R 0x00400000 4
R 0x00400004 4
R 0x00400008 4
R 0x0040000C 4
R 0x00400010 4
W 0x00400014 4
W 0x00400018 4
R 0x0040001C 4
R 0x00400020 4
W 0x00400024 4

Each line denotes a memory accesses. The format of each line is

operation address,size

The operation field denotes the type of memory access: R designates a memory read (load), and W designates a memory write (store), The address field specifies a 32-bit hexadecimal memory address. The size field secifies the number of bytes accessed by the operation.

Writing a Cache Simulator

You will write a cache simulator in csim.c that takes a memory trace as input, simulates the hit/miss behavior of a cache memory on this trace, and outputs the total number of hits, misses, and evictions.

We have provided you with the binary executable of a reference cache simulator, called csim-ref, that simulates the behavior of a cache with arbitrary size and associativity on a trace file. It uses the PLRU (pseudo least-recently used) replacement policy when choosing which cache line to evict.

Pseudo Least Recenty Used Replacement Policy

The Pseudo Least Recently Used (PLRU) cache replacement policy that uses one accessed bit per line is a simple approximation of true LRU. Each cache line in a set maintains a single bit indicating whether it has been accessed recently. When a line is referenced, its accessed bit is set to 1. When the cache needs to evict a line, it selects one whose accessed bit is 0, indicating it has not been used recently. If all bits in the set are 1, meaning every line was recently accessed, the policy resets all bits to 0 except for the one corresponding to the most recently accessed line, which remains 1. This approach reduces hardware complexity compared to true LRU while providing a reasonable approximation of recency-based replacement behavior.

Running the Reference Simulator

The reference simulator takes the following command-line arguments:

./csim-ref [-hv] -S <s> -E <E> -B <b> -t <tracefile>

• -h: Help flag that prints usage info
• -v: Verbose flag that displays trace info
• -S <s>: Number of sets in the cache
• -E: Associativity (number of lines per set)
• -B <b>: Number of bytes in the cache block
• -t <tracefile>: Name of the trace to replay

For example:

linux> 
hits:0 misses:8 evictions:7

Visualizing the Cache

The verbose -v flag, when set will show the contents of the cache after every memory update. This can be helpful to test to make sure your simulator is working properly.

The same example in verbose mode:

linux> ./csim-ref -v -S 2 -E 1 -B 4 -t traces/t1.trace
Cache Simulator:  Any key to advance, 'q' to quit.
Cache: Sets: 2, Lines/Set: 1, Last access: 0x800000

Set: 0
  Line: 0 | V:1 | L:0 | Tag:  100000
Set: 1
  Line: 0 | V:0 | L:0 | Tag:       0

Hits:0 | Misses:1 | Evictions:0

Your job is to fill in the csim.c file so that it takes the same command line arguments and produces the identical output as the reference simulator.

Programming Rules

• Your csim.c file must compile without warnings in order to receive credit.

• Your simulator must work correctly for arbitrary S, E, and B. This means that storage for your simulator’s data structures uses the malloc function. Type man malloc for information about this function. You can assume that S and B will always be a power of 2 (1, 2, 4, 8, etc.).

• When placing a line in the cache, if there is an empty line in the cache for a set, you should place it in the first free line. This is what the reference simulator does, and you should match this behavior to compare your cache to the reference simulator.

• For this lab, we are interested only in data cache performance, so your simulator does not actually read or write any cache data. That means we only care about the input address, not whether is is a R or W, or how many bytes the memory access is.

• To receive credit for this lab, you must call the function printSummary, with the total number of hits, misses, and evictions, at the end of your main function:

  printSummary(hit_count, miss_count, eviction_count);
  

  The starter code does this for you.

• For this this lab, you should assume that memory accesses are aligned properly, such that a single memory access never crosses block boundaries.

• You can not include any other files or libraries, though feel free to write any helper function you need.

• Do not change any of the variable names in any of the structs. The cache visualizer and the grading scripts uses these struct fields.

• The only function you need to edit is accessCache. Do not modify any other function. You may write as many helper functions as you need, however.

Hints

Here are some hints and suggestions for working on the lab:

• Do your initial debugging on the small traces, such as traces/t1.trace.
• The reference simulator takes an optional -v argument that enables verbose output, displaying the hits, misses, and evictions that occur as a result of each memory access as well as printing out the contents of the cache.
• Since you don’t know the size of your cache at compile time (as it depends on what options the user runs the program with) you must dynamically allocate any data structures you are using with the malloc() library call. We have implemented this for you, but it is a good idea to go over this code and make sure you understand how it works.
• One of the first tasks you will have to do it convert the number of blocks (B) and Sets (S), to the number of block offset bits and set index bits, respectively. You can assume that B and S will always be a power of two. To convert that number to the number of bits needed, think of what the underlying bit representation of that number (it will be a 1 followed by a number of zero). The number of zeros in that number is the number of bits you need to represent that number.

Evaluation

You can use the reference simulator csim-ref to obtain the correct answer for each of the traces. Try each trace under a variety of cache configurations. During debugging, use the -v option for a detailed record of each hit and miss. In addition to correctness, there will be 10 points awarded for style. Make sure you code is easy to understand and well documented.

For each test case, outputting the correct number of cache hits, misses and evictions will give you credit for that test case.

Submitting your work

Upload your csim.c to Gradescope.