CPS 104 Problem PB Cache simulation and evaluation The FCP computer (Fastest Computer Possible) is a 32- bit computer with 32-bit address space. As part of the FCP design team effort you need to design a data cache. Your task is to write a cache simulator that will let you evalu- ate cache performance. You are given a data address- reference trace file that was generated by running a pro- gram. The file has a sequence of addresses for memory read requests generated by the CPU. The FCP computer reads 4- byte words, but the addresses are 32-bit byte addresses. You are to simulate two types of caches: 1. A direct-map cache. 2. A two-way set associative cache with LRU replacement policy. Each cache line holds 32-bytes (8 words). Each cache holds a total of N bytes of data. Note that the tag is not counted as part of the cache size. Your job is to simulate the two cache types each with total byte size N = 4K, 8K, 16K, and 32K. You have to calculate the hit ratio for each cache configuration when run on the given address trace. You need not simulate the data portion of each cache line, since only the tags, the valid bits and the LRU bits are needed in determining the cache configuration, and hence whether a read reference hits or misses. The cache is empty when you start your simulation. Set all valid bits off. Each cache type must be simulated on the entire address trace. Such a simulation is termed a "run". For the 4K runs, you must generate a hex dump of the cache configura- tion at the end of the run in a format specified below. Also, for every run, you must print a single line giving, in order: NK-W H M R where N is the cache total data size (in K bytes), W is the set associativity (1 for direct mapped, 2 for 2-way associa- tive), H is the number of cache hits observed, M the number of cache misses, and R is the hit ratio, defined as H/(H+M). R is a floating-point number and should be printed to show 3 decimal places. All the other integers in these report lines should be printed in decimal. Use TAB characters to separate the fields. The "K-" should be printed as shown between N and W, with no spaces. - 2 - The format of the hex dump required consists of: 1. A line containing just NK-W, where N and W are defined as in the report format above, used to label the fol- lowing data; 2. One line for each index set in the cache. Each of these lines should list the tags in that index set, with the Most Recently Used listed first. The tags should be separated by a single space. Invalid tags should be printed as FFFFFFFF. The index sets should be listed in increasing order from 0. Each tag should be printed as an 8-digit hexadecimal number, using cap- ital letters and leading zeros (use format %08X). Print the two hex dumps first, with the 4K-1 dump first, followed by the report lines, in increasing order of the pair (N,W). The report line for 4K-1 may be placed between the hex dumps, for program simplicity. Your program should read a single line from stdin, using gets(). That line will be less than 256 characters in length, and will contain the name of the trace file your program should process on the current run. A copy of a sample trace file is in: /afs/acpub.duke.edu/project/cps/cps104/Address_trace To open the trace file use: #include ... FILE *File_pointer; char Fname[257]; ... gets(Fname); File_pointer = fopen(Fname,"r"); To read the sequences of addresses into the variable Address use: while (fscanf(File_pointer, "%x", &Address) == 1) { ... } You may use: rewind(File_pointer); to reset the file input pointer to the beginning of the file. - 3 - Hint: The program should run faster, if it makes only one pass over the address trace file; you might be able to organize your program to do this, although it is probably a bit complicated. An alternative is to read the whole file for each cache configuration to be simulated. 1. Teams You may work in two-person teams on this problem. The teams must consist of people who have not previously worked together in this class. Whether you work in a team or not, submit a file named "mailto", containing one line per team member, giving that team member's mail address. 2. Testing Any complex program presents a problem of correctness. I know of no guaranteed method of assuring that my version of this program performs correctly in every case. I increased my confidence that it does so, by creating a pro- gram which generates test files for the cache simulator. The test generator, reproduced below, can be modified, to produce test files with different, simple, structure. If you make them simple enough, you can use reasoning to see whether the cache simulator's output is correct, or fix it, if it is not. The test program I used is below: /* Program to generate a test file for the cache simulator */ #include FILE *Fp; char *Fn = "test"; int main() { int i,j,k,n; Fp = fopen(Fn,"w"); for (n=0; n<10; n++) { for (j=0; j<2; j++) { for (i=0; i<1000; i+=32) { k = j*8192 + i; fprintf(Fp,"%08x\n",k); } } } } A summary of the output produced by running my cache simulator on the test file generated by the program above is: - 4 - 4K-1 00000002 (30 identical lines deleted) 00000002 FFFFFFFF (94 identical lines deleted) FFFFFFFF 4K-2 00000004 00000000 (30 identical lines deleted) 00000004 00000000 FFFFFFFF FFFFFFFF (30 identical lines deleted) FFFFFFFF FFFFFFFF 4K-1 0 640 0.000 4K-2 576 64 0.900 8K-1 0 640 0.000 8K-2 576 64 0.900 16K-1 576 64 0.900 16K-2 576 64 0.900 32K-1 576 64 0.900 32K-2 576 64 0.900 I offer NO guarantee that the output above is in fact correct. It is your responsibility to (a) reason about the test file produced, to see if the cache performance reported makes sense; (b) try the test file produced on your simula- tor, to see if the results are the same; (c) create your own test files, run them through your simulator, and deter- mine if the output your program produces makes sense. If you are convinced, after several tests, that your program is correct, and mine is not, please discuss the situation with me. My testing is continuing, and if I dis- cover flaws in my program which change the results above, I will report them to the whole class.