Fully Associative Mapping

“Each memory block is mapped to any line of cache”

Fully associative mapping resolves the issue of conflict miss. Mean to say any block of main memory can come in any line of cache memory. For example, B0 can come in L1, L2, L3, and L4 and the same case for other all blocks. In this way the chance of cache hit are increased.

Let suppose there is a Main Memory (RAM) of size 128 Words and a Cache of size 16 Words. Main Memory and Cache are dived into blocks and Lines respectively. The size of each block Lines is of 4- words as shown in the following diagram.

Fully associative cache mapping- Example

Physical Address

As main memory size is of 128 words so 7 bits will be used to represent main memory. So, Physical address will be of 7 bits.

An example of fully associative mapping of W24 of B6 is given below

Fully associative memory block and block offset format values

As Block offset represent the Block size. So, 4 words of Block can be represented through 2bits.
As Block Number represent the Block in main memory. There are 32 blocks in main memory so 5bits are required to represent 32blocks. We have no need to divide Block Number into Line No and tag because any block of main memory can come in any cache Line.
So Block No is our Tag. Tag represent the Block No. as main memory of 32 blocks and any block can come in any cache line. In this way from 32 memory blocks, any block can come in any cache line. So 5 bits are required to represent any block in any cache line.

Note: if there are 128 blocks and each block size is 8 words then

Block offset = 3bits
Block number = 7bits
Tag= 7bits

Searching for block through Tag (cache Hit or miss)

Suppose CPU generate an address 1111100 for 128-word main memory.

First two bits (00) represent Block offset and last five bits (11111) represents the Tag in Cache memory.

As required word of memory block can present in any line of cache so the no. of comparator is increased. We match the tag of given address with the tag of all cache lines. If it matches then it is a cache hit case otherwise cache miss case.

Cache Hit for address (1111100) is given below

Fully associative cache mapping-Explain-with-Example-Cache Hit or miss

Shortcut Formula’s

Physical Address (PA) = Tag + Block Offset
Comparator = Total no. of lines

Comparator value in fully associative is equal to number of lines. Because any block of main memory can come in any line so we have to compare the tag of given address with tag of each line in cache.

Numerical Problem

Fully Associative Memory ( Byte and Word addressable) Numericals

Advantages vs. disadvantages

Advantages are that conflict miss issue resolve and hit rate is increased

The disadvantage is that Comparison time is increased. To search a particular block in the cache we will compare the tag bit of searching block with each line tag. If it matches then cache hit otherwise cache miss