In the introduction to cache we saw the need for the cache memory and some understood some important terminologies related to it.
The next question is how is a block found in the cache, the cache memory is always smaller than main memory so how is it decided as to which block of memory can be placed where in the cache, and when the processor tries to read/write to a memory location how is it decided whether the block is present in cache or not. These issues are addressed in this article, which is all about cache mapping.
Cache mapping as the name suggests deals with mapping the main memory locations/blocks to the cache blocks.
There are three main forms or mapping
1.Direct Mapping
2.Fully associative Mapping
3. Set associative Mapping.
To get an understanding of these various mapping techniques let us take and example.
Let us assume a system with a main memory of 32 blocks and a cache memory of 8 blocks.
The addresses of main memory blocks range from 0000 to 11111.
The addresses of cache memory blocks range from 000 to 111.
Direct mapping :
In direct mapping every block in the main memory can be placed in only one block in the cache memory. For eg block0 of main memory will always be placed in block0 of cache memory.
The decision as to which bock is placed where is taken based on the formula
(Block address in main memory ) mod (Number of blocks in cache)
For eg: The block number 20 of main memory in our example system can only be mapped to block number 4 in the cache because 20 % 8 = 4
The figure below depicts the mapping pictorially.
Fully Associative:
In the case of fully associative any block in main memory can be mapped to any block in the cache memory. That is there is no restriction on the mapping of the blocks.
For eg: The block1 of the main memory can be mapped to block0 or block1 or block2 .... or block7 any of them.
The figure below depicts the fully associative mapping
Set Associative :
The set associative is in between direct and full associative mapping. In this mapping the cache is divided into sets with each set consisting of same number of blocks. For eg in our example system we can split the 8 block cache into 4 sets with each set having 2 blocks.
Every block in the main memory will be mapped to one set. The block can be placed in any block with in the set. The mapping is arrived at using the formula
(Main memory block number/address ) mod (Number of sets in the cache ).
For eg the block10 of the main memory in our example system will be mapped to set2 in the cache because
10%4 =2
The figure below shows the set associative mapping
If each set has "n" blocks then the cache is called n-way set associative, in out example each set had 2 blocks hence the cache will be called 2-way set associative.
The next question that arises now is how does the system figure out which cache block maps to which block in the main memory as it is evident that each cache block maps to multiple blocks in the main memory.
The next question is how is a block found in the cache, the cache memory is always smaller than main memory so how is it decided as to which block of memory can be placed where in the cache, and when the processor tries to read/write to a memory location how is it decided whether the block is present in cache or not. These issues are addressed in this article, which is all about cache mapping.
Cache mapping as the name suggests deals with mapping the main memory locations/blocks to the cache blocks.
There are three main forms or mapping
1.Direct Mapping
2.Fully associative Mapping
3. Set associative Mapping.
To get an understanding of these various mapping techniques let us take and example.
Let us assume a system with a main memory of 32 blocks and a cache memory of 8 blocks.
The addresses of main memory blocks range from 0000 to 11111.
The addresses of cache memory blocks range from 000 to 111.
Direct mapping :
In direct mapping every block in the main memory can be placed in only one block in the cache memory. For eg block0 of main memory will always be placed in block0 of cache memory.
The decision as to which bock is placed where is taken based on the formula
(Block address in main memory ) mod (Number of blocks in cache)
For eg: The block number 20 of main memory in our example system can only be mapped to block number 4 in the cache because 20 % 8 = 4
The figure below depicts the mapping pictorially.
In the case of fully associative any block in main memory can be mapped to any block in the cache memory. That is there is no restriction on the mapping of the blocks.
For eg: The block1 of the main memory can be mapped to block0 or block1 or block2 .... or block7 any of them.
The figure below depicts the fully associative mapping
Set Associative :
The set associative is in between direct and full associative mapping. In this mapping the cache is divided into sets with each set consisting of same number of blocks. For eg in our example system we can split the 8 block cache into 4 sets with each set having 2 blocks.
Every block in the main memory will be mapped to one set. The block can be placed in any block with in the set. The mapping is arrived at using the formula
(Main memory block number/address ) mod (Number of sets in the cache ).
For eg the block10 of the main memory in our example system will be mapped to set2 in the cache because
10%4 =2
The figure below shows the set associative mapping
If each set has "n" blocks then the cache is called n-way set associative, in out example each set had 2 blocks hence the cache will be called 2-way set associative.
The next question that arises now is how does the system figure out which cache block maps to which block in the main memory as it is evident that each cache block maps to multiple blocks in the main memory.
very helping
ReplyDelete