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

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 specified set first, 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 2 above requires matching the tag
field of the address with each and every entry in the tag memory for the specified set.
Such a search is performed in parallel (associatively) over the set, hence the name,
set-associative mapping. The hardware overhead required to performing the associ-
ative search within a set in order to find a match between the tag field and the tag
memory is not as complex as that used in the case of the fully associative technique.
The set-associative-mapping technique is expected to produce a moderate cache
utilization efficiency, that is, not as efficient as the fully associative technique and
not as poor as the direct technique. However, the technique inherits the simplicity
of the direct mapping technique in terms of determining the target set.
An overall qualitative comparison among the three mapping techniques is shown
in Table 6.2. Owing to its moderate complexity and moderate cache utilization, the
set-associative technique is used in the Intel Pentium line of processors.
The discussion above shows how the associative-mapping and the set-associative
techniques answer the question about the placement of the incoming main memory
block in the cache. The other important question that was posed at the beginning of
the discussion on cache memory is that of replacement. Specifically, upon encoun-
tering a totally filled cache while a new main memory block has to be brought, which
of the cache blocks should be selected for replacement? This is discussed below.

6.2.6. Replacement Techniques

A number of replacement techniques can be used. These include a randomly selected
block (random selection), the block that has been in the cache the longest ( first-in-
first-out, FIFO), and the block that has been used the least while residing in the
cache (least recently used, LRU).
Let us assume that when a computer system is powered up, a random number
generator starts generating numbers between 0 and (N 2 1). As the name indicates,

TABLE 6.2 Qualitative Comparison Among Cache Mapping
Techniques

Expected
cache
utilization

Mapping
technique

Associative
tag search

Replacement
technique Simplicity

Direct Yes None Low Not needed

Associative No Involved High Yes

Set-associative Moderate Moderate Moderate Yes