We will be using a cache simulator for this homework - we will go over the simulator in lab 12 on monday. for this homework we’re going to look at sort. cc, which is provided in the files on blackboard (or i261/cache). the program uses either exchange sort or quicksort to sort a list of 10,000 random numbers. the simple version of quicksort assumes that there are no repeated numbers in the list. the list is therefore initialized with the numbers 0 to , and is then scrambled by repeatedly swapping items. read through the source code and check that you understand what the program is doing. now instrument the sorting functions (add calls to inst r and inst w) to identify all references to list. you can also look at histogram. cc to see how the addresses for the data values were sent to the simulator. starting with exchange sort, run the code through the cache simulator (without the graphical interface) and experiment with different direct mapped caches: try cache sizes in the range 4 kbytes to 64 kbytes and block sizes in the range one to eight words. in each case, record the cache access statistics and attempt to understand the observed miss rates. note that exchange sorting a list of 10,000 items takes some time: you? ll probably want to interrupt each simulation (by pressing ctrl-c) after, say, 100,000 accesses, and record the statistics up to that point. next, edit sort. cc to enable quicksort in place of exchange sort, recompile and repeat the above experiments. submit a report showing the instrumented sort. cc code and detailing the results of your experiments (tables, graphs) for each cache size, block size, and sorting algorithm. you should be able to discuss the miss rates that you were seeing and comment on any trends that you are able to discern.