LRU and FIFO L1 Cache Implementation using C

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
• Cache Simulator Considerations
• Cache Replacement Polies
• Input and Output
  • Program Output
• Source Code

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

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,653 hits)