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.


1 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.