In C:

Program (80 points) -You will write a program cachesim that reads a trace of memory accesses and simulates the behavior of two caches for that trace.

²Can direct-mapped and fully associative caches be considered special cases of n-way associativity?

³For direct-mapped caches, no decision needs to be made, because each set only contains one cache line.

⁴For a prefetching cache, the prefetched block is considered to be accessed if it is loaded from memory, but is not accessed if it is already in the cache.

Your program will take ?ve arguments. These are:

1. The cache size, in bytes. This will be a power of two.

2. The associativity, which will be direct for a direct-mapped cache, assoc:n for an n-way associative cache, or assoc for a fully associative cache (see section 1.2)

3. The replacement policy, which will be ?fo or lru .

4. The block size, in bytes. This will be a power of two.

5. The trace ?le.

Your program will use the ?rst four arguments to con?gure two caches, one which prefetches and one which does not. It will read the memory accesses in the trace ?le and simulate the behavior of both caches. When it is complete, it will print the number of cache hits, cache misses, memory reads, and memory writes for both caches.

Usage ./cachesim 512 direct fifo 8 trace1.txt

Your program SHOULD con?rm that the block size and cache size are powers of two. If the associativity is assoc:n, your program SHOULD con?rm that n is a power of two.

Your program MUST implement the ?fo replacement policy. Your program MAY implement lru for extra credit.

Input- The input is a memory access trace produced by excuting real programs. Each line describes a memory access, which may be a read or write operation. The lines contain three columns, separated by spaces. The ?rst is the program counter (PC) at the time of the access, followed by a colon. The second is R or W, indicating a read or write, respectively. The third is the 48-bit memory address which was accessed. Additionally, the last line of the ?le contains only the string #eof.

Here is a sample trace ?le: 0x804ae19: R 0x9cb3d40

0x804ae19: W 0x9cb3d40

0x804ae1c: R 0x9cb3d44

0x804ae1c: W 0x9cb3d44

0x804ae10: R 0xbf8ef498

#eof

You MAY assume that the trace ?le is correctly formatted. Output- Your program will print the number of cache hits, cache misses, memory reads, and memory writes observed when simulating the memory access trace, both with no prefetching and with prefetching.

The output must have this form:

no-prefetch

Cache hits: 6501

Cache misses: 3499

Memory reads: 3499

Memory writes: 2861

with-prefetch

Cache hits: 8124

Cache misses: 1876

Memory reads: 3521

Memory writes: 2861