Page 162 -

4.3 / ELEMENTS OF CACHE DESIGN 133

s + w

Cache Main memory
Memory address Tag Data B
Tag Set Word 0
F 0
B 1
s – d d w F 1
Set 0

s – d F k 1
F k s + w
B j

Compare F k i Set 1

(Hit in cache) F 2k 1
1 if match
0 if no match

0 if match
1 if no match
(Miss in cache)
Figure 4.14 K-Way Set Associative Cache Organization

• Number of lines in cache = m = k =n k * 2 d
• Size of cache = k * 2 d w words or bytes
• Size of tag = (s - d) bits

Example 4.2c Figure 4.15 shows our example using set-associative mapping with two
lines in each set, referred to as two-way set-associative. The 13-bit set number identifies a
unique set of two lines within the cache. It also gives the number of the block in main
13
memory, modulo 2 . This determines the mapping of blocks into lines. Thus, blocks
000000, 008000, Á , FF8000 of main memory map into cache set 0. Any of those blocks
can be loaded into either of the two lines in the set. Note that no two blocks that map into
the same cache set have the same tag number. For a read operation, the 13-bit set number
is used to determine which set of two lines is to be examined. Both lines in the set are ex-
amined for a match with the tag number of the address to be accessed.

In the extreme case of =n m, k = 1, the set-associative technique reduces to
direct mapping, and for =n 1, k = m, it reduces to associative mapping.The use of
two lines per set ( =n m/2, k = 2) is the most common set-associative organization.