Associative Memory
Associative memory (Content Addressable Memory, CAM) is a memory unit accessed by the content of the data rather than by its address. All words are searched in parallel, in a single memory cycle.
Ordinary RAM : "give me the word at address 1024"
Associative : "which word contains the value 4F2A?"
1. Organization
Components:
A (Argument register) : holds the data being searched for
K (Key register) : a MASK — a 1 selects the corresponding bit of A
for comparison; a 0 makes that bit a "don't care"
Memory array : m words of n bits, each with its own comparison logic
M (Match register) : m bits — bit i is set if word i matched
Every CELL of the array contains:
- a storage flip-flop
- a comparison circuit (XNOR + masking)
That is why associative memory costs several times more per bit
than ordinary RAM: each bit needs its own comparator.
2. The Match Logic
For word i, bit j:
Match(i,j) = A(j) . F(i,j) + A(j)' . F(i,j)' (XNOR = "equal")
Including the key mask:
Term(i,j) = Match(i,j) + K(j)'
(if K(j) = 0, that bit position is IGNORED — always "matches")
The whole word matches only if EVERY bit position agrees:
M(i) = Term(i,1) . Term(i,2) . ... . Term(i,n)
3. Worked Search Example
A (argument) = 101 111100
K (key) = 111 000000 <- compare only the first THREE bits
Word 1 = 100 111100 first 3 bits = 100 -> NO match
Word 2 = 101 000001 first 3 bits = 101 -> MATCH
Word 3 = 101 111100 first 3 bits = 101 -> MATCH
Word 4 = 011 111100 first 3 bits = 011 -> NO match
Match register M = 0 1 1 0
Notice: word 2 matched even though its lower bits differ completely —
because the key masked those positions out. This masking ability is
what makes associative memory useful for TAG comparison.
4. Read and Write Operations
READ:
1. Load A and K.
2. All words compare in parallel -> M is set.
3. If exactly one bit of M is set, read that word.
4. If SEVERAL bits are set, a PRIORITY circuit (Unit II!) selects
one at a time; the software reads them in sequence.
WRITE:
Option 1 : write to a specified address (like ordinary RAM),
used to load the memory initially.
Option 2 : TAG bits mark which words are occupied; a write goes
to the first free word found by a priority encoder.
Option 3 : overwrite the matched word (update in place).
5. Applications
| Application | How associative search is used |
|---|
| Cache memory (fully associative) | Compare the tag against every cache line simultaneously |
| TLB (Translation Lookaside Buffer) | Look up a virtual page number among all cached translations in one cycle |
| Network routers | Longest-prefix match on IP addresses at line rate (TCAM) |
| Database search engines | Find records matching a key without scanning |
| Pattern recognition | Compare an input pattern against stored templates |
| Data compression | Dictionary lookup in LZ-family algorithms |
| Virus scanners | Match against a signature database |
6. Ternary CAM (TCAM)
A normal CAM cell stores 0 or 1.
A TERNARY CAM cell stores 0, 1, or X (don't care) PER CELL —
the mask is stored with the data instead of in a global key register.
This is what allows a router to store entries like:
192.168.1.0/24 -> stored as 11000000 10101000 00000001 XXXXXXXX
and match any address in that subnet in ONE cycle.
7. Associative Memory vs Random Access Memory
| Basis | RAM | Associative memory (CAM) |
|---|
| Accessed by | Address | Content |
| Search time | O(n) if you must scan for a value | O(1) — one cycle regardless of size |
| Hardware per bit | 1 storage cell | Storage cell + comparator |
| Cost | Low | Very high (4–10× RAM) |
| Power | Low | High (every cell switches on every search) |
| Capacity | Large (GB) | Small (KB) |
| Typical use | Main memory | Cache tags, TLB, routing tables |
8. Why Associative Memory Is Small
Every bit needs its own comparator, so:
- area per bit is 4-10x larger than RAM
- EVERY cell in the array switches on EVERY search
-> power consumption scales with the whole array, not with
the one word you wanted
For a 1 MB fully associative structure the power would be prohibitive.
This is exactly why real caches are SET-ASSOCIATIVE rather than fully
associative — they compare only 2, 4 or 8 tags instead of thousands.
That trade-off is the entire subject of the next lesson.
Summary
Associative memory = searched by CONTENT, all words in parallel
Registers: A (argument), K (key/mask), M (match)
Match logic: XNOR per bit, masked by K, ANDed across the word
Search time O(1) regardless of size
Costly in area and power -> used only for cache tags, TLBs and TCAMs
