CODEWITHSUNDEEP
cachingmemorycpu-architecture
rpbudd
rpbudd

Reputation: 79

Cache hit rate for a set-associative cache: I don't understand this diagram

The title may not be very good but I couldn't find a better one.

We had homework to do and I didn't hand it in because I didn't understand it. Now because it's over, we got the solutions... And now I'm trying to understand the task using the solutions because trying to understand the complicated script of our professor is a waste of time for me.

The task:

We have a direct mapped cache with following access frequency on main memory blocks:

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

What's the hitting quote (aka hit rate) if the cache is a set-associative cache with set size 4 and FIFO?

From my last question about direct-mapped caches, I learned how to count the hit quote and wanted say thank you very much for it by the way. My only problem for this is that I don't understand how the numbers are placed in the table like that.

I thought like programming maybe: 0-3 is array1 and other 0-3 is array2. We take first number of the cache, 2 and put it in array1 so it is in array1[0]. Then we do same for the next number, take 5 and put it in array2[0]. Now take next number 0 and put in array[1].

But as it seems the pattern is wrong, it's correct till line 4 of table but then it's wrong...

Why are the numbers placed like that in the table?

Solution: enter image description here

Upvotes: 2

Views: 654

Answers (1)

Kaz
Kaz

Reputation: 58578

You are probably wondering why the numbers don't line up with the addresses, as in the direct mapped case. What is going on in this diagram is that the items are placed into the sets left to right, that is all, because the sets are initially empty. The values 2, 0, 10 and 8 map to the leftmost set. The 2 appears first so it is in the leftmost column. Then 0 is placed in the next available position. 2 occurs again, and that is a "hit" indicated by the parentheses. Then 10 occurs and goes into the third spot. 8 goes to the fourth spot, and the cache block is now full. 0 recurs, and there is a hit, since it is still in the cache, in the second spot. Now 4 occurs. The cache set is full: something has to be kicked out. The 2 is kicked out (possibly due a least-recently-used (LRU) replacement policy) and replaced by 4. That is why the 4 is in the leftmost column; it has replaced the 2. Now 2 occurs again and is no longer in the cache, since it was just kicked out. Now the least recently used cache item is 0, so it is kicked out and 2 now lives in the second spot.

Note that real four-way set-associative caches don't always use a full block-wide LRU replacement policy due to some further simplifications to speed them up.

And, by the way, the addresses are distributed into the sets according to simple modulo 4. It is not the case that even addresses go to the left set and odd to the right:

    set 0             set 1
0   1   2   3  |   0   1   2   3    <-   addr modulo 4
---------------+-----------------
0   1   2   3  |   4   5   6   7    <-   full addr
8   9  10  11  |  12  13  14  15

As you can see, this is consistent with what is in the table; except of course that the addresses don't match their modulo 4 position: they are given an arbitrary spot in each set based on the replacement policy.

Upvotes: 3

Related Questions