Fully Associative Mapping refers to a technique of cache mapping that allows mapping of the main memory block to a freely available cache line. Also, a fully associative cache would permit the storage of data in any cache block. There would be no forcing of every memory address into a single particular block. In case the data and information are fetched from memory, then they can be placed in an unused block of a cache.
In this article, you will take a look at the Fully Associative Mapping according to the GATE Syllabus for CSE (Computer Science Engineering). Read ahead to learn more.
Table of Contents
- What is Fully Associative Mapping?
- Physical Address
- Searching for a Block through Tags (Cache Hit or Cache Miss)
- Numerical Problem
- Advantages vs Disadvantages
What is Fully Associative Mapping?
“Every memory block can be mapped to any cache line.”
The fully associative mapping helps us resolve the issue related to conflict misses. It means that any block of the main memory can easily come in a line of cache memory. Here, for instance, B0 can easily come in L1, L2, L3, and L4. Also, the case would be similar for all the other blocks. This way, the chances of a cache hit increase a lot.
Now, let us assume that there is a RAM (Main Memory) size of 128 Words along with a Cache size of 16 Words. Here, the Cache and the Main Memory are divided into Lines and blocks, respectively. Every block Line is of the size 4- words. It is shown in the diagram given as follows:
Physical Address
Since the main memory has a size of 128 words, a total of 7 bits would be used for representing the main memory. Thus, the Physical address would be 7 bits in size. Given below is an example of the fully associative mapping of W24 of the B6:
- Since the Block offset represents the Block size, 4 words of Block could be represented through two bits.
- Since the Block Number represents the Block in the main memory, there are a total of 32 blocks in the main memory. Thus, 5 bits would be required here to represent 32 blocks. We do not need to divide the Block Number into Line Numbers and tags. It is because, in any cache Line, any main memory block can come.
- Thus, Block Number is our Tag. A tag represents the Block Number as the 32 blocks’ main memory. Also, any block can come in a cache line. This way, any block can come from 32 memory blocks in any cache line. Thus, 5 bits would be required whenever we want to represent a block in a cache line.
Note: In case there are a total of 128 blocks, and the size of every block is 8 words, then,
Tag= 7 bits
Block number = 7 bits
Block offset = 3 bits
Searching for a Block through Tags (Cache Hit or Cache Miss)
Suppose that a CPU generates an address 1111100 for a main memory of 128-word. The first two bits (00) here would represent the Block offset, and the last five bits (11111) here would represent the Tag in Cache memory.
Since the required word of the memory block can be present in a line of cache, the number of the comparator is increased. Here, we match the tag of the given address with the tags of all the cache lines. In case it matches, then it’s a case of a cache hit, or else, it is a case of a cache miss.
Here is the Cache Hit for the address (1111100):
Shortcut Formulas
- Comparator = Total number of lines
- Physical Address (PA) = Block Offset + Tag
The value of the comparator in a fully associative mapping is equal to the total number of lines. It is because any main memory block can come in any line. This way, we can compare the tag of the given address with the tag of each and every line in the cache.
Numerical Problem
Advantages vs Disadvantages
The primary advantage of a fully associative mapping is that the conflict miss issue is resolved, and the hit rate is increased. On the other hand, the primary disadvantage is that the comparison time is increased. In order to search any specific block in any cache, one has to compare the tag bit of the searching block with each and every line tag. If it matches, a cache hit occurs, or else, a cache miss occurs.
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.
Also Explore,
- Types of Instructions in Computer Architecture
- ALU (Arithmetic Logic Unit)
- Control Unit
- Microprogrammed Control Unit
- Instruction Formats
- Addressing Modes
- Memory Hierarchy
- Associative Mapping
- Direct Mapping
- Conversion of Bases to Other Bases
- Flynn’s Classification of Computers
- SIMD
- SISD
- MIMD
- MISD
- De Morgan’s Theorems
Comments