[Solved]1 Overview Goal Assignment Help Understand Caches Better Required Write Cache Simulator Us Q37185031
1 Overview
The goal of this assignment is to help you understand cachesbetter. You are required to write a cache simulator using the Cprogramming language. The programs have to run on iLab machines. Weare providing real program memory traces as input to your cachesimulator. The format and structure of the memory traces aredescribed below. We will not give you improperly formatted files.You can assume all your input files will be in proper format asdescribed.
2 Memory Access Traces The input to the cache simulator is amemory access trace, which we have generated by executing realprograms. The trace contains memory addresses accessed duringprogram execution. Your cache simulator will have to use theseaddresses to determine if the access is a hit or a miss, and theactions to perform in each case. The memory trace file consists ofmultiple lines. Each line of the trace file corresponds to a memoryaccesses performed by the program. Each line consists of multiplecolumns, 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 memoryaccess is a read (R) or a write (W) operation. And the last columnreports the actual 48-bit memory address that has been accessed bythe program. In this assignment, you only need to consider thesecond and the third columns (i.e. you dont really need to know thePCs). The last line of the trace file will be the string #eof. Wehave provided you three input trace files (some of them are largerin size). Here is a sample trace file. 0x804ae19: R 0x9cb3d400x804ae19: W 0x9cb3d40 0x804ae1c: R 0x9cb3d44 0x804ae1c: W0x9cb3d44 0x804ae10: R 0xbf8ef498 #eof 1
3 Cache Simulator
You will implement a cache simulator to evaluate differentconfigurations of caches. It should be able to run with differenttraces files. The followings are the requirements for your cachesimulator: • 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 arespecfied in bytes. • Replacement algorithm: Least Recently Used(LRU). When a block needs to be replaced, the cache evicts theblock that was accessed least recently. It does not take intoaccount whether the block is frequently accessed. • You have tosimulate a write through cache.
4 Cache Simulator Interface
You have to name your cache simulator first. Your program shouldsupport the following usage interface: ./first where: A) is thetotal size of the cache in bytes. This number should be a power of2. B) is one of: direct – simulate a direct mapped cache. assoc -simulate a fully associative cache. assoc:n – simulate an n wayassociative cache. n will be a power of 2. C) Here is valid cachepolicy is lru. D) is a power of 2 integer that specifies the sizeof the cache block in bytes. E) is the name of the trace file. Yourprogram should check if all the inputs are in valid format, if notprint error and then terminate the program.
5 Cache Prefetcher
Prefetching is a common technique to increase the spatiallocality of the caches beyond the cache line. The idea ofprefetching is to bring the data into the cache before it is needed(accessed). In a normal cache, you bring a block of data into thecache whenever you experience a cache-miss. Now, we want you toexplore a different type of cache that prefetches, not onlybringing in the block corresponding to the access but alsoprefetches one adjacent block, which will result in one extramemory read. For example, if a memory address 0x40 misses in thecache and the block size is 4 bytes, then the prefetcher wouldbring the block corresponding to 0x40 + 4 into the cache. Theprefetcher is 2 activated only on misses and it is not active on acache hit. If the prefetched block is already in the cache, it doesnot issue a memory read. With respect to cache replacementpolicies, if the prefetched block hits in the cache, the linereplacement policy status should not be updated. Otherwise, it istreated similar to a block that missed the cache. 6 CacheReplacement Policy The goal of the cache replacement policy is todecide which block has to be evicted in case there is no space inthe set for an incoming cache block. It is always preferable – toachieve the best performance – to replace the block that will bere-referenced furthest in the future. There are different ways onecan implement cache replacement policy. Here we use LRU replacementpolicy. 6.1 LRU Using this algorithm, you can always evict theblock accessed least recently in the set without any regard to howoften or how many times it was accessed before. So let us say thatyour cache is empty initially and that each set has two ways. Nowsuppose that you access blocks A, B, A, C. To make room for C, youwould evict B since it was accessed less recently than A. 7 SampleRun Your program should print out the number of memory reads (percache block), memory writes (per cache block), cache hits, andcache misses for normal cache and the cache with prefetcher. Youshould follow the exact same format shown below (pay attention tocase sensitivity of the letters), otherwise, the autograder cannotgrade your program properly. $./first 32 assoc:2 lru 4 trace1.txtno-prefetch Memory reads: 336 Memory writes: 334 Cache hits: 664Cache misses: 336 with-prefetch Memory reads: 336 Memory writes:334 Cache hits: 832 Cache misses: 168 In this example above, we aresimulating 2-way set associate cache of size 32 bytes. Each cacheblock is 4 bytes. The trace file name is trace1.txt. As you cansee, the simulator should simulate both catch types with theprefetcher and without the prefetcher in a single run and displaythe results for both. Note: Some of the trace files are quitelarge. So it might take a few minutes for the autograder to gradefor all the testcases. 3
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 thatthe memory size is 2pow48 . Therefore, memory addresses are 48 bit(zero extend the addresses in the trace file if theyre less than48-bit in length). (c) the number of bits in the tag, cacheaddress, and byte address are determined by the cache size and theblock size. 2. For a write-through cache, there is the question ofwhat should happen in case of a write miss. In this assignment, theassumption is that the block is fist read from memory (one readmemory), and then followed by a memory write. 3. You do not need tosimulate the memory in this assignment. Because, the traces doesntcontain any information on data values transferred between thememory and the caches. 4. You have to compile your program with thefollowing flags: -Wall -Werror -fsanitize=address 9 Submission Youhave to e-submit the assignment using Sakai . Put all files (sourcecode + Makefile + report.pdf) into a directory named first, whichitself is a sub-directory under pa4 . Then, create a tar file(follow the instructions in the previous assignments to create thetar file). Your submission should be only a tar file named pa4.tar.You have to e-submit the assignment using Sakai. Your submissionshould be a tar file named pa4.tar. To create this file, puteverything that you are submitting into a directory named pa4.Then, cd into the directory containing pa4 (that is, pa4s parentdirectory) and run the following command: $tar cvf pa4.tar pa4 Tocheck that you have correctly created the tar file, you should copyit (pa4.tar) into an empty directory and run the following command:$tar xvf pa4.tar This is how the folder structure should be. • pa4– first ∗ first.c ∗ first.h ∗ Makefile ∗ report.txt Source code:all source code files necessary for building your programs. e.g.first.c and first.h. Makefile: There should be at least two rulesin your Makefile: first: build the executables (first). clean:prepare for rebuilding from scratch. report.txt: In a text file,you should briefly describe the main data structures being used inyour program. More importantly, you should report your observationon how the prefetcher changed the cache hits and number of memoryreads. Explain why?
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… . . .
OR
