Cache Memory

Due: 5:00am, Monday November 18, 2024

Handout Instructions

Login to your university Unix account and copy the assignment code to a location under your home directory. The starter code for this assignment is on the Linux server here:

/export/home/public/schwesin/cpsc235/assignments/project4

Description

This project will help you understand the impact that cache memories can have on the performance of programs. You will write a program that simulates the behavior of a cache memory.

Reference Trace Files

The traces subdirectory of the handout directory contains a collection of trace files that we will use to evaluate the correctness of the cache simulator. 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 -l

on the command line runs the executable program “ls -l”, 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 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.

There is a reference implementation of the project in the reference subdirectory . called simulator-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 options:

    `-h`: Optional help flag that prints usage info

    `-v`: Optional verbose flag that displays trace info

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

    `-f <file>`: Name of the `valgrind` trace to replay

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

    ./reference/simulator-ref -s 4 -E 1 -b 4 -f traces/trace2.txt
    hits:4 misses:5 evictions:3

The same example in verbose mode:

    ./reference/simulator-ref -v -s 4 -E 1 -b 4 -f traces/trace2.txt
    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

There are two files: simulator.cpp and simulator.py have the command line parsing implemented. Your job is to complete either of these files to produce the same output as the reference implementation.

Programming Rules

Your program must compile/interpret without warnings in order to receive credit.
Your simulator must work correctly for arbitrary s, E, and b. This means that you will need to allocate storage for your simulator’s data structures at runtime.
For this project, we are interested only in data cache performance, so your simulator should ignore all instruction cache accesses (lines starting with “I”). Recall that valgrind always puts “I” in the first column (with no preceding space), and “M”, “L”, and “S” in the second column (with a preceding space). This may help you parse the trace.
For this this project, 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.

Evaluation of the Cache Simulator

We will run your cache simulator using different cache parameters and traces. There are eight test cases to consider, each worth 12 points:

    ./simulator -s 1 -E 1 -b 1 -f traces/trace1.txt
    ./simulator -s 4 -E 2 -b 4 -f traces/trace2.txt
    ./simulator -s 2 -E 1 -b 4 -f traces/trace3.txt
    ./simulator -s 2 -E 1 -b 3 -f traces/trace4.txt
    ./simulator -s 2 -E 2 -b 3 -f traces/trace4.txt
    ./simulator -s 2 -E 4 -b 3 -f traces/trace4.txt
    ./simulator -s 5 -E 1 -b 5 -f traces/trace4.txt

Note the eight test case is an additional trace that is not include in the assignment code. You can use the reference simulator simulator-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 12 points, and your simulator outputs the correct number of hits and misses, but reports the wrong number of evictions, then you will earn 8 points.

Working on the Cache Simulator

Here are some hints and suggestions:

Do your initial debugging on the small traces, such as traces/trace3.txt.
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 code, but we strongly recommend that you do so. It will help you debug by allowing you to directly compare the behavior of your simulator with the reference simulator on the reference trace files.
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.

Handin Instructions

The provided makefile has a target named submit. To submit your assignment execute the command

    make submit

This will copy the appropriate files to a protected directory owned by your instructor.

Grading Criteria

Your score will be computed out of a maximum of 100 points based on the following distribution:

96 Correctness points.

4 Programming style points.

Note: poor programming practices, such as using global variables, will result in a penalty to the grade.