CS Taleem Logo
Intro to COA

 Fully Associative Mapping

In fully associative mapping, each memory block is mapped to any cache line. It resolves the issue of conflict miss. This means that any main memory block can come in any cache memory line. For example, B0 can come in L1, L2, L3, and L4; the same is true for all other blocks.   In this way, the chance of a cache hit is increased.

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

Fully associative cache mapping- Example

Physical Address

As the main memory size is 128 words, therefore 7 bits will be used to represent the main memory. So, the 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 represents the Block size. So, 4 words of Block can be represented through 2bits.
  • The block Number represents the Block in the main memory. There are 32 blocks in the main memory, so 5 bits are required to represent 32 blocks. We do not need to divide Block Number into Line No and Tag because any main memory block can come in any cache Line.
  • So, Block No is our Tag. The tag represents Block No. as the 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 the CPU generates an address 1111100 for 128-word main memory.

The first two bits (00) represent Block offset, and the last five bits (11111) represent the Tag in Cache memory.

As required, the word of the memory block can be present in any line of cache, so the number of the comparator is increased. We match the tag of the given address with the tag of all cache lines. If it matches, then it is a cache hit case; otherwise, it is a 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 a number of lines.  Because any block of main memory can come in any line, That’s why we have to compare the tag of the given address with the tag of each line in the cache.

Numerical Problem

Fully Associative Memory ( Byte and Word addressable) Numericals

Advantages vs. disadvantages

The advantages are that conflict miss issues are resolved, and the hit rate increases. The disadvantage is that Comparison time is increased. To search a particular block in the cache, we will compare the tag bit of the searching block with each line tag. If it matches, then cache hit; otherwise, cache miss.