Finding the Cache Miss/Hit Rate in Multi-Dimensional Arrays

Question

I'm trying to study for a test and one of the practice problems involve calculating the "hit" and "miss" rates for a cache. I have the answer to the question, but I can't figure out the process behind it.

Given the following;

A 2048-byte direct- mapped data cache with 32-byte blocks. and assuming sizeof(int) == 4, Square begins at memory address 0, The cache is initially empty and Variables i and j are stored in registers.

  struct point_color { 
  int c; 
  int m; 
  int y; 
  int k; 
  }; 

  struct point_color square[16][16]; 
  int i, j;

  for (i = 0; i < 16; i++){ 
  for (j = 0; j < 16; j++) { 
  square[i][j].c = 0; 
  square[i][j].m = 0; 
  square[i][j].y = 1; 
  square[i][j].k = 0; 
  } 
  } 

I'm trying to find the "total number of writes that miss in the cache" and the "miss rate"

So far, I know that the total number of writes is 16*16*4 = 1024 times, but I'm completely lost when attempting to find the cache hit and miss rates.

Answer 1

A 2048-byte direct- mapped data cache with 32-byte blocks. and assuming sizeof(int) == 4, Square begins at memory address 0, The cache is initially empty and Variables i and j are stored in registers.

You can view struct point_color square[16][16]; as a long tape in memory starting from 0. Each entry in the matrix contains a struct of size 4*4 = 16 bytes. When the matrix is completely filled with structs it will be of size 16*16*16 = 4096 bytes. (memory addresses 0...4095-16), looking like this (memory addresses on the right):

+-----------------+
|  square[0][0]   | 0-15
+-----------------+
|  square[0][1]   | 16-31
+-----------------+
|  square[0][2]   | 32-47
+-----------------+
        .
        .
        .
+-----------------+
|  square[15][15] | 4080-4095
+-----------------+

The cache is direct-mapped with 32-byte blocks, that means that it will look like this:

  +----------------+
  |    32 bytes    | row 0   
  +----------------+          
  |    32 bytes    | row 1    
  +----------------+          
  |    32 bytes    | row 2    
  +----------------+          
          .                   
          .                   
          .                   
  +----------------+          
  |    32 bytes    | row 63   
  +----------------+       

As you see the first 2048 bytes that is written will all fit in the cache, after that the cache will need to start replacing rows in the cache. Since this is a direct-mapped cache the replacement is straight-forward. You can calculate which row in the cache that the memory-block should be placed by looking at the memory address and dividing it into parts. For this particular cache the address-layout is:

   +----------------------+----------+--------+
   |       21bits         | 6bits    | 5bits  |
   |        tag           | index    | offset |
   +----------------------+----------+--------+

The sequence of operations and cache hit/miss will look like this:

write square[0][0].c = 0;   ---> cache miss (address 0), load memory block 0-31 into cache
write square[0][0].m = 0;   ---> cache hit (address 4)
write square[0][0].y = 0;   ---> cache hit (address 8)
write square[0][0].k = 0;   ---> cache hit (address 12)
write square[0][1].c = 0;   ---> cache hit (address 16)
write square[0][1].m = 0;   ---> cache hit (address 20)
write square[0][1].y = 0;   ---> cache hit (address 24)
write square[0][1].k = 0;   ---> cache hit (address 28)
write square[0][2].c = 0;   ---> cache miss (address 32), load memory block 32-63 into cache
write square[0][2].m = 0;   ---> cache hit (address 36)
write square[0][2].y = 0;   ---> cache hit (address 40)
                             .
                             .
                             .
                             .
write square[8][0].c = 0;   ---> cache miss (address 2048), load memory block 2048-2079 into cache and replace the cache-row containing memory block 0-31
write square[8][0].m = 0;   ---> cache hit (address 2052)
write square[0][0].y = 0;   ---> cache hit (address 2056)
                             .
                             .
                             .

You see the pattern? 1/8 operations will be a cache miss.

Miss-rate: 12.5%

Hit-rate: 87.5%