Introduction:-
                         When a Cache MISS occurs, that means when the CPU doesn’t find the required instructions in the cache memory, the CPU tries to fetch the instruction from primary memory. 

As the locality of reference is applicable in the computer system, instead of fetching a single instruction a group of instruction are sent from primary memory to cache. 

These groups of instructions are called blocks.

Entire primary memory is divided into equal sized blocks. 

Cache memory is also divided into same-sized blocks. 

For placing primary memory blocks into cache memory blocks, 3 different mapping techniques are available.

Cache memory mapping techniques:

i) Direct Mapping
ii) Associative Mapping
iii) Set – Associative Mapping

Direct Mapping:-
                                 The main memory is divided into 4096 block which contains 16 location each.
4096= 22  * 210 * 24  .

THUS IT GIVES ADDRESS BIT OF 2+10+4 =16

In this block J of the main memory maps on to block J modulo 128 of the cache. 

Thus main memory blocks 0,128,256,….is loaded into cache is stored at block 0. 

Block 1,129,257,….are stored at block 1 and so on.
Memory address is divided into 3 fields, the lower 4-bits selects one of the 16 words in a block. When new block enters the cache, the 7-bit cache block field determines the cache positions in which this block must be stored. The higher order 5-bits of the memory address of the block are stored in 5 tag bits associated with its location in cache.  They identify which of the 32 blocks that are mapped into this cache position are currently resident in the cache.

Associative Mapping:-
                                        An incoming main memory block can be placed in any available cache block.
Therefore, the address issued by the processor need only have two fields. These are the Tag and Word fields.  Tag field uniquely identifies the block while residing in the cache.
Word field identifies the element within the block that is requested by the processor.
The length, in bits, of each of the fields are given by:
Word field=log2B, where B is the size of the block in words.
Tag field=log2M, where M is the size of the main memory in blocks.
The number of bits in the main memory address=log2(B*M).
The MAR holds the address of main memory. In associative mapping there is a new memory content addressable memory. Unlike direct memory, main memory any block can be placed into any block in cache. In CAM there is so many location which contains block number of main memory and the respective block number in cache memory. CAM allows parallel searching so the searching of many location can be done very fast.

The major drawbacks of these two mapping techniques are:
In direct mapping there is no flexibility. The block 0 of main memory has to be placed in block 0 of the cache memory. 

If the 128th block of the main memory has to be placed in cache memory then the block address of the cache has to be 128 mod 128 = 0.

When 128th block is transferred from main memory to cache the 0th block (in cache) which was containing 0th block of main memory is over written and the 128th block (of main memory) would replace the 0th block of cache. 

The previous data would be lost.

In associative mapping any block of the main memory is mapped into any available cache block.

CAM is an expensive memory which is used to store the tag address and the cache block that has been associated with it.
So the use of associative memory increases the cost drastically although it provides flexibility.

Set Associative Mapping:-
                                                It is the combination of direct and associative mapping technique.
Cache blocks are grouped into sets And mapping allow block of main memory reside into any block of a specific set. Hence contention problem of direct mapping is eased , at the same time , hardware cost is reduced by avoiding the use of larger CAM. For a cache with two blocks per set. 
In this case, memory block 0, 64, 128,…..,4032 map into cache set 0 and they can occupy any two block within this set. Having 64 sets means that the 6 bit set field of the address determines which set of the cache might contain the desired block.
The tag bits of address must be associatively compared to the tags of the two blocks of the set to check if desired block is present. This is two way associative search.

In this example the set is made by using two blocks per set. Thus 128 block of the cache memory has been reduced as 64 sets. Thus in main memory the blocks are being arranged in set form as shown in the figure. While arranging it yields 64 tags which requires 6 bits address line to be addressed and 64 set requires again 6 bits to be addressed. Thus the 12 bits are divided into 6 bit tag address and 6 bits set address. 
The 6 bit tag has been used in CAM word and the other field would log2 N where N here is 2. since 2 blocks are combined for a set. Since N=2 the CAM word will produce 1 bit info and the 6 bit set address is used to find the set in cache memory giving 7 bit Cache address and 4 bit offset.