Home » Operating System

Cache Mapping and Its Types

In this tutorial, we will learn about the cache mapping and its types. By Prerana Jain Last updated : May 08, 2023

Overview

• 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 k^th line of cache.

Types of Cache Mapping 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.

Architecture

• 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

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.

---