UVMArena

Comparators in Cache Mapping Techniques

In cache memory design, the number of comparators required depends on the mapping technique used. Comparators are hardware blocks that compare the tag stored in cache with the tag from the CPU address to determine whether a cache hit or miss occurs.

Different cache mapping techniques determine how many locations must be searched, which directly impacts the number of comparators required.

1. Direct Mapped Cache

In direct mapping, each memory block can be placed in only one specific cache line.

The cache line is determined using:


cache_line = frame_number % number_of_cache_lines

For example:

Frame number = 41
Cache lines = 16


41 % 16 = 9

This means the data must be located in cache line 9. Since the location is known exactly, the system only needs to check one cache line.

Comparator Requirement:
Direct Mapping requires only one comparator because only one cache line is checked.

2. Fully Associative Cache

In fully associative mapping, a memory block can be placed in any cache line.

Since the block may exist anywhere in the cache, the CPU must compare the incoming tag with the tag stored in every cache line.

If the cache has N lines, the system must compare the tag against all N lines simultaneously.

Comparator Requirement:
Fully associative caches require N comparators, where N is the number of cache lines.

3. Set-Associative Cache

Set-associative caches are a compromise between direct mapping and fully associative mapping.

The cache is divided into multiple sets, and each set contains multiple lines (ways).

The set is determined using:


set_number = frame_number % number_of_sets

Example:

Frame number = 41
Number of sets = 4


41 % 4 = 1

This means the block must be searched inside Set 1.

Inside the selected set, the block could be in any line (way), so the tag must be compared with all lines inside that set.

Comparator Requirement:
If the cache is K-way set associative, then K comparators are required.

Comparator Summary

Mapping Technique	Search Scope	Number of Comparators
Direct Mapping	Only one cache line	1
Fully Associative	All cache lines	N (number of cache lines)
K-Way Set Associative	All lines inside a set	K

Conflict Misses

A conflict miss occurs when multiple memory blocks compete for the same cache location.

Direct Mapping

Direct mapping has the highest number of conflict misses because each memory block has only one possible cache location.

Even if other cache lines are free, the system must replace the specific mapped line.

Fully Associative Mapping

Fully associative caches have zero conflict misses because blocks can be placed anywhere in the cache.

Set Associative Mapping

Set associative caches reduce conflict misses compared to direct mapping.

A block can be placed in any line within the set. If a free line exists in the set, the cache will use it instead of replacing an existing block.

Conflict Miss Comparison:

Direct Mapping: High conflict misses
Set Associative: Medium conflict misses
Fully Associative: Zero conflict misses

Key Takeaways

Direct mapping searches only one line → 1 comparator
Fully associative caches search all lines → N comparators
K-way set associative caches search within a set → K comparators
Conflict misses decrease as associativity increases.
Set-associative caches provide a good balance between hardware complexity and cache performance.

Introduction