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,

Direct Mapping
Associate Mapping
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.

Memory Mapping and Its Types

Direct Mapped Cache: Working and Implementation