Memory System Design I - Fundamentals of Computer Organization and Architecture - page 118

3. Among the elements contained in the cache block, the targeted element can be
selected using the Word field.
4. If in step 2, no match is found, then this indicates a cache miss. Therefore, the
required block has to be brought from the main memory, deposited in the first
available cache block, and the targeted element (word) is made available to
the processor. The cache Tag memory and the cache block memory have to
be updated accordingly.

It should be noted that the search made in step 1 above requires matching the tag
field of the address with each and every entry in the tag memory. Such a search, if
done sequentially, could lead to a long delay. Therefore, the tags are stored in an
associative (content addressable) memory. This allows the entire contents of the
tag memory to be searched in parallel (associatively), hence the name, associative
mapping.
It should be noted that, regardless of the cache organization used, a mechanism is
needed to ensure that any accessed cache block contains valid information. The val-
idity of the information in a cache block can be checked via the use of a single bit for
each cache block, called the valid bit. The valid bit of a cache block should be
updated in such a way that if valid bit ¼ 1, then the corresponding cache block car-

ries valid information; otherwise, the information in the cache block is invalid.
When a computer system is powered up, all valid bits are made equal to 0, indicating
that they carry invalid information. As blocks are brought to the cache, their statuses
are changed accordingly to indicate the validity of the information contained.
The main advantage of the associative-mapping technique is the efficient use of
the cache. This stems from the fact that there exists no restriction on where to place
incoming main memory blocks. Any unoccupied cache block can potentially be
used to receive those incoming main memory blocks. The main disadvantage of
the technique, however, is the hardware overhead required to perform the associat-
ive search conducted in order to find a match between the tag field and the tag
memory as discussed above.
A compromise between the simple but inefficient direct cache organization and
the involved but efficient associative cache organization can be achieved by con-
ducting the search over a limited set of cache blocks while knowing ahead of
time where in the cache an incoming main memory block is to be placed. This is
the basis for the set-associative mapping technique explained next.

Set-Associative Mapping In the set-associative mapping technique, the cache

is divided into a number of sets. Each set consists of a number of blocks. A given
main memory block maps to a specific cache set based on the equation
s ¼ i mod S, where S is the number of sets in the cache, i is the main memory
block number, and s is the specfic cache set to which block i maps. However, an
incoming block maps to any block in the assigned cache set. Therefore, the address
issued by the processor is divided into three distinct fields. These are the Tag, Set,
and Word fields. The Set field is used to uniquely identify the specific cache set