This is a Cache Simulator program to demonstrate cache mechanism which is written in C. The source code can run in many of the C Compilers with minor modifications (if required). It can run on real memory traces provided as input and shows output as number of memory reads, writes and cache hits, misses.
Memory Access Traces
As mentioned earlier, the input to the cache simulator is memory traces, which can be generated by executing computer programs. You can use programs such as Valgrind to perform memory profiling and tracing. The trace contains memory addresses accessed during program execution. Cache simulator uses those 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 of which corresponds to a memory access performed by the program. Each line consists of multiple columns, which are space separated.
The first column reports the PC (program counter) when this particular memory access occurred, followed by a colon. Second column lists whether the memory access is a read (R) or a write (W) operation. The last column reports the actual 48-bit memory address that has been accessed by the program.
In this C Program, we only use the second and the third columns and not going to use Program Counter (PC) column.
Here is a sample trace file:
0x804ae1c: W 0x9cb2874 0x804ae10: R 0xbf8ef498 0x804ae16: R 0xbf8ef49c 0x804ae19: R 0x9cb2880 0x804ae19: W 0x9cb2880 0x804ae1c: R 0x9cb2884 0x804ae1c: W 0x9cb2884 0x804ae10: R 0xbf8ef498 0x804ae16: R 0xbf8ef49c 0x804ae19: R 0x9cb2890 0x804ae19: W 0x9cb2890
Cache Simulator Considerations
We only implement Level 1 cache and is write through.
- Initially cache is empty and cache lines are all invalid.
- The cache size, associativity, the replacement policy, and the block size are input parameters.
- Cache size and block size are specified in bytes as input.
- Number of bits for tag, set index and block offset are determined by the input.
- The program checks if input is in valid format. If input is not valid then show an error message and program exits.
Cache Replacement Polies
We have implemented two cache replacement policies i.e. least recently used (LRU) and First-in first-out (FIFO) replacement policies.
Using LRU algorithm, we always evict the block accessed least recently in the set without any regard to how often or how many times it was accessed before. Let’s say that your cache is empty initially that Set has two lines. Now assume that you access blocks A, B, A, C. To make room for C, you would evict B since it was accessed less recently than A.
In First-in first-out (FIFO), you evict the block that was added to the set earliest. Suppose we have two lines and access A, B, A, C. To make room for C, you would evict A, since it was added earlier than B.
Input and Output
The program prints out the number of memory reads, memory writes, cache hits, and cache misses in the following format.
$./cache 32 assoc:2 lru 4 trace1.txt
$./cache 128 assoc:4 fifo 4 trace2.txt
Memory reads: 3663620
Memory writes: 611377
Cache hits: 2153874
Cache misses: 3663620