Review of Memory Hierarchy - Computer Architecture: A Quantitative Approach - page 555

Q2: How Is a Block Found If It Is in the Cache?
Caches have an address tag on each block frame that gives the block address. The tag of every
cache block that might contain the desired information is checked to see if it matches the block
address from the processor. As a rule, all possible tags are searched in parallel because speed
is critical.
There must be a way to know that a cache block does not have valid information. The most
common procedure is to add a valid bit to the tag to say whether or not this entry contains a
valid address. If the bit is not set, there cannot be a match on this address.
Before proceeding to the next question, let's explore the relationship of a processor address
to the cache. Figure B.3 shows how an address is divided. The first division is between the
block address and the block offset . The block frame address can be further divided into the tag
ield and the index field. . The block offset field selects the desired data from the block, the index
field selects the set, and the tag field is compared against it for a hit. Although the comparison
could be made on more of the address than the tag, there is no need because of the following:
■ The offset should not be used in the comparison, since the entire block is present or not,
and hence all block offsets result in a match by definition.
■ Checking the index is redundant, since it was used to select the set to be checked. An ad-
dress stored in set 0, for example, must have 0 in the index field or it couldn't be stored in
set 0; set 1 must have an index value of 1; and so on. This optimization saves hardware and
power by reducing the width of memory size for the cache tag.
FIGURE B.3 The three portions of an address in a set associative or direct-mapped
cache . The tag is used to check all the blocks in the set, and the index is used to select the
set. The block offset is the address of the desired data within the block. Fully associative
caches have no index field.
If the total cache size is kept the same, increasing associativity increases the number of
blocks per set, thereby decreasing the size of the index and increasing the size of the tag. That
is, the tag-index boundary in Figure B.3 moves to the right with increasing associativity, with
the end point of fully associative caches having no index field.
Q3: Which Block Should Be Replaced on a Cache Miss?
When a miss occurs, the cache controller must select a block to be replaced with the desired
data. A benefit of direct-mapped placement is that hardware decisions are simplified—in fact,
so simple that there is no choice: Only one block frame is checked for a hit, and only that block
can be replaced. With fully associative or set associative placement, there are many blocks to
choose from on a miss. There are three primary strategies employed for selecting which block
to replace:
■ Random —To spread allocation uniformly, candidate blocks are randomly selected. Some
systems generate pseudorandom block numbers to get reproducible behavior, which is
particularly useful when debugging hardware.