Effects of associativity

$3.$ Write a simple C program for which a $4-$way associative cache has a significantly lower miss rate than an equally sized $2-$way set associative cache. It will be easiest if you use blockSize$1.$c as a starting point. You may choose any cache size and block size you wish, but they must remain the same for the entire problem.

Hints for writing programs with a specified cache behavior:

You need not loop through the entire array. Instead, find addresses that collide in the cache. Remove the inner loop and make NUM$\_$LOOPS $1,000,000.$Notice in blockSize$1.$c that array is an array of characters; therefore, each item in the array is exactly $1$ byte. As a result, it is easy to identify data items that will or will not conflict in the cache. For example, in an $8$KB direct$-$mapped cache, array bytes $0$ and $8192$ will conflict. This is basically a pencil$-$and$-$paper problem that we happen to be using a cache simulator to verify.Write the simplest program you can that will produce a $100\%$ miss rate for the $2-$way cache.

Submit the source code, all cache parameters, and resulting hit rates.

$4.$ Write a simple C program for which an associativity of $2$ has a higher miss rate than a direct$-$mapped cache. You may choose any cache size and block size you wish, but they must remain the same for the entire problem.

Submit the source code, all cache parameters, and resulting hit rates.

Hints:

As with the previous problem, start by writing a program that has a $100\%$ miss rate for a $2-$way cache.Look for addresses that conflict in a two$-$way cache, but do not conflict in a direct$-$mapped cache.

$5.$ Explain why your code above produces the miss rates observed $($i$.$e$.,$ why your code has a higer miss rate on the two$-$way cache$).$

$6.$ Next, we will monitor the effect of associativity on a more realistic program $--$ quicksort.

Choose a cache size and leave this constant for all of the runs.The qsort executable and sample inputs are found in ~lalejina$/$qsort$/.$Use input$\_1$e$4$ for input. $($It contains $50,000$ randomly generated integers.$)$Copy qsort and input$\_1$e$4$ from ~lalejina$/$qsort$/$ into your current directory.The full command you are testing is

$./$qsort input$\_1$e$4$

Run this command through Cachegrind as you did in problem $1$ to monitor the cache behavior. However, this time you will be varying the block size and degree of associativity $($i$.$e$.,$ you will need a double loop$).$This program may take a few seconds to run.Produce a graph showing miss rates as associativity ranges over $1,2,4,8,16,$ and fully associative. Your graph should have associativity on the x$-$axis and miss$-$rate on the y$-$axis. There should be four lines $--$ one per block size. Be sure to clearly label your graph with the cache size.You are welcome to plot the data in whatever program you prefer.

Submit this plot as your answer to $(6).```$

$/*$ i$.$e$.,64$KB$.$ The array needs to be at least twice the size of the

$8$KB cache so that the array doesn't fit in memory. $*/$

#define ARRAY$\_$SIZE $64*1024$

#define NUM$\_$LOOPS $1000$

$/*****************************************************************************************$

$*$

$*$ Notice that the array is an array of characters. This means that

$*$ each item in the cache is exactly $1$ byte. This makes it easy to

$*$ identify data items that will or will not conflict in the cache.

$*$ For example, in an $8$KB direct$-$mapped cache, array bytes $0$ and $8192$

$*$ will conflict.

$*$

$*$ This program simply iterates through each byte in the cache NUM$\_$LOOPS

$*$ times.

$*$

$*$ Declaring the local variables as "register" variables encourages

$*$ the compiler to keep the values of these variables in a register,

$*$ thereby reducing their effect on the cache hit rate.

$```$

$```$

int main$()\{$

$\_$Alignas$(64)/*$ make sure that the array aligns with the cache. $*/$

char array$[$ARRAY$\_$SIZE$]$;

register int outer$\_$loop;

register int inner$\_$loop;

register int solution $=0$;

for $($outer$\_$loop $=0$; outer$\_$loop $$ NUM$\_$LOOPS; outer$\_$loop$++)\{$

for $($inner$\_$loop $=0$; inner$\_$loop $$ ARRAY$\_$SIZE; inner$\_$loop$++)\{$

solution $*=$ array$[$inner$\_$loop$]$;

$\}$

$\}$

return solution;

$\}$

$```$