# Compute cache miss rate for the given code

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.