replacement bits for a cache entry
Hey Dr. Patt,
I'm going through the problem set and I'm having trouble with how many
replacement bits are in the tag store. I thought there were replacement
bits for each entry in the tag store,
Depends on the associativity, and depends on the implementation. So:
a. replacement bits for a direct mapped cache: I will let you answer
b. 2-way set associative: one bit per set, since there are two blocks in
a set and one must be LRU, so one bit is enough to handle the entire
c. 4-way, 8-way, etc.: the normal way to handle this is to provide LRU bits
for each entry indicating where in the LRU/MRU range the particular block
is. Recall the victim, next victim scheme where we used two bits to
indicate whether a block was a victim, a next-victim, or neither.
Recall that we can also implement replacement by looking at all elements
of the set as a whole. We showed a three-bit scheme for handling blocks
in a set. Say, the blocks in the set are A,B,C,D. One bit to tell
which is LRU between A and B, one bit to tell the same thing for C and D,
and one bit to tell LRU is one of A,B or one of C,D. Of course, this is
not REALLY LRU, but most agree it is close enough. The victim/nextvictim
scheme is also not really LRU, but again, most agree it is close enough.
We could of course do REAL LRU (no one ever does) by noting that there are
n! different orderings for the n elements of a single set, and encode those
n! ways with log (n!) bits. The problem with that is the logic to update
the ordering after each access is horrific.
As to tag store entries, for every block in the cache (in Cache_D), there is
a corresponding entry in the tag store (Cache_A) which contains all the
bookkeeping information for that specific entry. Therefore, when we evict
a block from the cache, we ONLY replace its tag store entry. ...although we
do need to update the LRU information about all the blocks in the cache.
Does this help? If still not clear, ping me again.
but then in our recitation section
we derived this equation for the size of a tag store:
tag store size = 2^(# of index bits) * (associativity *( # of tag bits +
dirty bit + valid bit + ... ) + replacement bits)
(I'm sorry, this is written poorly)
Tell me when I'm wrong... I think this means that there are only
replacement bits for each indexed row of the tag store. So, if we need to
bring in a new block we evict the entire row of the tag store. And... this
is because for every row, all but one entry is there to just say that the
other blocks that are mapped to that row via the index bits are NOT
located in the cache. Can you tell me if this is correct?
<<name withheld to protect ...>>