ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

Cache Mapping and their types

In this article, we are going to discuss the cache mapping and also discuss cache mapping in computer organization and architecture/operating system.
Submitted by Prerana Jain, on August 10, 2020

  • Main memory is divided into frames in O.S. but there will call it to block so 1 frame of main memory in OS =1 block of main memory in.
  • The cache is also divided into some size blocks called lines. 1 block of main memory = 1 line in the cache.
  • Blocks are further divided into wards.
  • We use the notation 1 word =1 byte.
  • K = m % n
  • M is the main memory block no. of cache lines are n then mth block will be present in the kth line of cache.

Types of mapping

There are mainly three types of mapping,

  1. Direct Mapping
  2. Associate Mapping
  3. Set Associate Mapping

1) Direct Mapping

In a direct mapping scheme, the main memory blocks are directly mapped onto a particular cache memory line. It is also known as many to mane mapping.

Eg- In the given example, the 15 blocks of the main memory will be mapped into the cache in such a way.

Now further analyzing this structure we will find out that the 6-bit address generated by CPU is now divided into:-

The block number is further divided into parts.

Tag and Line Number:

  • The line number will specify at which line in the cache is the data present.
  • The tag will specify the location in the cache that needs to be searched.
Cache Mapping and their types (1)

Architecture of direct mapping

  • If we have 'n' lines in the cache, then n*1 multiple is required.
  • If the tag size is 'n' bits then 'n' number of the comparator is required.
  • If tag size is 'n' bits then 'n' numbers of the multiplexer are required.

Advantages:

  • Direct addressing is faster as the time required to access is less.
  • The hardware cost of direct addressing is less.

Disadvantages:

The main disadvantage of direct mapping is conflict is a miss.

Example: If main memory size 32 GB, cache size 32KB block size 1 KB then how to find tag bit and tag directory size.

Main memory= 32GB
Physical address = 2^30. 2^5 = 35bit
Block size = 1KB, block offset 2^10 = 10 bit
Line Number = cache size/block size
= 32kb/ 1 kb = 2^5 = 5 bits
Then frame all these values in frame or block
Cache Mapping and their types (2)

2) Associate Mapping

  • To overcome the problem of conflict miss in the direct mapping, we have associate mapping.
  • A block of main memory can be mapped to any freely available cache lines. This makes fully associate mapping more flexible than direct mapping.
  • A replacement algorithm is needed to replace a block if the cache is free.
  • It is also known as many to many mapping.
  • In fully associate mapping, we only have two fields Tag/ Block number field and a block offset field.
  • Here the no. of bit in tag = no. of bits to require to represent block number.

Hardware architecture:

  • If we have 'n' line in the cache then 'n' no. of the comparator are required.
    Set of comparator = size of the tag.
  • If we have 'n' tag then we require 'n' bit comparator.

Disadvantage:

  • Hardware cost is high as compared to direct mapping.
  • Tag directory size is more as compared to direct mapping.

3) Set Associate Mapping

  • In k way set associate mapping block of cache/ cache lines are grouped into sets where each set contains 'k' no. of lines.
  • A particular block of main memory can map to only one particular set of the cache. However which that cache, the memory block can map to any freely available cache line.
  • The physical address for the k-way set associate memory is divided as

Formulas:

  • Number of lines in cache = cache size/block size
  • Number of sets = line number/ set size in terms of no of the cache line.
Cache Mapping and their types (3)

ADVERTISEMENT



ADVERTISEMENT



Comments and Discussions

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

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.