Hello cengineer1,
I'm basing my answer to this problem on my understanding of set
associative cache as learned from this useful course URL:
http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/
If I understand the terminology of your question correctly, each set
in the cache contains three slots (as the term is used in the
aforementioned notes), and each slot is the size of 3 words. (I'm
assuming that "blocks" in your question is not another term for
"slots" as used above, because then the question description is
redundant.)
So our empty cache, with unused slots as underscores, starts out like this:
_, _, _| _, _, _| _, _, _|
The one thing your question does not specify is how we associate
addresses with a particular set. Given that your stated addresses
range from 0 to 46, we can't just take the first decimal digit, as we
only have three sets to choose from. We could convert to binary and
take two digits in the middle, but with 3 slots per set and 3 word
blocks in each slot, that just doesn't map out nicely. We could map
0-19 for the first set, 20-39 for the second, 40-59 for the third, but
that will cause a lot of collisions in the first set based on your
address hits. However, we need our set mapping to divide nicely
into blocks of 3 words each. Let's say that set one is 0-17, set two
is 18-35, set three is 36-53.
So our first address lookup, address 1, isn't found, because the cache
is empty of course. We load the 3-word block that contains the address
into set one, and have our pick of three slots, so we'll toss it into
the first one.
0-2, _, _| _, _, _| _, _, _|
Address 16 isn't found in the cache either, so we load it into set one:
0-2, 15-17, _| _, _, _| _, _, _|
Address 8 isn't found, so we load it:
0-2, 15-17, 6-8 | _, _, _| _, _, _|
Address 0 is found in set one, hooray we've saved time! No change to the cache.
We look for address 22 in set two, based on our associative scheme,
and do not find it, so we load it there:
0-2, 15-17, 6-8 | 21-23, _, _ | _, _, _ |
We look for address 19 in set two, and do not find it, so we load it up:
0-2, 15-17, 6-8 | 21-23, 18-20, _ | _, _, _ |
We look for address 12 in set one, and it's not there. We want to
load it up, but we've got to kick another 3-word block out of a slot
first. Here's another design choice: are we doing first-in-first-out
(FIFO), least recently used, or some other wacky scheme? I like least
recently used, so let's boot out the second slot:
0-2, 12-14, 6-8 | 21-23, 18-20, _ | _, _, _ |
Aww geez, we just booted out the next address we were looking for. Oh
well, them's the breaks. Moving right along, we boot out the third
slot in set one and load it up there:
0-2, 12-14, 15-17 | 21-23, 18-20, _ | _, _, _ |
Address 46 is not yet loaded in set three, so we'll drop it in:
0-2, 12-14, 15-17 | 21-23, 18-20, _ | 45-47, _, _ |
Address 10 isn't in set one - collision again. Least recently used is
now the first slot, so let's replace it:
9-11, 12-14, 15-17 | 21-23, 18-20, _ | 45-47, _, _ |
Address 32 isn't in our cache either. Set two still has a vacant
slot, though, so no collision.
9-11, 12-14, 15-17 | 21-23, 18-20, 30-32 | 45-47, _, _ |
We look for address 18 in our cache in set two - success! No change to the cache.
Address 14 is found in set one, so again no change (and we do a little
happy dance because we've saved some time).
We look for address 32 in set two, and again we find it there. No change.
Address 9 is found in set one, success again, and no change. Likewise
for address 20 (hey, we're on a roll here, finally).
Address 0 is not found in set one. Least recently used is the second slot:
9-11, 0-2, 15-17 | 21-23, 18-20, 30-32 | 45-47, _, _ |
And that's the final state of our cache!
Now keep in mind, there were two design decisions made along the way
here which could have played out differently. Choosing how we map our
association of address ranges to cache sets will make a big
difference. In fact, the choice I did make is not analogous to how
this is usually done in hardware, but is sort of bad practice.
Hardware designers know that memory use tends to get grouped into a
region of memory, just as we had many more addresses in the lower
ranges than we did in the upper range. Our third set within the cache
went almost entirely unused! When using binary, the middle digits are
generally chosen to decide set association for this reason. We
could've done that here and still mapped things cleanly by using a
base 3 number system, I suppose, but that's sort of painful to spend
time figuring out!
The other key decision left open by your question was how we choose
which slot within a set to kick out of the cache. FIFO would have
worked just fine, and who knows, there might be some other scheme
which would work even better. Least recently used isn't a bad choice,
though.
Search strategy:
3 way set associative cache
References:
Set Associative Cache (course notes for Computer Organization,
cmsc311, University of Maryland Department of Computer Science)
http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Memory/set.html
http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/
I hope this helps your understanding of set associative caches, it
certainly did mine! Have a great day,
- josh_g-ga |
