Cache Mapping
What does it represent ?
- It tells that which word of the main memory will be placed at which location of cache memory.
Basic Idea :- Mapping between the Cache Address & the Main memory address referring to the same until of information.
Types of Mapping
1. Direct Mapping
2. Associative Mapping
3. Set-Association Mapping
Direct Mapping :-
If the ith block of main memory has to be placed at the jth block of cache memory, then
j = i mod (No. of blocks in cache)
Example :- Let us say there are 128 Blocks in cache memory, then the scenario is like :-
Main Memory Cache
0th Block → 0 mod 128 = 0th Block of Cache
1st Block → 1 mod 128
= 1st block cache
.
.
.
In direct mapping , we divide the main memory addressing space into three parts :-
- Word
- Index
- Tag
Word → Number of bits required to identify a particular word within the block
= log2 (No. of words / Block)
Index → Number of bits required to identify the block, no. in cache memory where a main memory block will be placed.
= log2 (No. of block in cache)
Example : Let there be given a 16 word 64 KW main memory & a 128 line cache. Then find the corresponding Tag, Index & word bits in Direct Mapping.
Associative Mapping:-
→ Drawbacks of Direct Mapping
- High Conflict Miss → We had to replace a cache memory block even where other blocks in the cache memory were present as empty.
Solution :- Associative Mapping
Idea : To avoid high conflict miss, any block of main memory can be placed anywhere in cache memory.
Associative Mapping Addressing Scheme
- Tag
- Word
Word Bits :- No. of bits required to identify a particular word within a 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)
Advantage :- 0 % conflict Miss occurs
Disadvantage :- Very High Tag comparisons are required.
Number of Tag comparisons = No. of Blocks inside the Cache (Entire Cache search)
Set Associative Mapping :-
- To overcome the high conflict miss in Direct Mapping
- Large Tag comparisons in case of Associative Mapping
Set Associative Mapping Concept :-
- Cache Blocks are divide into sets
- Set size is always in the power of 2 i.e if cache has 2 Blocks /Set , then it is called 2 - way Set Associative.
Similarly,
4-way Set Associative ⇒ Blocks /Set
2-way Set Associative ⇒ 2 Blocks/Set
Set Associative Addressing Scheme :-
- Tag
- Set
- Word
Word :- No. of Bits required to identify a particular word within the block = log2 (No. of Words/Block)
Set :- No. of Bit required to identify the corresponding set no. inside the cache where a Main Memory block will be placed = log2 (No. of sets in cache)
Tag :- No. of bits required to compare two blocks which belong to the same set.
Mapping Technique :-
1. If ith block of Main Memory have to be placed in jth set of Cache Memory , then
j = i mod (No. of sets in Cache)
2. A new block from Main Memory can be placed anywhere within the set.
- It tells that which word of the main memory will be placed at which location of cache memory.
Basic Idea :- Mapping between the Cache Address & the Main memory address referring to the same until of information.
Types of Mapping
1. Direct Mapping
2. Associative Mapping
3. Set-Association Mapping
Direct Mapping :-
If the ith block of main memory has to be placed at the jth block of cache memory, then
j = i mod (No. of blocks in cache)
Example :- Let us say there are 128 Blocks in cache memory, then the scenario is like :-
Main Memory Cache
0th Block → 0 mod 128 = 0th Block of Cache
1st Block → 1 mod 128
= 1st block cache
.
.
.
In direct mapping , we divide the main memory addressing space into three parts :-
- Word
- Index
- Tag
Word → Number of bits required to identify a particular word within the block
= log2 (No. of words / Block)
Index → Number of bits required to identify the block, no. in cache memory where a main memory block will be placed.
= log2 (No. of block in cache)
Example : Let there be given a 16 word 64 KW main memory & a 128 line cache. Then find the corresponding Tag, Index & word bits in Direct Mapping.
Associative Mapping:-
→ Drawbacks of Direct Mapping
- High Conflict Miss → We had to replace a cache memory block even where other blocks in the cache memory were present as empty.
Solution :- Associative Mapping
Idea : To avoid high conflict miss, any block of main memory can be placed anywhere in cache memory.
Associative Mapping Addressing Scheme
- Tag
- Word
Word Bits :- No. of bits required to identify a particular word within a 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)
Advantage :- 0 % conflict Miss occurs
Disadvantage :- Very High Tag comparisons are required.
Number of Tag comparisons = No. of Blocks inside the Cache (Entire Cache search)
Set Associative Mapping :-
- To overcome the high conflict miss in Direct Mapping
- Large Tag comparisons in case of Associative Mapping
Set Associative Mapping Concept :-
- Cache Blocks are divide into sets
- Set size is always in the power of 2 i.e if cache has 2 Blocks /Set , then it is called 2 - way Set Associative.
Similarly,
4-way Set Associative ⇒ Blocks /Set
2-way Set Associative ⇒ 2 Blocks/Set
Set Associative Addressing Scheme :-
- Tag
- Set
- Word
Word :- No. of Bits required to identify a particular word within the block = log2 (No. of Words/Block)
Set :- No. of Bit required to identify the corresponding set no. inside the cache where a Main Memory block will be placed = log2 (No. of sets in cache)
Tag :- No. of bits required to compare two blocks which belong to the same set.
Mapping Technique :-
1. If ith block of Main Memory have to be placed in jth set of Cache Memory , then
j = i mod (No. of sets in Cache)
2. A new block from Main Memory can be placed anywhere within the set.
No comments