Associative Memory

Introduction

Conventional memory is addressed by location — you provide an address and get back data. Associative memory (also called Content-Addressable Memory or CAM) works differently: you provide a piece of data (or a pattern), and the memory tells you if and WHERE that data is stored — all in parallel, in a single cycle. This parallel search capability makes associative memory essential for cache tag lookup, TLB translation, and network routing, despite its higher cost.

How Associative Memory Works

In conventional RAM: "What's stored at address 5?" → Returns data at location 5 In associative memory: "Is the value 0x3FA7 stored anywhere?" → Returns the match location (or all matching locations)

Internal Structure

Each cell in associative memory contains:

1. Storage (flip-flop to hold the bit)
2. Comparison logic (XOR gate to compare with search input)

All cells compare simultaneously — this is what enables single-cycle parallel search.

Match Logic

For each entry, a match line goes high only if ALL bits match:

If any bit differs, the match line for that entry is pulled low.

Masking

A mask register allows partial matching — masked bit positions are ignored during comparison:

Only the unmasked positions are compared. This enables searching by partial keys.

Associative Memory vs Conventional RAM

Applications

TLB (Translation Lookaside Buffer)

The TLB is the quintessential use of associative memory:

• Search key: Virtual Page Number
• Stored data: Physical Frame Number + permissions
• Fully associative (any translation can be in any entry)
• ~32-512 entries, searched every memory access

Cache Tag Arrays

• Cache tags compared against address tag in parallel
• Fully associative caches use CAM for all tag comparisons
• Set-associative caches use small CAMs within each set

Network Routers

• Routing tables searched by destination address
• Ternary CAM (TCAM) supports wildcards for prefix matching
• Enables wire-speed packet classification

Pattern Matching

• Intrusion detection systems
• DNA sequence databases
• AI associative recall

Ternary CAM (TCAM)

Standard CAM matches on 0 and 1. TCAM adds a third state: don't care (X). Each cell can be set to 0, 1, or X. During comparison, X positions always match regardless of the search key.

This is particularly useful for:

• Network routing (IP prefix matching: 192.168.X.X)
• Firewall rules with wildcards
• Access control lists

Hardware Cost and Power

The main drawback of associative memory is cost and power:

• Each cell needs comparison circuitry (~12 transistors vs 6 for SRAM)
• Every search activates ALL cells simultaneously (high dynamic power)
• This limits practical size to a few thousand entries

Power-saving techniques:

• Search only when needed (clock-gated)
• Segmented search (check portions sequentially)
• Hybrid designs (hashed index + small associative check)

Key Takeaways

1. Associative memory searches by content, not by address — parallel comparison in one cycle
2. Each cell has storage plus comparison logic, making it 2× more expensive than SRAM
3. The TLB is the most critical application — enables fast virtual-to-physical address translation
4. CAM provides O(1) search time regardless of the number of entries
5. TCAM extends CAM with don't-care bits for pattern matching with wildcards
6. High cost and power limit associative memory to small, performance-critical uses (TLBs, cache tags, routers)
7. Despite being expensive, the performance benefit of parallel search makes CAM indispensable in modern CPUs