3
$\begingroup$

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] (Read) - Miss
  • A[0] (Write) - Hit
  • A[1] (Read) - Hit
  • A[1] (Write) - Hit

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

Any help regarding this is appreciated.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – dhj Apr 8 '13 at 4:28
  • $\begingroup$ 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. $\endgroup$ – avi Apr 8 '13 at 4:51
  • $\begingroup$ I have edited the question & added only one block will be moved in case of miss. $\endgroup$ – avi Apr 8 '13 at 5:00
  • 1
    $\begingroup$ 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? :) $\endgroup$ – dhj Apr 8 '13 at 14:26
  • 1
    $\begingroup$ Don't you mean cache line is 8 words? Or is cache block the same as a line? I've never heard that terminology. $\endgroup$ – gardenhead Jun 28 '14 at 22:16
1
$\begingroup$

Since there is 8 word block, 2 element can stay in one block. Now notice that each element is refered twice, one read and one write operation. So when in a block when 1st element is refered for read, it will be miss, and hence that block will be copied to cache. Now 2nd reference to that 1st element will be hit, as well as both reference to 2nd element will also ne hit sience block has 2 elements. So out of 4 reference, 1 miss and 3 hit for one block. Gets repeated for each and every block. So hit 3/4 and miss 1/4

$\endgroup$
1
$\begingroup$

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%.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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