1
$\begingroup$

This a problem in a computer architecture course that's giving me some trouble:

You have an application whose memory access pattern is a stream and its entire data set is 128kB. The data cache in your machine has a capacity of 64kB. It is word-addressable and direct-mapped with 32B lines. It is able to fetch one line at a time.

Given the access pattern: 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, …, 32768, where each access is a 4B word.

  1. What is the miss rate?
  2. Can the miss rate be reduced by using a larger cache?
  3. Can the miss rate be reduced if the size of the data set were reduced?

Here's what I think is going on: The cache is initially empty, meaning each access will result in a compulsory miss. So would this mean the miss rate is 100%, since no data is initially loaded and the pattern doesn't hit any address twice?

Any help understanding this would be much appreciated!

|cite|improve this question
$\endgroup$
  • $\begingroup$ The reason why cache works is the principle of locality. It depends how data is loaded into the cache I think, if it's only loaded once the address is accessed, yes that will result in 100% miss rate. However, it can be possible to fetch more data (When position Y is needed, load position Y + position Y+ 1, because you guess the other positions are needed soon.) If I recall correctly, for hard-drives they fetch more data than the data requested, because the PoL holds, the next request could be in cache. Not sure how applicable this is to your situation. $\endgroup$ – Dylan Meeus Jul 6 '14 at 21:43
  • $\begingroup$ Thanks Dylan. I was missing that critical piece of the puzzle. $\endgroup$ – Victor Brunell Jul 6 '14 at 22:26
4
$\begingroup$

It seems you don't understand how cache lines work. A cache line is a contiguous chunk of memory. In this example, the cache line size is 32 bytes. This means that 32 contiguous bytes are always loaded into the cache at a time, namely whenever a miss occurs.

So if we initially assume the cache is empty (or "cold"), then the first access will be a miss. However, the first 28 bytes will be loaded in. This means that in addition to loading word 0 into the cache, the words at addresses 4, 8, 12, 16, 20, 24, and 28 will also get loaded into the cache. Conveniently, this is how your example program accesses data (linearly), so we will get a cache hit for all of those words. When we hit the word at address 32 we will again get a miss and the process repeats. Thus, our miss rate is 1/8, once for every 32 byte block.

Since we are never accessing the same data more than once, the size of the cache itself is irrelevant, i.e. all we need is for the cache to be able to hold a single line. Thus, we can not reduce our miss rate with a larger cache.

And finally, as shown from the analysis, the size of the data set is irrelevant. It doesn't matter if we're reading in 1 Kilobyte or 1 Gigabyte, the miss rate is the same.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks Stephen. This is a big help. So, I load a full block (32B) for each miss. For 0, this would be the words at 0-28. When I try to access the word at byte address 32, I again get a miss and have to load another block from memory (words 32-60) into the second cache line. Is that about right? $\endgroup$ – Victor Brunell Jul 6 '14 at 22:24
  • $\begingroup$ Yes that's right. $\endgroup$ – gardenhead Jul 6 '14 at 22:54

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.