Calculating miss rates of word-addressable and direct-mapped cache

Question Detail: 

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!

Asked By : Victor Brunell

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28248

Answered By : gardenhead

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 28 we will again get a miss and the process repeats. Thus, our miss rate is 1/8.

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.