This problem is to predict the cache behavior of C code. You are given the following code to analyze:

int x$[2][128]$;

int sum $=0$;

for$($int i$=0$; i$<128$; i$++$

$$sum $+=$ x$[0][$i$]*$ x$[1][$i$]$;

Assume this code is executed under the following conditions:

sizeof$($int$)=4$

Array x begins at memory address $0$ and is stored in row$-$major order.

The cache is initially empty in each case below.

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

Given these assumptions, estimate the miss rates for the following cases:

Size of the array x $=2$ x $128$ x $4=1024=1$K bytes

Case $1$: Assume the cache is $512$ bytes, direct$-$mapped, with $16-$byte cache blocks. What is the miss rate?

Cache size $=512$ bytes, B $=16,$ S $=512/16=32$ sets

One cache line can hold $4$ elements of the array x

i$=0$:$$

$$x$[0][0]$ misses $($cold miss$)$ and x$[0][0]$ x$[0][1]$ x$[0][2]$ x$[0][3]$ are loaded in set $0$

$$x$[1][0]$ misses $($conflict miss$)$ and x$[1][0]$ x$[1][1]$ x$[1][2]$ x$[1][3]$ are loaded in set $0$

i$=1$:

$$x$[0][1]$ misses $($conflict miss$)$ and x$[0][0]$ x$[0][1]$ x$[0][2]$ x$[0][3]$ are loaded in set $0$

$$x$[1][1]$ misses $($conflict miss$)$ and x$[1][0]$ x$[1][1]$ x$[1][2]$ x$[1][3]$ are loaded in set $0$

i$=2$:

$$ x$[0][2]$ misses $($conflict miss$)$ and x$[0][0]$ x$[0][1]$ x$[0][2]$ x$[0][3]$ are loaded in set $0$

$$ x$[1][2]$ misses $($conflict miss$)$ and x$[1][0]$ x$[1][1]$ x$[1][2]$ x$[1][3]$ are loaded in set $0$

i$=3$:

$$ x$[0][3]$ misses $($conflict miss$)$ and x$[0][0]$ x$[0][1]$ x$[0][2]$ x$[0][3]$ are loaded in set $0$

$$ x$[1][3]$ misses $($conflict miss$)$ and x$[1][0]$ x$[1][1]$ x$[1][2]$ x$[1][3]$ are loaded in set $0$

The pattern is always missing:

Miss rate $=100\%$

Case $2$: What is the miss rate if we double the cache size to $1,024$ bytes?

Cache size $=1,024$ bytes, B $=16,$ S $=1,024/16=64$ sets

One cache line can hold $4$ elements of the array x

i$=0$:$$

$$x$[0][0]$ misses $($cold miss$)$ and x$[0][0]$ x$[0][1]$ x$[0][2]$ x$[0][3]$ are loaded in set $0$

$$x$[1][0]$ misses $($cold miss$)$ and x$[1][0]$ x$[1][1]$ x$[1][2]$ x$[1][3]$ are loaded in set $32$

i$=1$:

$$x$[0][1]$ hits

$$x$[1][1]$ hits

i$=2$:

$$ x$[0][2]$ hits

$$ x$[1][2]$ hits

i$=3$:

$$ x$[0][3]$ hits

$$ x$[1][3]$ hits

The pattern is always $2$ misses followed by $6$ hits $(2$ of $8$ reads miss$)$

Miss rate $=25\%$

Case $3$: Now assume the cache is $512$ bytes, two$-$way associative using an LRU replacement policy, with $16-$byte cache blocks. What is the cache miss rate?

Cache size $=512$ bytes, B $=16,$ E $=2,$ S $=512/32=16$ sets

One cache line can hold $4$ elements of the array x

$$i$=0$:$$

$$x$[0][0]$ misses $($cold miss$)$ and x$[0][0]$ x$[0][1]$ x$[0][2]$ x$[0][3]$ are loaded in set $0$ line $1$

$$x$[1][0]$ misses $($cold miss$)$ and x$[1][0]$ x$[1][1]$ x$[1][2]$ x$[1][3]$ are loaded in set $0$ line $2$

$$i$=1$:

$$x$[0][1]$ hits

$$x$[1][1]$ hits

$$ i$=2$:

$$ x$[0][2]$ hits

$$ x$[1][2]$ hits

$$ i$=3$:

$$ x$[0][3]$ hits

$$ x$[1][3]$ hits

$$ The pattern is always $2$ misses followed by $6$ hits $(2$ of $8$ reads miss$)$

$$ Miss rate $=25\%$

Case $4$: For case $3,$ will a larger cache size help to reduce the miss rate? Why or why not?

A larger cache size will not help to reduce the miss rate because the only misses are cold misses $($unavoidable$)$

Case $5$: For case $3,$ will a larger block size help to reduce the miss rate? Why or why not?$$

Yes. Because more elements will be loaded in the cache line.$$

Example: B $=32$ bytes

x$[0][0]$ will miss and$$

$8$ elements are loaded in the cache x$[0][0]$ to x$[0][7]-$ Set$0($line$1)$

x$[1][0]$ will miss and

$8$ elements are loaded in the cache x$[1][0]$ to x$[1][7]-$ Set$0($line$2)$

x$[0][1]$ will hit

x$[1][1]$ will hit

x$[0][2]$ will hit

x$[1][2]$ will hit

x$[0][3]$ will hit

x$[1][3]$ will hit

x$[0][4]$ will hit

x$[1][4]$ will hit

x$[0][5]$ will hit

x$[1][5]$ will hit

x$[0][6]$ will hit

x$[1][6]$ will hit

x$[0][7]$ will hit

x$[1][7]$ will hit

x$[0][8]$ will miss and

$8$ elements are loaded in the cache x$[0][8]$ to x$[0][15]-$ Set$1($line$1)$

x$[1][8]$ will miss and

$8$ elements are loaded in the cache x$[1][8]$ to x$[1][15]-$ Set$1($line$2)$

x$[0][9]$ will hit

x$[1][9]$ will hit

x$[0][10]$ will hit

x$[1][10]$ will hit

x