Associative Mapped Cache (Fully Associative Cache)

Associative Mapping, also called Fully Associative Cache, is a cache mapping technique used in computer architecture where any block of main memory can be placed in any cache line. This approach was introduced to solve one of the major limitations of Direct Mapped Cache, known as the conflict miss.

Motivation: Problem with Direct Mapping

In a Direct Mapped Cache, each frame of RAM can only be stored in a single predetermined cache line. The mapping is typically defined by the rule:

Cache Line = Frame Number mod Number of Cache Lines

Because of this strict rule, two different memory frames that map to the same cache line cannot coexist in the cache at the same time.

This means that even if other cache lines are empty, a new frame may still be forced to replace the data in a specific cache line. This situation creates a conflict miss.

In other words, the cache may still have free space, but the mapping restriction forces data replacement, which reduces the overall cache efficiency.

Concept of Associative Mapping

Associative mapping removes this restriction completely. In this technique:

• Any frame of RAM can be stored in any cache line.
• There is no fixed mapping rule between frames and cache lines.
• The system can place data in any free cache line.

Because of this flexibility, the cache can utilize available space more efficiently and avoid unnecessary replacements that occur in direct mapping.

Advantage: Elimination of Conflict Misses

Since memory frames are not restricted to specific cache lines, the system will always place a new block into an available free line if one exists.

As a result:

• Conflict misses are completely eliminated.
• Cache utilization becomes more efficient.

However, associative caches can still experience capacity misses. This occurs when the cache becomes completely full and an existing line must be replaced to store new data.

Address Structure in Associative Mapping

The physical address generated by the system does not change depending on the cache mapping technique. What changes is how we interpret the address fields.

In associative mapping, the physical address is divided into two parts:

• Tag
• Offset

Physical Address

+----------------------+-----------+
|         TAG          |  OFFSET   |
+----------------------+-----------+

Because a memory frame can be stored in any cache line, the tag must uniquely identify the frame. Therefore, the entire frame number becomes the tag.

The offset specifies the exact byte or word inside the cache block.

Frame Placement in Cache

Unlike direct mapping, associative mapping allows complete flexibility in where data is placed inside the cache.

• Any memory frame can be placed in any cache line.
• The system typically uses a replacement policy such as LRU, FIFO, or Random.
• The placement decision depends on which cache lines are free or selected for replacement.

Searching in Associative Cache

Because a block can be located in any cache line, the system cannot determine the exact line in advance. Therefore, the cache must search all cache lines to determine whether the requested data is present.

The search operation works as follows:

• The CPU sends a memory address to the cache.
• The tag portion of the address is extracted.
• This tag is compared with the tag stored in every cache line.
• If a match is found, a cache hit occurs.
• If no match is found, the result is a cache miss.

Parallel Tag Comparison

Searching every cache line sequentially would be too slow. To improve performance, associative caches perform tag comparisons in parallel.

Requested TAG
      |
      v
+-------------+   +-------------+   +-------------+
| Comparator  |   | Comparator  |   | Comparator  |
| Cache Line0 |   | Cache Line1 |   | Cache Line2 |
+-------------+   +-------------+   +-------------+
        |                 |                 |
        +-------- Parallel Comparison -----+

Each cache line contains its own comparator that checks whether the stored tag matches the requested tag.

Hardware Requirements

Because each cache line requires its own comparator, associative caches require more hardware resources than direct mapped caches.

If a cache has N lines, the hardware must include:

• N comparators
• Parallel comparison logic
• Replacement policy logic (LRU, FIFO, Random)

Disadvantage of Associative Mapping

The primary drawback of associative caches is their hardware complexity. Since every cache line requires a comparator and parallel comparison circuitry, the design consumes more silicon area and increases system cost.

• More comparators are required.
• More silicon area is used.
• Power consumption increases.
• Overall hardware cost becomes higher.

For this reason, fully associative structures are usually implemented only in small hardware structures.

A common example is the Translation Lookaside Buffer (TLB), which typically contains a small number of entries and benefits from the flexibility of associative lookup.

Summary

• Associative mapping allows any RAM frame to be stored in any cache line.
• It completely eliminates conflict misses.
• The physical address is divided into Tag and Offset.
• The entire frame number becomes the tag.
• All cache lines must be searched to locate data.
• Tag comparisons are performed in parallel.
• Each cache line requires its own comparator.
• Hardware cost is higher than direct mapped caches.
• Fully associative designs are commonly used in structures such as TLBs.