# Finding hit ratio of a cache

Consider an array A[100] & each element occupies 4 word. A 32 word cache is used and divided into 8 word blocks. What is the hit ratio for the following statement. Assume one block is read into cache in case of miss:

for(i=0;i<100;i++)
A[i]=A[i]+10


each array element is of 4 word & each cache block size is 8 words, so we load 8 words into cache.

When program tries to read A[0], for the first time it will be miss. Hence it will be brought to memory (& also A[1]). Next, A[1] will be hit. So, it will be like :

• A[0] - Miss
• A[1] - Hit
• A[2] - Miss
• A[3] - Hit
• .....

So hit ratio is 50% ? Am I wrong anywhere ?

I also have one more doubt. First when it tries to access A[0], it will be miss. And then when it brings A[0] to cache, CPU tries to access A[0] again, now it should be considered as hit ? Like,

• A[0] (Write) - Hit
• A[1] (Write) - Hit

If above is correct, then Hit ratio will be 75%.

Any help regarding this is appreciated.

• Wouldn't this depend on the optimization capabilities of the compiler and how the array, A, was generated? Ideally couldn't the optimization process move all 32 words in at a time? Then on a miss move in the next 32 for a miss, 7x hit, miss, 7x hit, ... , miss, hit, hit, hit? For a 12% cash miss? – dhj Apr 8 '13 at 4:28
• I think optimisation of compiler isn't considered here. So I assumed cpu will move only one block from memory to cache & not fill the entire cache. – avi Apr 8 '13 at 4:51
• I have edited the question & added only one block will be moved in case of miss. – avi Apr 8 '13 at 5:00
• I think you answered your own question! If you count read hits and write hits (not just read hits) and ignore any optimization that could be done (just one 8 word block at a time) then I think your edit is the reason the answer is given as 75%! Homework problem? :) – dhj Apr 8 '13 at 14:26
• Don't you mean cache line is 8 words? Or is cache block the same as a line? I've never heard that terminology. – gardenhead Jun 28 '14 at 22:16

Since the line size is 8 words, 2 consecutive elements are loaded into the cache per miss. Now notice that each element is accessed twice, once for a read and once for a write. So for every even $i$th element, when it is first read, it will be a miss, and hence the corresponding cache line - containing elements $i$ and $i+1$ - will be read into the cache. Now the write to element $i$ will be a hit, as well as both references to element $i+1$. So for every 4 references, there will be 1 miss and 3 hits. Thus the hit rate is 75% and the miss rate is 25%.