Understanding Cache Memories

Due: Sunday May 8th, 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 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 trace files are generated by a Linux program called valgrind. For example, typing

valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ls

on the command line runs the executable program ls, captures a trace of each of its memory accesses in the order they occur, and prints them on stdout.

valgrind memory traces have the following form:

I 0400d7d4,8
 M 0421c7f0,4
 L 04f6b868,8
 S 7ff0005c8,8

Each line denotes one or two memory accesses. The format of each line is

[space]operation address,size

The operation field denotes the type of memory access: I denotes an instruction load, L a data load, S a data store, and M a data modify (i.e., a data load followed by a data store). There is never a space before each I. There is always a space before each M, L, and S. The address field specifies a 64-bit hexadecimal memory address. The size field specifies the number of bytes accessed by the operation.

Writing a Cache Simulator

You will write a cache simulator in csim.c that takes a valgrind 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 valgrind trace file. It uses the LRU (least-recently used) replacement policy when choosing which cache line to evict.

The reference simulator takes the following command-line arguments:

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

The command-line arguments are based on the notation (s, E, and b) from page 617 of the CS:APP3e textbook. For example:

linux> ./csim-ref -s 2 -E 1 -b 4 -t traces/t2.trace
hits:4 misses:5 evictions:3

The same example in verbose mode:

linux> ./csim-ref -v -s 2 -E 1 -b 4 -t traces/t2.trace
L 10,1
Hits: 0, Misses: 1, Evictions: 0
S:0  L:0  V:0  T:0          LRU:0
S:1  L:0  V:1  T:0          LRU:1
S:2  L:0  V:0  T:0          LRU:0
S:3  L:0  V:0  T:0          LRU:0
M 20,1
Hits: 1, Misses: 2, Evictions: 0
S:0  L:0  V:0  T:0          LRU:0
S:1  L:0  V:1  T:0          LRU:1
S:2  L:0  V:1  T:0          LRU:2
S:3  L:0  V:0  T:0          LRU:0
L 22,1
Hits: 2, Misses: 2, Evictions: 0
S:0  L:0  V:0  T:0          LRU:0
S:1  L:0  V:1  T:0          LRU:1
S:2  L:0  V:1  T:0          LRU:3
S:3  L:0  V:0  T:0          LRU:0
S 18,1
Hits: 3, Misses: 2, Evictions: 0
S:0  L:0  V:0  T:0          LRU:0
S:1  L:0  V:1  T:0          LRU:4
S:2  L:0  V:1  T:0          LRU:3
S:3  L:0  V:0  T:0          LRU:0
L 110,1
Hits: 3, Misses: 3, Evictions: 1
S:0  L:0  V:0  T:0          LRU:0
S:1  L:0  V:1  T:4          LRU:5
S:2  L:0  V:1  T:0          LRU:3
S:3  L:0  V:0  T:0          LRU:0
L 210,1
Hits: 3, Misses: 4, Evictions: 2
S:0  L:0  V:0  T:0          LRU:0
S:1  L:0  V:1  T:8          LRU:6
S:2  L:0  V:1  T:0          LRU:3
S:3  L:0  V:0  T:0          LRU:0
M 12,1
Hits: 4, Misses: 5, Evictions: 3
S:0  L:0  V:0  T:0          LRU:0
S:1  L:0  V:1  T:0          LRU:7
S:2  L:0  V:1  T:0          LRU:3
S:3  L:0  V:0  T:0          LRU:0
hits:4 misses:5 evictions:3

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

Evaluation

This section describes how your work will be evaluated. The full score for this lab is 100 points:

Evaluation for Correctness

We will run your cache simulator using different cache parameters and traces. There are eight test cases, each worth 9 points, except for the last case, which is worth 18 points:

linux> ./csim -s 2 -E 1 -b 4 -t traces/t1.trace
linux> ./csim -s 4 -E 2 -b 4 -t traces/t2.trace
linux> ./csim -s 1 -E 1 -b 1 -t traces/t3.trace
linux> ./csim -s 2 -E 1 -b 3 -t traces/t4.trace
linux> ./csim -s 2 -E 2 -b 3 -t traces/t4.trace
linux> ./csim -s 2 -E 4 -b 3 -t traces/t4.trace
linux> ./csim -s 5 -E 1 -b 5 -t traces/t4.trace
linux> ./csim -s 5 -E 1 -b 5 -t traces/t5.trace

You can use the reference simulator csim-ref to obtain the correct answer for each of these test cases. During debugging, use the -v option for a detailed record of each hit and miss.

For each test case, outputting the correct number of cache hits, misses and evictions will give you full credit for that test case. Each of your reported number of hits, misses and evictions is worth 1/3 of the credit for that test case. That is, if a particular test case is worth 9 points, and your simulator outputs the correct number of hits and misses, but reports the wrong number of evictions, then you will earn 6 points.

Implementation of printCache

In addition to correctness, there are 10 points for implementing a printCache function. This function prints out the entire contents of your cache. This can be very helpful when you are trying to debug your code. It is invoked when you run the simulator with the -v option.

Evaluation for Style

There are 9 points for coding style. These will be assigned manually by me. I am looking for code that is well documented with comments and easy to understand.

Working on the Lab

We have provided you with an autograding program, called test-csim, that tests the correctness of your cache simulator on the reference traces. Be sure to compile your simulator before running the test:

linux> make
linux> ./test-csim
                        Your simulator     Reference simulator
Points (s,E,b)    Hits  Misses  Evicts    Hits  Misses  Evicts
     0 (2,1,4)       0       0       0       2       3       1  traces/t1.trace
     0 (4,2,4)       0       0       0       4       5       2  traces/t2.trace
     0 (1,1,1)       0       0       0       9       8       6  traces/t3.trace
     0 (2,1,3)       0       0       0     167      71      67  traces/t4.trace
     0 (2,2,3)       0       0       0     201      37      29  traces/t4.trace
     0 (2,4,3)       0       0       0     212      26      10  traces/t4.trace
     3 (5,1,5)       0       0       0     231       7       0  traces/t4.trace
     0 (5,1,5)       0       0       0  265189   21775   21743  traces/t5.trace
     3

TEST_CSIM_RESULTS=3

For each test, it shows the number of points you earned, the cache parameters, the input trace file, and a comparison of the results from your simulator and the reference simulator.

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

Submitting your work

Upload your csim.c to Gradescope.