Direct Mapped Cache in Operating System

In this tutorial, we will learn about the working of a direct mapped cache with a diagram, the need for the replacement algorithm in the direct mapping, and the steps of implementation of a direct mapped cache. By Monika Jha Last updated : May 08, 2023

In Direct mapped cache memory, each block mapped to exactly one location in cache memory.

Working of Direct Mapped Cache

CPU generates a memory request, so the line number field of the address is used to access the particular line of the cache.
The tag field of the processor address is then compared with the tag of the line.
If the two tags match, a cache hit occurs and the desired word is found in the cache and they do not match, a cache miss occurs.
If the cache miss occurs, the desired word must be brought from the most memory.
It is then held within the cache along with the new tag substituting the previous one.

A diagram to show the implementation of direct-mapped cache as follows,

Need of Replacement Algorithm

In direct mapping, there is no requirement of any replacement algorithm.
Due to the main memory block can map only to a particular line of the cache.
Hence, the new incoming block will always replace the existing block (if any) in that particular line.

Implementation of direct mapped cache

The following are the steps to implement direct mapped cache:

Step 1

Each multiplexer reads the line range from the generated physical address victimization it's choosing lines in parallel.
To scan the line range of L bits, range of choose lines every multiplexer should have = L.

Step 2

After reading the line number, every multiplexer goes to the corresponding line within the cache memory victimization its input lines in parallel.
Number of input lines every multiplexer should have = number of lines within the cache memory.

Step 3

Each multiplexer outputs the tag bit it has selected from that line to the comparator using its output line.
The number of output lines in each multiplexer = 1.
A multiplexer will output solely one bit on the output line. So, to output the complete tag to the comparator, Number of multiplexers required = Number of bits in the tag.

Step 4

The comparator compares the tag of the generated address with the tag coming from the multiplexers.
For comparison, only one comparator is required.
Here, Size of comparator = Number of bits in the tag.
If these two tags do not match, a cache miss occurs otherwise a cache hit occurs.

Hit Latency

The time taken to search out whether or not the specified word is available within the Cache Memory or not is termed as hit latency.

For direct mapping cache: Hit latency = Multiplexer latency + Comparator latency.

Problem Based on Direct Mapped Cache

If there is a direct-mapped cache with block size 4 KB, the size of the main memory is 16 GB and there are 10 bits in the tag. Then find out,

Size of cache memory
Tag directory size

Solution

We are considering that the memory is byte addressable.
So, the number of Bits in Physical Address-
= Size of main memory
= 16 GB
= 234 bytes
Hence, Number of bits in physical address = 34 bits

Number of Bits in Block Offset-
Block size
= 4 KB
= 212 bytes
Hence, Number of bits in block offset = 12 bits

Number of Bits in Line Number-
= total num of bits in physical address – (Num of bits in tag + Num of bits in block offset)
= 34 bits – (10 bits + 12 bits)
= 34 bits – 22 bits
= 12 bits
Hence, the total number of bits in line number = 12 bits

Number of Lines in Cache-
Number of bits in line num = 12 bits
Thus, Total number of cache lines = 212 lines
 
Size of Cache Memory-
= Total numb of cache lines x Line size
= 212 x 4 KB
= 212 x 22 KB
= 214 KB
= 16 MB
Thus, Size of cache memory = 16 MB
 
Tag Directory Size-
= Num of tags x Tag size
= Num of cache lines x Num of bits in tag
= 212 x 10 bits
= 40960 bits
= 5120 bytes
Thus, size of tag directory = 5120 bytes

References

Cache Mapping and Its Types

Set-associative Mapped Cache: Working and Implementation