1
$\begingroup$

Below, we have given you four different sequences of addresses generated by a program running on a processor with a data cache. Cache hit ratio for each sequence is also shown below.

\begin{array}{|c|c|c|} \hline Sequence No. & Address Sequence & Hit Ratio \\ \hline 1& 0, 2, 4, 8, 16, 32, 64, 128 &0.50\\ \hline 2&0, 1024, 2048, 3072, 4096, 3072, 2048, 1024, 0 &0.33 \\ \hline 3&0, 256, 512, 1024, 2048, 1024, 512, 256, 0 &4/9 \\ \hline 4& 0, 512, 2048, 0, 1536, 0, 1024, 512 &0.25 \\ \hline \end{array}

Assumptions: all memory accesses are one byte accesses. All addresses are byte addresses. Assuming that the cache is initially empty at the beginning of each sequence, find out the
following parameters of the processors data cache:

  1. Associativity (1, 2 or 4 ways) (4 points)
  2. Block size (1, 2, 4, 8, 16, or 32 bytes) (4 points)
  3. Total cache size (1024 B or 2048 B) (4 points)
  4. Replacement policy (LRU or FIFO) (4 points)

Please justify (explain) your answers.

I can't understand what they are asking. When they say "find out the following parameters of the processors data cache", do they mean that I have to choose one of these parameters that fits the logic in the table? Can you better explain what I have to do in this problem?

$\endgroup$
  • 2
    $\begingroup$ For caches with different parameters, those address sequences would all get different hit ratios. You have to deduce what kind of parameters would give the hit ratios shown. $\endgroup$ – Karolis Juodelė Nov 15 '16 at 8:43
  • 1
    $\begingroup$ This problem is designed to make you review the course material and then do basic arithmetics. I suggest you do so. $\endgroup$ – Raphael Nov 15 '16 at 10:23
  • 1
    $\begingroup$ I think I got it. I took number theory and abstract algebra. I found an application of congruence in this exercise. I feel happy that I finally found some meaning in having taken these courses. $\endgroup$ – TheMathNoob Nov 15 '16 at 10:34
  • $\begingroup$ @Raphael I need help. Consider this link and take a look at page 10/10 ece.cmu.edu/~ece447/s13/lib/exe/…. For the total cache size, why do they say that For sequence 3, a total cache size of 512 B will give a hit rate of 4/9 with a 4-way associative cache and 8 byte blocks regardless of the replacement policy, which is higher than 0.33. If we consider a 512 B cache then the numer of sets is $(512/8)/4=16$. All 0, 64, 128, 256, 512 are congruent to 0 mod (16), so they all map to the same set which means at 512 we have to make a replacement. $\endgroup$ – TheMathNoob Nov 17 '16 at 5:01
  • $\begingroup$ This will lead to 3/9 hits since one piece of data was flushed by the replacement. $\endgroup$ – TheMathNoob Nov 17 '16 at 5:02

Your Answer

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

Browse other questions tagged or ask your own question.