Problem $5.(12$ points$)$:

$3M$ decides to make Post$-$Its by printing yellow squares on white pieces of paper. As part of the printing process,

they need to set the CMYK $($cyan$,$ magenta, yellow, black$)$ value for every point in the square. $3$M hires you to

determine the efficiency of the following algorithms on a machine with a $2048-$byte direct$-$mapped data cache with

$32$ byte blocks.

You are given the following definitions:

struct point$\_$color $\{$

int $c$;

int $m$;

int $y$;

int $k$;

;

struct point$\_$color square $[16][16]$ :

register int $i,j$ :

Assume:

sizeof$($int$)=4$

square begins at memory address $0$

The cache is initially empty.

The only memory accesses are to the entries of the array square. Variables i and $j$ are stored in registers.

A$.$ What percentage of the writes in the following code will miss in the cache?

for

for $(j=0$;$j<mn\; id="EditorElement\_456550">1</mn><mn\; id="EditorElement\_456551">6</mn>$;$j++)($

square $[$i$][$j$].$c $=0$ :

square $[i][j]*m=0$;

square $[$i$][$j$]y=1$

square $[i][j].k=0$;

$\}$

Miss rate for writes to square:

$\%$

B$.$ What percentage of the writes in the following code will miss in the cache?

for

for

square $[j][i].c=0$;

square $[j][i].m=0$;

square $[j][i]*y=1$;

square $[j][i].k=0$ :

$\}$

Miss rate for writes to square:

C$.$ What percentage of the writes in the following code will miss in the cache?

for

for $(j=0$;$j<mn\; id="EditorElement\_455911">1</mn><mn\; id="EditorElement\_455912">6</mn>$;$j++)($

square $[$i$][$j$]y=1$;

$]$

for

for $(j=0$;$j<mn\; id="EditorElement\_455818">1</mn><mn\; id="EditorElement\_455819">6</mn>$;$j++)($

square $[$i$][$j$].$c $=0$;

square $[i][j]*m=0$;

square $[i][j].k=0$ :

$\}$