Page 154 -

4.3 / ELEMENTS OF CACHE DESIGN 125

Example 4.2 For all three cases, the example includes the following elements:
• The cache can hold 64 KBytes.
• Data are transferred between main memory and the cache in blocks of 4 bytes each.
This means that the cache is organized as 16K = 2 lines of 4 bytes each.
14
• The main memory consists of 16 Mbytes, with each byte directly addressable by a
24-bit address (2 24 = 16M). Thus, for mapping purposes, we can consider main mem-
ory to consist of 4M blocks of 4 bytes each.

DIRECT MAPPING The simplest technique, known as direct mapping, maps each
block of main memory into only one possible cache line. The mapping is ex-
pressed as
i = j modulo m
where
i = cache line number
j = main memory block number
m = number of lines in the cache
Figure 4.8a shows the mapping for the first m blocks of main memory. Each
block of main memory maps into one unique line of the cache. The next m blocks
of main memory map into the cache in the same fashion; that is, block B m
of main memory maps into line L of cache, block B m 1 maps into line L , and
1
0
so on.
The mapping function is easily implemented using the main memory address.
Figure 4.9 illustrates the general mechanism. For purposes of cache access, each
main memory address can be viewed as consisting of three fields. The least signifi-
cant w bits identify a unique word or byte within a block of main memory; in most
contemporary machines, the address is at the byte level.The remaining s bits specify
s
one of the 2 blocks of main memory. The cache logic interprets these s bits as a tag
of s - r bits (most significant portion) and a line field of r bits.This latter field iden-
r
tifies one of the m = 2 lines of the cache.To summarize,
• Address length = (s + w) bits

• Number of addressable units 2 s w words or bytes
w
• Block size = line size = 2 words or bytes
2 s+w
• Number of blocks in main memory = = 2 s
2 w
• Number of lines in cache = m = 2 r
• Size of cache = 2 r w words or bytes
• Size of tag = (s - r) bits