replacement bits for a cache entry

	Hey Dr. Patt,

Hey Student!

	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
     that one.

  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.

Yale Patt

	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 ...>>