Explain Direct-Mapping Cache Organization with diagram-Solution

Question:

Explain Direct-Mapping Cache Organization with diagram.

Solution:

DIRECT MAPPING 

The simplest technique, known as direct mapping, maps each block of main memory into only one possible cache line. The mapping is expressed as,

i = j modulo m

Where,
i  = cache line number
j  = main memory block number
m = number of lines in the cache

Figure 1 shows the mapping for the first m blocks of main memory.

Figure-1-m blocks of main memory

Each block of main memory maps into one unique line of the cache.The next 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 so on.

The mapping function is easily implemented using the main memory address.
Figure 2 illustrates the general mechanism.




For purposes of cache access, each main memory address can be viewed as consisting of three fields. The least significant 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 one of the 2^s 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 identifies one of the m = 2^r lines of the cache.To summarize,

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




Tags: Computer Organization and Architecture,  Direct-Mapping Cache Organization, Direct mapping example, Cache Organization with diagram-Solution, mapping functions