Description
1 Logistics
You must run this lab on a 64-bit x86-64 machine.
2 Overview
This lab will help you understand the impact that cache memories can have on the performance of your C
programs.
The lab consists of two parts. In the first part you will write a small C program (about 200-300 lines) that
simulates the behavior of a cache memory. In the second part, you will optimize a small matrix transpose
function, with the goal of minimizing the number of cache misses.
3 Downloading the assignment
Please download the tarball from the course website as you have in past assignments.
Start by copying cachelab-handout.tar to a protected Linux directory in which you plan to do your
work. Then give the command
linux tar xvf cachelab-handout.tar
This will create a directory called cachelab-handout that contains a number of files. You will be
modifying two files: csim.c and trans.c. To compile these files, type:
linux make clean
linux make
1
WARNING: Do not let the Windows WinZip program open up your .tar file (many Web browsers are set
to do this automatically). Instead, save the file to your Linux directory and use the Linux tar program to
extract the files. In general, for this class you should NEVER use any platform other than Linux to modify
your files. Doing so can cause loss of data (and important work!).
4 Description
The lab has two parts. In Part A you will implement a cache simulator. In Part B you will write a matrix
transpose function that is optimized for cache performance.
4.1 Reference Trace Files
The traces subdirectory of the handout directory contains a collection of reference trace files that we will
use to evaluate the correctness of the cache simulator you write in Part A. The trace files are generated by a
Linux program called valgrind. For example, typing
linux 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.
4.2 Part A: Writing a Cache Simulator
In Part A 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.
2
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:
Usage: ./csim-ref [-hv] -s
