CODEWITHSUNDEEP
c++cachingmemorycpu-architecture
RRP
RRP

Reputation: 2853

Fully Associative Cache

I am to trying to figure a problem for hw, where i need to see how many cache misses occur for the following nested loop

for i=0; i < 32 ; i++
   for j=0; j < 32; j++
      sum += arr[i][j];

I have a fully associative cache which has 16 cache lines, where each cache line can store 32 words. The cache is initially empty and arr[0][0] maps to the first cache line

Now according to my understanding, there will be a total of 32 misses.Initially when a request is made the cache is empty so it counts as a miss and according to a fully associative cache all the blocks get populated and then the LRU is applied.

I am a bit confused here,could use some guidance here

Upvotes: 0

Views: 1425

Answers (1)

Rohith R
Rohith R

Reputation: 1329

Assuming an integer is stored in a word.

Lets start with the 1st memory access ie. arr[0][0]. It will result in a miss which comes under compulsory miss. This will bring 32 integers in to the cache. To our benefit we are going to access those exact memory locations in our further accesses. Which is from arr[0][0] to arr[0][31].

Now when we access arr[1][0] we are accessing the 33rd location and this is not in our cache. So this is again a miss.

In general for every 32 values that you access you will have a miss. Please not that this is only for the kind of loop that you have showed :

for i=0; i < 32 ; i++
   for j=0; j < 32; j++
      sum += arr[i][j];

Here the memory access is continuous. Further as @Peter Cordes said in the comments, the fully associative cache will behave in the exact same way as a direct mapped cache in your particular case.

Upvotes: 2

Related Questions