Content-addressable memory (CAM): Exercises — Hardware deep dive

Before we start, one picture fixes every symbol we will reuse.

Figure — Content-addressable memory (CAM)

The one relation you will use over and over: $ML_{r} = \prod_{i = 0}^{n - 1} (D_{r, i} ⊙ S_{i}) (product = AND)$ Read it in English: "the row matches when all columns agree." A single disagreeing column makes one factor $0$ , and $0$ times anything is $0$ — the whole row dies. That is the wired-OR of mismatches doing its job.

Level 1 — Recognition

Recall Solution L1.1

CAM maps data → address: you feed a search word, you get back the address of a matching row. The block that collapses many possible HIGH match lines into one address is the Priority Encoder.

Recall Solution L1.2

(a) XOR ( $D \oplus S$ ) — outputs 1 when bits differ. (b) XNOR ( $D ⊙ S$ ) — outputs 1 when bits are equal. (c) AND (the product $\prod_{i}$ ). The row matches only if all per-column XNORs are 1.

Recall Solution L1.3

TCAM (Ternary CAM). It uses the ==don't-care $X$ == symbol (implemented with a mask bit $M_{i}$ ), which matches both 0 and 1 — the foundation of Longest Prefix Matching.

Level 2 — Application

Recall Solution L2.1

Compare bit by bit; any disagreeing column zeros the row.

R0 1100 vs 1010: columns differ at bit-1 and bit-2 → mismatch → $ML_{0} = 0$ .
R1 1010 vs 1010: all agree → $ML_{1} = 1$ .
R2 0110 vs 1010: bit-3 and bit-1 differ → $ML_{2} = 0$ .
R3 1010 vs 1010: all agree → $ML_{3} = 1$ . Match vector = $(0, 1, 0, 1)$ . Two rows match — exactly why we need an encoder. Lowest index wins → output address 1.

Recall Solution L2.2

Align rightmost as bit-0: $D =$ 1101 → $(D_{3}, D_{2}, D_{1}, D_{0}) = (1, 1, 0, 1)$ ; $S =$ 1001 → $(1, 0, 0, 1)$ .

bit-0: $1 ⊙ 1 = 1$
bit-1: $0 ⊙ 0 = 1$
bit-2: $1 ⊙ 0 = 0$ ← disagreement
bit-3: $1 ⊙ 1 = 1$ Product $= 1 \cdot 1 \cdot 0 \cdot 1 = 0$ → no match. The single column-2 disagreement killed it.

Recall Solution L2.3

Recall $+$ is OR here.

$M_{i} = 1$ : $match_{i} = 1 + (1 ⊙ 0) = 1 + 0 = 1$ . The mask forces a match regardless of $S_{i}$ . ✔ don't-care works.
$M_{i} = 0$ : $match_{i} = 0 + (1 ⊙ 0) = 0 + 0 = 0$ . Now the bits genuinely must agree, and $1 \neq = 0$ → no match.

Level 3 — Analysis

Recall Solution L3.1

Left side: "NOT (any bit mismatches)". Right side: "all bits agree". Enumerate the four agreement patterns of two columns, where $a_{i} = (D_{i} ⊙ S_{i})$ and mismatch $m_{i} = \overline{a_{i}}$ :

$a_{1} a_{0}$	$⋁ m = m_{1} \lor m_{0}$	$\overline{⋁ m}$	$a_{1} \land a_{0}$
0 0	$1 \lor 1 = 1$	0	0
0 1	$1 \lor 0 = 1$	0	0
1 0	$0 \lor 1 = 1$	0	0
1 1	$0 \lor 0 = 0$	1	1

Columns " $\overline{⋁ m}$ " and " $a_{1} \land a_{0}$ " are identical → the identity holds. Both are 1 only when every column agrees.

Recall Solution L3.2

To drive a line HIGH only when matched, the circuit would first have to know which rows match — but computing that is the very thing we are trying to do. It is circular. The dynamic-logic escape is: assume everyone matches (precharge HIGH), then let each mismatching cell conditionally discharge its own line to LOW. A single NMOS pull-down path per cell suffices, no answer needed in advance. This is the precharge → evaluate style: fast, small, but it burns energy charging thousands of lines every search — the root of CAM's power cost.

Recall Solution L3.3

Three match lines (rows 1, 3, 5) go HIGH simultaneously — duplicates all match in parallel. A Priority Encoder must resolve this; with lowest-index priority the output is address 1.

Level 4 — Synthesis

Recall Solution L4.1

Check each prefix against 10.1.2.3:

/0 matches everything → matches.
10.0.0.0/8: top 8 bits 10 agree → matches.
10.1.0.0/16: top 16 bits 10.1 agree → matches.

All three match. Longest prefix (/16) must win. Since the Priority Encoder picks the lowest index, sort rows longest-prefix-first:

10.1.0.0/16 → port C
10.0.0.0/8 → port B
0.0.0.0/0 → port A

Encoder returns the highest row that matched = row 0 → port C. Correct: the most specific rule wins.

Recall Solution L4.2

Total cells $= R \cdot n = 1024 \times 32 = 32768$ .

(a) BCAM: $32768 \times 10 = 327, 680$ transistors.
(b) TCAM: $32768 \times 16 = 524, 288$ transistors.
Ratio TCAM/BCAM $= 16/10 = 1.6 \times$ . TCAM's don't-care flexibility costs 60% more silicon per bit — the price of storing 0/1/X.

Level 5 — Mastery

Recall Solution L5.1

A stuck-open mismatch transistor means that column can never pull the ML LOW, so the match line ignores that bit — it behaves as though every row had a don't-care there. Effect: rows will report matches even when that column disagrees, causing false hits (e.g. 1010 matching a 1011 search if bit-0 is the faulty column). This resembles a TCAM don't-care functionally, but the crucial difference: a TCAM don't-care is intentional and per-cell (mask bit $M_{i} = 1$ chosen by software), while the fault is unintentional, column-wide, and unmaskable — a hardware defect, not a searchable feature.

Recall Solution L5.2

Average SRAM scan $= R /2 = 1024/2 = 512$ cycles. CAM $= 1$ cycle. Speedup $= 512/1 = 512 \times$ . The cost: CAM precharges and (partially) discharges every one of the 1024 match lines on every search, plus each cell carries 10–16 comparison transistors instead of a 6T Static RAM (SRAM) cell. So CAM trades large area + high dynamic power for that latency win — which is why it is reserved for latency-critical parallel search like a Translation Lookaside Buffer (TLB) or fully-associative Cache Memory, not general storage.

Recall Solution L5.3

Distinct prefix lengths from /0 to /32 inclusive $= 33$ . If 4 prefixes match, 4 match lines are HIGH simultaneously. Determinism is guaranteed by the Priority Encoder combined with longest-prefix-first row ordering: many HIGH lines enter, exactly one address (the most specific rule) leaves.