[Solved]1 Overview Goal Assignment Help Understand Caches Better Required Write Cache Simulator Us Q37267630

1 Overview
The goal of this assignment is to help you understand cachesbetter. You are required to write a
cache simulator using the C programming language. The programs haveto run on iLab machines.
We are providing real program memory traces as input to your cachesimulator. The format and
structure of the memory traces are described below.
We will not give you improperly formatted files. You can assume allyour input files will be in
proper format as described.

2 Memory Access Traces
The input to the cache simulator is a memory access trace, which wehave generated by executing
real programs. The trace contains memory addresses accessed duringprogram execution. Your
cache simulator will have to use these addresses to determine ifthe access is a hit or a miss, and
the actions to perform in each case. The memory trace file consistsof multiple lines. Each line of
the trace file corresponds to a memory accesses performed by theprogram. Each line consists of
multiple columns, which are space separated. The first columnreports the PC (program counter)
when this particular memory access occurred, followed by acolon(:). Second column lists whether
the memory access is a read (R) or a write (W) operation. And thelast column reports the actual
48-bit memory address that has been accessed by the program. Inthis assignment, you only need
to consider the second and the third columns (i.e. you don’t reallyneed to know the PCs). The last
line of the trace file will be the string #eof. We have providedyou three input trace files (some of
them are larger in size).

Here is a sample trace file.
0x804ae19: R 0x9cb3d40
0x804ae19: W 0x9cb3d40
0x804ae1c: R 0x9cb3d44
0x804ae1c: W 0x9cb3d44
0x804ae10: R 0xbf8ef498
#eof

3 Cache Simulator
You will implement a cache simulator to evaluate differentconfigurations of caches. It should be
able to run with different traces files. The followings are therequirements for your cache simulator:
• Simulate only one level cache; i.e., an L1 cache.
• The cache size, associativity, the replacement policy, and theblock size are input parameters.
Cache size and block size are specfied in bytes.
• Replacement algorithm: Least Recently Used (LRU). When a blockneeds to be replaced, the
cache evicts the block that was accessed least recently. It doesnot take into account whether
the block is frequently accessed.
• You have to simulate a write through cache.

4 Cache Simulator Interface
You have to name your cache simulator first. Your program shouldsupport the following usage
interface:
./first <cache size><associativity><cachepolicy><block size><trace file>
where:
A) <cache size>is the total size of the cache in bytes. Thisnumber should be a power of 2.
B) <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 of2.
C) <cache policy> Here is valid cache policy is lru.
D) <block size> is a power of 2 integer that specifies thesize of the cache block in bytes.
E) <trace file>is the name of the trace file.
Your program should check if all the inputs are in valid format, ifnot print error and then terminate
the program.

5 Cache Prefetcher
Prefetching is a common technique to increase the spatial localityof the caches beyond the cache
line. The idea of prefetching is to bring the data into the cachebefore it is needed (accessed). In
a normal cache, you bring a block of data into the cache wheneveryou experience a cache-miss.
Now, we want you to explore a different type of cache thatprefetches, not only bringing in the
block corresponding to the access but also prefetches one adjacentblock, which will result in one
extra memory read.

For example, if a memory address 0x40 misses in the cache and theblock size is 4 bytes, then
the prefetcher would bring the block corresponding to 0x40 + 4 intothe cache. The prefetcher is
activated only on misses and it is not active on a cache hit. Ifthe prefetched block is already in the
cache, it does not issue a memory read. With respect to cachereplacement policies, if the prefetched
block hits in the cache, the line replacement policy status shouldnot be updated. Otherwise, it is
treated similar to a block that missed the cache.

6 Cache Replacement Policy
The goal of the cache replacement policy is to decide which blockhas to be evicted in case there
is no space in the set for an incoming cache block. It is alwayspreferable – to achieve the best
performance – to replace the block that will be re-referencedfurthest in the future. There are
different ways one can implement cache replacement policy. Here weuse LRU replacement policy.

6.1 LRU
Using this algorithm, you can always evict the block accessed leastrecently in the set without any
regard to how often or how many times it was accessed before. Solet us say that your cache is
empty initially and that each set has two ways. Now suppose thatyou access blocks A, B, A, C.
To make room for C, you would evict B since it was accessed lessrecently than A.

7 Sample Run
Your program should print out the number of memory reads (per cacheblock), memory writes (per
cache block), cache hits, and cache misses for normal cache and thecache with prefetcher. You
should follow the exact same format shown below (pay attention tocase sensitivity of the letters),
otherwise, the autograder cannot grade your program properly.

$./first 32 assoc:2 lru 4 trace1.txt
no-prefetch
Memory reads: 336
Memory writes: 334
Cache hits: 664
Cache misses: 336
with-prefetch
Memory reads: 336
Memory writes: 334
Cache hits: 832
Cache misses: 168

In this example above, we are simulating 2-way set associate cacheof size 32 bytes. Each cache
block is 4 bytes. The trace file name is trace1.txt. As you cansee, the simulator should simulate
both catch types with the prefetcher and without the prefetcher ina single run and display the
results for both. Note: Some of the trace files are quite large. Soit might take a few minutes for
the autograder to grade for all the testcases.

8 Simulation Details
1. (a) When your program starts, there is nothing in the cache. So,all cache lines are empty
(invalid).
(b) you can assume that the memory size is 2pow48 . Therefore,memory addresses are 48 bit (zero
extend the addresses in the trace file if they’re less than 48-bitin length).
(c) the number of bits in the tag, cache address, and byte addressare determined by the cache size
and the block size.
2. For a write-through cache, there is the question of what shouldhappen in case of a write miss.
In this assignment, the assumption is that the block is fist readfrom memory (one read memory),
and then followed by a memory write.
3. You do not need to simulate the memory in this assignment.Because, the traces doesn’t contain
any information on data values transferred between the memory andthe caches.
4. You have to compile your program with the following flags:
-Wall -Werror -fsanitize=address

Expert Answer

---

Answer to 1 Overview The goal of this assignment is to help you understand caches better. You are required to write a cache simula… . . .