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/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.

Table of Contents

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.

L1 Cache Implementation in C
L1 Cache Implementation in C using LRU and FIFO

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:

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

OR

$./cache 128 assoc:4 fifo 4 trace2.txt

Program Output

Memory reads: 3663620

Memory writes: 611377

Cache hits: 2153874

Cache misses: 3663620

Source Code

  L1 Cache implementation in C (299.2 KiB, 3,652 hits)