How exactly to count the hit rate of a direct mapp

Question

We got a cache given with 8 frames and it's directly mapped. Following access sequence on main memory blocks has been observed:

2 5 0 13 2 5 10 8 0 4 5 2

Count the hit rate of this organized cache.

Solution:

I understand how and why the numbers are placed in the table like that. But I don't understand why 2 and 5 have been bold-printed and why we got hit rate of 17%.

This has been solved by our professor but I don't understand it completely.

Answer 1

I understand how and why the numbers are placed in the table like that.

So you understand which how addresses map to cache lines, and that the vertical axis is time.

But I don't understand why 2 and 5 have been bold-printed and why we got hit rate of 17%.

The table entries are bold (cache hit) when the previous access to the same cache line was to the same address. A different address that maps to the same cache line causes a cache miss (evicting the old contents).

Visually / graphically: look vertically upwards in the same column to see which data is currently hot in the cache line.

Obviously once you know how many cache hits there were, calculating the hit rate is easy.

---

Normally you should just ask your professor extremely basic questions like this. However, your diagram was really easy to understand, so it made this trivial question easy to understand and answer.

Answer 2

Like was mentioned by @Margaret Bloom in the comments, the numbers in bold refer to cache-hits. Non-bold refer to cache misses.

You might understand it better by using this simulator: cachesimulator.com

The Simulator works with WORD-instructions only, so a little conversion of your assignment need to be made in order to simulate it:

cache-size: 32 bytes (8 rows)

block-size: 4 bytes (one word per row)

associativity: 1 (direct-mapped cache)

replacement algorithm: LRU

memory size: (any number larger than (14*4) works) for example: 1024

Now since the simulator works with WORD-instructions you need to convert your access sequence by multiplying each number by 4, also, in the simulator you enter addresses in hexadecimal so after you have multiplied by 4 you convert to hexadecimal, then you get:

8 14 0 34 8 14 28 20 0 10 14 8

In the simulator you enter instructions on the form:

<operationtype><space><register><space><address>

In your case the operationtype is LOAD and the register does'nt matter. So you can use any register, for example:

LOAD 1 8
LOAD 1 14 
LOAD 1 0 
LOAD 1 34 
LOAD 1 8 
LOAD 1 14 
LOAD 1 28 
LOAD 1 20 
LOAD 1 0 
LOAD 1 10 
LOAD 1 14 
LOAD 1 8

Enter the instructions above in the text-area of the simulator and click run. You can then see the cache hits and misses in real-time and when the simulation is finnished you can analyze the results by looking at the content of the cache memory and the list of instruction-results. You can view the main-memory address that each element in the cache refers to by hovering over it.