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.

Improve this question
$\endgroup$
8
  • $\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, 2013 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, 2013 at 4:51
  • $\begingroup$ I have edited the question & added only one block will be moved in case of miss. $\endgroup$
    – avi
    Apr 8, 2013 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, 2013 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, 2014 at 22:16

2 Answers 2

Reset to default
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

Improve this answer
$\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%.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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