Compute cache miss rate for the given code

Question

Problem Description:

We consider a 128-byte data cache that is 2-way associative ($E=2$) and can hold 4 doubles in every cache line. A double is assumed to require 8 bytes.

For the below code we assume a cold cache. Further, we consider an array A of 32 doubles that are cache aligned (that is, $A[0]$ is loaded into the first slot of a cache line in the first set). All other variables are held in registers. The code is parameterized by positive integers $m$ and $n$ that satisfy $m*n = 32$ (i.e., if you know one you know the other). Recall that the miss rate is defined as $\frac{\text{number of misses}}{\text{number of accesses}}.$

// Code: 
float A[32], t = 0;
for(int i = 0; i < m; i++)
  for(int j = 0; j < n; j++)
      t += A[j*m + i];

Problem: Determine the miss rate for when $m=1,2$ and $16.$

My Attempt:

When $m=1$ we access the elements, $$A[0],A[1],A[2],\cdots,A[31]$$ and since each block in the cache can hold $2$ doubles, this means that for every miss we get one hit and so the miss rate is $1/2.$

When $m=2$ we access the elements, $$A[0],A[2],A[4],\cdots,A[30].$$ Here we first miss $A[0]$ but then we load the block with $(A[0],A[1]).$ However, this does not help since we need to access $A[2]$ and therefore we miss every time and thus the miss rate is $1.$

When $m=16$ we access the elements, $$A[0],A[1],A[2],\cdots,A[31].$$ And so like before this should have a miss rate of $1/2.$

However, the answers are: $$m=1, \text{miss rate} = 1/4$$ $$m=2, \text{miss rate} = 1/2$$ $$m=16, \text{miss rate} = 1/4.$$

I am not sure how to obtain these answers and so any help will be much appreciated.

Answer 1

As the cache is 4 doubles, for m=1, after accessing A[0], there are in the cache A[0]...A[3]. So next access A[1] is a hit and it is the same for A[2] and A[3]. Only access A[4] will be a miss. Hence miss rate is 0.25

For m=2, After accessing A[0], the cache holds the same line. Next access is A[2] which is a hit, and A[4] is a miss and so on. So miss rate is 0.5. Note that total cache size is 8 doubles. So when accessing A[8], cache line 0 is cleared and when A[1] will be accessed on later iterations, it will be again a miss.

For m=16 and n=2, one needs to look closely at the access patterns. Also do not forget that the cache is associative with two lines.

iteration 1 i=0, j=0 -> A[0] miss in line 0
iteration 2 i=0, j=1 16j+i -> A[16] miss in line 1
iteration 3 i=1, j=0 16j+i -> A[1] hit in line 0 (because cache is 2 ways associative)
iteration 4 i=1, j=1 16j+i -> A[17] hit in line 1

and all access will be hits until iteration 8 (i=4, j=0). In that case, we access A[4] that isn't in any cache and we restart a new cycle. So we have 2 misses for 8 iteations and miss rate is 0.25