Page 160 -

4.3 / ELEMENTS OF CACHE DESIGN 131

With associative mapping, there is flexibility as to which block to replace when
a new block is read into the cache. Replacement algorithms, discussed later in this
section, are designed to maximize the hit ratio. The principal disadvantage of asso-
ciative mapping is the complex circuitry required to examine the tags of all cache
lines in parallel.

Cache Time Analysis Simulator
SET-ASSOCIATIVE MAPPING Set-associative mapping is a compromise that ex-
hibits the strengths of both the direct and associative approaches while reducing
their disadvantages.
In this case, the cache consists of a number sets, each of which consists of a
number of lines.The relationships are

m = n * k
i = j modulo n

where
i = cache set number
j = main memory block number
m = number of lines in the cache

n = number of sets
k = number of lines in each set

This is referred to as k-way set-associative mapping. With set-associative
mapping, block B can be mapped into any of the lines of set j. Figure 4.13a illus-
j
n
trates this mapping for the first blocks of main memory.As with associative map-
ping, each word maps into multiple cache lines. For set-associative mapping, each
word maps into all the cache lines in a specific set, so that main memory block B 0
maps into set 0, and so on. Thus, the set-associative cache can be physically imple-
n
mented as associative caches. It is also possible to implement the set-associative
cache as k direct mapping caches, as shown in Figure 4.13b. Each direct-mapped
n
cache is referred to as a way, consisting of lines.The first lines of main memory
n
n
n
are direct mapped into the lines of each way; the next group of lines of main
memory are similarly mapped, and so on. The direct-mapped implementation is
typically used for small degrees of associativity (small values of k) while the asso-
ciative-mapped implementation is typically used for higher degrees of associativ-
ity [JACO08].
For set-associative mapping, the cache control logic interprets a memory
n
address as three fields: Tag, Set, and Word. The d set bits specify one of 2 d
s
sets. The s bits of the Tag and Set fields specify one of the 2 blocks of main mem-
ory. Figure 4.14 illustrates the cache control logic. With fully associative mapping,
the tag in a memory address is quite large and must be compared to the tag of
every line in the cache. With k-way set-associative mapping, the tag in a memory