CS 105

Writing a Cache Memory Simulator

In this part of the assignment, you will write a cache simulator 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.

Reference Cache Simulator

Included in the starter code is a 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:

Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>
Options:
  -h         Print this help message.
  -v         Optional verbose flag.
  -s <num>   Number of set index bits.
  -E <num>   Number of lines per set.
  -b <num>   Number of block offset bits.
  -t <file>  Trace file.

Examples:
  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace
  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace

More Details

-v
Optional verbose flag displays trace information.
-s s
Number of set index bits (\( S = 2^s \) is the number of sets).
-E E
Associativity (number of lines per set).
-b b
Number of block bits (\( B = 2^b \) is the block size).
-t tracefile
Name of the valgrind trace to replay.

The command-line arguments are based on the notation (s, E, and b) discussed in class and on pages 615--617 of the CS:APP3e textbook (see especially Figure 6.26).

For example,

./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace
hits:4 misses:5 evictions:3

The same example in verbose mode:

./csim-ref -v -s 4 -E 1 -b 4 -t traces/yi.trace
L 10,1 miss
M 20,1 miss hit
L 22,1 hit
S 18,1 hit
L 110,1 miss eviction
L 210,1 miss eviction
M 12,1 miss eviction hit
hits:4 misses:5 evictions:3

Coding

Your job is to fill in the provided csim.c file, which starts out as

#include "cachelab.h"

int main()
{
    printSummary(0, 0, 0);
    return 0;
}

Your finished program will take the same command-line arguments as the provided reference simulator and produce identical output to it.

Rules

  • Include both partners' names and login IDs in the header comment in csim.c.

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

  • Your simulator must work correctly for arbitrary values of s, E, and b. You will need to allocate storage for your simulator's data structures using the malloc function. (Run man alloc for details.)

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

    printSummary(hit_count, miss_count, eviction_count);

Tips

  • Your cache simulator is only simulating performance with respect to hits, misses, and evictions, so each cache line does not need to store a block of data!

  • As mentioned in the rules, you should ignore all instruction cache accesses in the trace (lines starting with I).

    Remember that Valgrind always puts I in the first column (i.e., with no preceding space), and M, L, and S begin in the second column (i.e., with a preceding space). This format may help you parse the trace.

  • Each data load (L) or store (S) operation can cause at most one cache miss. The data-modify operation (M) is treated as a load followed by a store to the same address. Thus, an M operation can result in two cache hits, or a miss and a hit plus a possible eviction.

  • For this lab, you should assume that memory accesses are aligned properly, such that a single memory access never crosses block boundaries. By making this assumption, you can ignore the request sizes in the Valgrind traces.

  • We recommend that you use the getopt function to parse your command-line arguments.

    See man 3 getopt for details. (man getopt may give you the man page for the separate program used for shell scripts.)

    You will need to include the following header files:

    #include <getopt.h>
#include <stdlib.h>
#include <unistd.h>

  • The fscanf function will be useful for reading from the trace file. Since fscanf is complicated, concentrate on the %c, %Lx, and %d format options. Note that if you place a space character before %c, you can ignore Valgrind's habit of putting a blank before the L, S, and M characters.

  • Addresses in the trace files are 64-bit hexadecimal. If you use fscanf, the format specifier you should use is %llx.

  • Do your initial debugging on the smaller traces, such as traces/dave.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. You are not required to implement this feature in your csim.c code, but we strongly recommend that you do so because it will help you debug by allowing you to directly compare the behavior of your simulator with the reference simulator when you test with the reference trace files.

Testing

In addition to comparing the results of your program with those of the provided reference simulator on various trace files, we have also provided you with an autograding program, test-csim, that tests the correctness of your cache simulator on the reference traces.

(Don't forget to recompile your simulator before running the test!)

make
./test-csim
                        Your simulator     Reference simulator
Points (s,E,b)    Hits  Misses  Evicts    Hits  Misses  Evicts
     3 (1,1,1)       9       8       6       9       8       6  traces/yi2.trace
     3 (4,2,4)       4       5       2       4       5       2  traces/yi.trace
     3 (2,1,4)       2       3       1       2       3       1  traces/dave.trace
     3 (2,1,3)     167      71      67     167      71      67  traces/trans.trace
     3 (2,2,3)     201      37      29     201      37      29  traces/trans.trace
     3 (2,4,3)     212      26      10     212      26      10  traces/trans.trace
     3 (5,1,5)     231       7       0     231       7       0  traces/trans.trace
     6 (5,1,5)  265189   21775   21743  265189   21775   21743  traces/long.trace
    27

For each test, the autograder 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.

Grading and Evaluation

For this part of the assignment, we will run your cache simulator using a number of different cache parameters and traces. There are eight test cases, each worth 3 points, except for the last case, which is worth 6 points:

./csim -s 1 -E 1 -b 1 -t traces/yi2.trace
./csim -s 4 -E 2 -b 4 -t traces/yi.trace
./csim -s 2 -E 1 -b 4 -t traces/dave.trace
./csim -s 2 -E 1 -b 3 -t traces/trans.trace
./csim -s 2 -E 2 -b 3 -t traces/trans.trace
./csim -s 2 -E 4 -b 3 -t traces/trans.trace
./csim -s 5 -E 1 -b 5 -t traces/trans.trace
./csim -s 5 -E 1 -b 5 -t traces/long.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, printing 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. So if a particular test case is worth 3 points, and your simulator outputs the correct number of hits and misses, but reports the wrong number of evictions, then you will earn 2 points.

To Complete This Part of the Assignment

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)