Home » Operating Systems

Working and implementation of Direct Mapped Cache

In this article, we are going to learn about the working of Direct mapped Cache with a diagram. After we will discuss the need for the replacement algorithm in the direct mapping and steps of implementation of Direct mapped Cache.
Submitted by Monika Jha, on November 19, 2019

Prerequisites: Memory mapping and its types

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,

Direct Mapped Cache


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.

Steps to implement direct memory 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,

  1. Size of cache memory
  2. 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:

ADVERTISEMENT
ADVERTISEMENT




Comments and Discussions!




Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.