Recent Post

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.

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