Consider professor vamshi writes a program given below and run on a system which has 2way set associative 16KB data cache with 32 bytes block where each word size is 32 bits and LRU replacement policy is used. and the base address of the array is $0x0$ and initialy cache is empty, then the number of data cache misses? (Assume integer takes 4 bytes)
$int \,i,a[1024*1024],x=0;$
$for(i=0;i<1024;i++)$
{
$x+=a[i]+a[1024*i]$
}
My Analysis
Number of integer elements that can come in 1 block=$\frac{32}{4}=8\,elements/Block$
Number of blocks needed to store $1024 \times 1024$ elements=$\frac{1024^2}{8}=131072\,blocks$
#Lines=$\frac{2^{14}}{2^5}=2^9$
#sets=$\frac{2^9}{2}=2^8=256$
Therefore the mapping function of the cache is $mod\,256$
Since, this $16KB$ cache is 2way set associative, it can hold total of 512 blocks at one time when full.
Now, in our loop $0\leq i \leq 1023$ when we access $a[i]$, this will cause 1 miss per 8 accesses to array elements.So, for $a[i]$ code part I incur $\frac{1024}{8}=128\,misses$
Also, the elements $a[0]-a[1023]$ will be stored in Blocks numbered $B0,B1,….B128.$.So, they will take the set numbers as $0...128$
Now, when $i=0$ then $a[i]$ and $a[i*1024]$ refer to same element.
Now for remaining values of $i$, I need to see where $a[i*1024]$ in located in which blocks.
| $i$ |
$a[1024*i]$ |
Block Number |
Set Number |
| 1 |
$a[1024]$ |
$\lfloor \frac{1024}{8} \rfloor=B128$ |
$128$ |
| 2 |
$a[2048]$ |
$B256$ |
$0$ |
| 3 |
$a[3072]$ |
$B384$ |
$128$ |
| 4 |
$a[4096]$ |
$B640$ |
$0$ |
and so on it goes for $i=1023,a[i*1024]$
Now here One thing I need to see is
for elements $a[1016]$ to $a[1023]$ they will be present in block $B128$ and this will map to set $128$ and we can see above that access sequences of $a[i*1024]$ also has the mapping for set $128$ in every two accesses. But that won’t be a problem I think because, when $i=1016$ and till it becomes $i=1023$ the block numbered $B128$ will be continuously referenced and hence it won’t be replaced by the access sequence generated by the code part of $a[i*1024].$(LRU is the replacement policy)
Now the number of misses causes by code part of $a[i*1024]$ will be
$1024-1$($-1$ because at $i=0$, only $a[0]$ accessed) and then after that every time a new block is accessed which causes a cache miss.
Total misses=$1023+128=1151$
Please let me know If I went somewhere wrong.
