Tag: compute

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.