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

The direct-mapping technique answers not only the placement of the incoming main
memory block in the cache question, but it also answers the replacement question.
Upon encountering a totally filled cache while a new main memory block has to be
brought, the replacement is trivial and determined by the equation j ¼ i mod N.
The main advantages of the direct-mapping technique is its simplicity measured
in terms of the direct determination of the cache block; no search is needed. It is also
simple in terms of the replacement mechanism. The main disadvantage of the tech-
nique is its expected poor utilization of the cache memory. This is represented in
terms of the possibility of targeting a given cache block, which requires frequent
replacement of blocks while the rest of the cache is not used. Consider, for example,
the sequence of requests made by the processor for elements held in the main
memory blocks 1, 33, 65, 97, 129, and 161. Consider also that the cache size is
32 blocks. It is clear that all the above blocks map to cache block number 1. There-
fore, these blocks will compete for that same cache block despite the fact that the
remaining 31 cache blocks are not used.
The expected poor utilization of the cache by the direct mapping technique is
mainly due to the restriction on the placement of the incoming main memory
blocks in the cache (the many-to-one property). If such a restriction is relaxed,
that is, if we make it possible for an incoming main memory block to be placed
in any empty (available) cache block, then the resulting technique would be so flex-
ible that efficient utilization of the cache would be possible. Such a flexible tech-
nique, called the Associative Mapping technique, is explained next.

Fully Associative Mapping According to this technique, an incoming main

memory block can be placed in any available cache block. Therefore, the address
issued by the processor need only have two fields. These are the Tag and Word
fields. The first uniquely identifies the block while residing in the cache. The
second field identifies the element within the block that is requested by the pro-
cessor. The MMU interprets the address issued by the processor by dividing it
into two fields as shown in Figure 6.7. The length, in bits, of each of the fields in
Figure 6.7 are given by:

1. Word field ¼ log 2 B, where B is the size of the block in words

2. Tag field log 2 M, where M is the size of the main memory in blocks

3. The number of bits in the main memory address ¼ log 2 (B M)

¼

It should be noted that the total number of bits as computed by the first two equations
should add up to the length of the main memory address. This can be used as a check
for the correctness of your computation.

Figure 6.7 Associative-mapped address fields