Calculate a miss rate for a direct mapped cache

Question

Assume this is a MIPS processor with a 32 bit word size and addresses are word aligned.

The question is the following:

Calculate a miss rate for a direct mapped cache with a size (capacity) of 16 words and block size of 4 words. Assume cache is initially empty. The code is as follows:

lw $s0, 0($0)
lw $s0, 0x10($0)
lw $s0, 0x20($0)
lw $s0, 0x30($0)
lw $s0, 0x40($0)

I do have an answer to the question, it is 2/5 = 40%, but I get it to be a 100%. I'm not sure what I'm missing. Can anyone provide an explanation to how to calculate a miss rate?

Here is my reasoning

This is a 16 word direct mapped cache with 4 words per block. Meaning there are 4 sets, 16/4 = 4. Since addresses are word aligned and the word size is 4 bytes (32 bits), lower two bits of the address don't matter. Since there are 4 words per block, it would mean that the next 2 bits are needed to determine the block offset, and since there are 4 sets, the next two bits are needed to determine the set number. Whatever is left is used for the tag.

                   -----------------------------------------------------
address           |    tag    | set number | block offset | byte offset |
                  |-----------|------------|--------------|-------------|
bit number        | 31      6 | 5        4 | 3          2 | 1         0 |
                   -----------------------------------------------------

Address 0x0 maps to set 0. Since block size is 4 words the CPU would need to load 4 words, at addresses 0x0, 0x4, 0x8, 0xC.

Address 0x10, maps to set 1. The CPU needs to load 4 words, at addresses 0x10, 0x14, 0x18, 0x1C

The same happens for address 0x20, 0x30, and 0x40. What am I missing?

Any help is appreciated.

That's correct, I'm assuming word addressing. Would you mind expanding on the answer. I'm not quite clear. — flashburn

Stack Player Stack Player · Accepted Answer · 2014-05-09T07:36:09

Your analysis is correct for as far as I know all will be misses in the given code, but I think what is meant by miss rate is a general probability for cache misses...otherwise 100% seems correct for this specific example (also assuming you are not missing anything from the problem's given...like some additional "intelligence" added to the cache controller)

Calculate a miss rate for a direct mapped cache

1 Answers