CS211 Summer 2020
Assignment 3 – Cache Simulator
The goal of this assignment is to help you understand caches better. You are required to write
a cache simulator using the C programming language.
2. Memory Access Traces
The input to the cache simulator is a memory access trace, which we have generated by
executing real programs. The trace contains memory addresses accessed during program
execution. Your cache simulator will have to use these addresses to determine if the access is
a hit or a miss, and the actions to perform in each case. The memory trace file consists of
multiple lines. Each line of the trace file corresponds to a memory accesses performed by the
program. Each line consists of two columns, which are space separated. The second column
reports 48-bit memory address that has been accessed by the program while the first column
indicates whether the memory access is a read (R) or a write (W). The trace file always ends
with a #eof string. We have provided you three input trace files (some of them are larger in
size). You can safely assume the trace files always have proper format. Here is a sample trace
3. Cache Simulator
You will implement a cache simulator to evaluate different configurations of caches. Your
program should be able to support traces with any number of lines. The followings are the
requirements for your cache simulator:
• You simulate one level cache.
• The cache size, associativity, the replacement policy, and the block size are the input
parameters. Cache size and block size are specified in bytes.
• Replacement algorithm: First In First Out (FIFO). When a block needs to be replaced,
the cache evicts the block that was accessed first. It does not take into account whether
the block is frequently or recently accessed.
• You have to simulate a write through cache.
4. Cache Simulator Interface
You have to name your cache simulator first. Your program should support the following usage interface: ./first <cache size><block size><cache policy><associativity><trace file>
A) <cache size>is the total size of the cache in bytes. This number should be a power of 2.
B) <block size>is a power of 2 integer that specifies the size of the cache block in bytes.
C) <cache policy>Here is valid cache policy is fifo.
D) <associativity>is one of:
direct – simulate a direct mapped cache.
assoc- simulate a fully associative cache.
assoc:n – simulate an n way associative cache. n will be a power of 2.
E) is the name of the trace file.
NOTE: Your program should check if all the inputs are in valid format, if not print error and
then terminate the program.
5. Sample Output
As the output, your program should print out the number of memory reads (per cache block),
memory writes (per cache block), cache hits, and cache misses. You should follow the exact
same format shown below (pay attention to case sensitivity of the letters), otherwise, the
autograder can not grade your program properly.
$./first 32 4 fifo assoc:2 trace2.txt
Memory reads: 3499
Memory writes: 2861
Cache hits: 6501
Cache misses: 3499
In this example above, we are simulating 2-way set associate cache of size 32 bytes. Each
cache block is 4 bytes. The trace file name is trace2.txt.
NOTE: Some of the trace files are quite large. So it might take a few minutes for the
autograder to grade for all the testcases.