Determine cache miss rate for a code snippet

Question

I am preparing for an upcoming exam and I was having trouble with this problem:

direct mapped cache of size 64K with block size 16 bytes. Cache starts empty

What is the cache miss rate if...

1. ROWS = 128, COLS = 128
2. ROWS = 128 and COLS = 192
3. ROWS = 128 and COLS = 256

[solution: page 5 http://www.inf.ethz.ch/personal/markusp/teaching/263-2300-ETH-spring11/midterm/midterm.pdf ]

I was confused about how they got "the cache stores 128 x 128 elements". I thought the cache size was 64K (2^16).

Also, can someone explain how to approach each question? My professor had some formula to calculate the number of accesses in each block: block size/stride, but it doesn't seem to work here.

Answer 1

As far as I understand; in case 1, both src and dst matrices are of 64kb size (128 * 128 * 4 bytes); since the cache is directly mapped and has a size of 64kb; the entries of src & dst of the same indexes will have to be mapped to the same location in the cache (since (0+i mod)64 = (64+i mod)64) at the same time to be used in the line

dest[i][j]=src[i][j]

Therefore you have 100% miss rate; The same is applied to case 3 since the new size is a multiple of 64kb (128 * 256 * 4), so it doesn't make any difference;

But for case 2; the size of the matrices becomes 96 kb (128 * 192 *4 bytes); so now both src & dst may be loaded at the same time and you will have a lower miss rate.