Abstract
In direct mapping, only one possible place in the cache is available for each block in the main memory.
In associative mapping, any place in the cache is available for each block in the main memory.
Scope
This article talks about the differences between direct and associative mapping
Definition
Cache mapping represents which word of the main memory will be placed at which location of the main memory. It represents the mapping between the cache addresses and the main memory addresses referring to the same unit of information.
There are three types of mapping
- Direct mapping
- Associative mapping
- Set associative mapping
Direct mapping :
While transferring the data from main memory to cache memory, it uses the formula KmodN to replace any line. Where K indicates main memory block no. and N indicates no. of cache lines.
In direct mapping we divide the main memory addressing space into three parts :
- Word
- Index
- Tag
| Tag | Index | Word |
Total addressing bits
Word: No. of bits required to identify a particular word within the block.
log2(No. of words / Block)
Index: No. of bits required to identify the block number in cache memory where the main memory block will be placed.
log2(No. of blocks in cache)
Example: Let there be given a 16-word 64-kw main memory and a 128 line cache. Then friend the corresponding tag, index, and word bits in direct mapping.
128 line cache implies = 128 blocks in cache
Similarly no. of blocks in main memory = 64/16
= 4*210 = 212
Also since main memory size = 64 kw = 216 w
16 bits are required to represent the address space of main memory.
Now, Index = log2(No. of blocks in cache)
= log2(128) = log227 = 7log22 = 7
Word = log2(No. of words / Block)
= log2(Block size in words)
= log216 = log224 = 4
Tag bits = Total bits - Index bit - Word bits
= 16 - 7 - 4 = 5.
The drawback of direct mapping
High conflict miss = We had to replace a cache memory block even when the other block in cache memory was present as empty. The solution to this is associative mapping.
Associative mapping :
While transferring the data from main memory to cache lines, it checks the availability of the line. If the line is free, immediately data is transferred without any formulae (rules). If the line is not available, with the help of a replacement algorithm any one of the lines is replaced by the new data.
The main idea was to avoid high conflict miss, any block of main memory can be placed anywhere in cache memory.
Associative mapping addressing scheme
| Tag | Word |
Total addressing bits
Word bits: No. of bits required to identify a particular word within the block.
log2(No. of words / Block) log2(1 block size in terms of words)
Tag bits: Used to distinguish any 2 blocks inside the cache
log2(No. of blocks in main memory)
It has zero percent conflict miss.
It requires very high tag comparisons
No. of tag comparisons = No, of blocks inside the cache (Entire cache search)
Summary
Direct mapping suffers from high conflict miss. We had to replace a cache memory block even when other blocks in the cache memory we present as empty. To avoid high conflict miss the solution is associative mapping. In this, any block of main memory can be placed anywhere in cache memory.
Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article