Content-Addressable Memory
Search a memory by its content: compare every entry at once, encode the winner, and use don't-care bits for ranges.
You Will Be Able To
- Explain how a CAM differs from a RAM: a key in, an address out.
- Build the match lines and the priority encoder of a CAM.
- Use the care mask of a ternary CAM to match ranges of keys.
- Name where CAMs are used and what they cost.
- Lesson
- G8.11
- Time
- 30 min
- Runs on
- Your browser
- Check
- 4 questions
A small router held three routes: one exact address, one range and a default. Every packet to the range or to the default was dropped. The CAM compared the don't-care bits too.
match has one bit per entry, entry 0 on the right.- Cycle 0
Key a5 matches entry 0 exactly. That works, because entry 0 cares about every bit.
- Cycle 1
Key a7 should match entry 1 (a0 to af). The compare looks at the don't-care bits too: 7 is not 0, so no match.
- Cycle 2
Key 3c should fall to the default route, entry 2. It matches nothing.
Measured on Icarus Verilog: the example of this lesson as it ships.
Search by Content
A RAM takes an address and returns the word stored there. A CAM works the other way round. It takes a word, the key, and returns the address where that word is stored.
- I/O
- Storage
- Datapath
- Control
- Data
- Search a5
Entries 0, 1, 2 match. The priority encoder picks the lowest: entry 0.
- Search a7
Entries 1, 2 match. The priority encoder picks the lowest: entry 1.
- Search 3c
Entry 2 matches. The priority encoder picks the lowest: entry 2.
Read the diagram as text
- Key: broadcast to every entry
- Entry 0: exactly a5
- Entry 1: a0 to af
- Entry 2: anything
- Entry 3: not written
- Priority encoder: the lowest match wins
- hit, index: the result
- Entry 0 → Priority encoder: match 0
- Entry 1 → Priority encoder: match 1
- Entry 2 → Priority encoder: match 2
- Entry 3 → Priority encoder: match 3
- Priority encoder → hit, index: index
All entries compare in the same cycle. A RAM would need one cycle per entry to search the same way.
match has one bit per entry, entry 0 on the right.- Cycle 0
a5 matches entries 0, 1 and 2. Entry 0 is the most specific, and it wins.
- Cycle 1
a7 matches entries 1 and 2. Entry 1 wins.
- Cycle 2
3c matches only the default, entry 2.
Measured on Icarus Verilog: the example with the care mask applied.
Match Lines and the Priority Encoder
Each CAM cell stores a bit and compares it with one bit of the key, with an XOR. All cells of an entry share one match line. Any cell that disagrees pulls the line low.
The match lines go to a priority encoder. Several entries can match at once, so the encoder must pick one. Here the lowest index wins, which lets the table be ordered by priority.
| Entries of 8 bits | CAM search: cells, levels | RAM read: cells, levels |
|---|---|---|
| 4 | 123, 8 | 65, 3 |
| 16 | 533, 20 | 361, 7 |
Measured with Yosys on flip-flop storage, with a valid bit per entry and the priority encoder written as a loop. The numbers depend on the coding style; a tree encoder is shallower. The RAM has one read multiplexer.
Ternary CAM: Don't-Care Bits
A ternary CAM (TCAM) stores a care mask with each entry. A bit with care 0 matches both 0 and 1. One entry can then cover a whole range of keys.
Every bit compared
match[i] = valid[i] && ((key ^ value[i]) == 8'h00);
Icarus: a7 and 3c give hit=0.
Only care bits compared
match[i] = valid[i] && (((key ^ value[i]) & care[i]) == 8'h00);
Icarus: a7 hits entry 1, 3c hits entry 2.
A router stores its routes in a TCAM, the most specific first. The lowest match is then the longest prefix that fits: the best route.
Where CAMs Are Used
| Use | Key | Result |
|---|---|---|
| Fully associative cache | the address tag | the line that holds it |
| TLB | the virtual page number | the entry with the physical frame |
| Network router | the destination address | the best route, through a TCAM |
| Packet filter | the packet header fields | the first rule that applies |
Each one needs an answer by content in a single cycle.
Lesson G12.2 builds caches, where a set-associative cache compares only a few tags per set. That is a small CAM inside every set.
Asked in interviews
What is a CAM?
A memory searched by content. The key is compared with every entry in the same cycle. Each entry drives a match line, and a priority encoder turns the match lines into a hit and an index.
Binary CAM or TCAM?
A binary CAM matches exact keys. A TCAM adds a care mask per entry, so a bit can be "don't care". Routers use TCAMs for longest-prefix match, with the most specific routes at the lowest index.
Why are CAMs expensive?
Every entry needs its own comparator, and every search switches every match line, which costs area and power. The priority encoder adds logic levels. So CAMs stay small: TLBs, small caches, routing tables.
Try It
The bench writes three routes. Entry 0 is exactly a5, entry 1 is a0 to af (care f0), and entry 2 is anything (care 00). Then it searches a5, a7 and 3c.
Only a5 hits. The other two lines show match=0000 hit=0: the compare ignores the care mask.
Fix the match line: AND the difference key ^ value[i] with care[i] before testing it for zero.
Run again: a5 gives match=0111 index=0, a7 gives match=0110 index=1, and 3c gives match=0100 index=2.
Synthesize the design to measure its cells and inspect the mapped gates.
search a5: match=0001 hit=1 index=0 search a7: match=0000 hit=0 index=0 search 3c: match=0000 hit=0 index=0Original design · 158 cells · 36 flip-flops · 0 latches · 9 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
// tb.sv: the bench (read-only). A small routing table: entry 0 is the exact address a5, entry 1 is
// every address a0 to af, entry 2 matches anything (the default route). Entry 3 is never written.
`timescale 1ns/1ps
module tb;
logic clk = 0, we = 0;
logic [1:0] waddr = 0;
logic [7:0] wvalue = 0, wcare = 0, key = 0;
wire [3:0] match;
wire hit;
wire [1:0] index;
tcam4 dut (.*);
always #5 clk = ~clk;
task automatic write(input logic [1:0] a, input logic [7:0] v, input logic [7:0] c);
waddr = a; wvalue = v; wcare = c; we = 1; @(posedge clk); #1 we = 0;
endtask
task automatic search(input logic [7:0] k);
key = k; #1;
$display("search %h: match=%b hit=%b index=%0d", k, match, hit, index);
endtask
initial begin
write(2'd0, 8'ha5, 8'hff); // exactly a5
write(2'd1, 8'ha0, 8'hf0); // a followed by anything
write(2'd2, 8'h00, 8'h00); // anything
search(8'ha5); search(8'ha7); search(8'h3c);
$finish(0);
end
endmodule
Check Yourself
Common Mistakes
Wrong Compare every bit of a ternary entry, care or not.
The CAM then matches exact keys only. On Icarus the lab finds no entry for a7 or 3c, although two entries cover them.
Fix Mask the difference with the care bits before testing it for zero.
match[i] = valid[i] && ((key ^ value[i]) == 8'h00);match[i] = valid[i] && (((key ^ value[i]) & care[i]) == 8'h00);Wrong Let the priority encoder pick the highest matching entry.
The table is ordered from the most specific entry to the least. In the spot item, the highest entry turns a5 into a default-route hit.
Fix Scan from the top down and keep the last match, so the lowest index wins. A casez with the lowest bit first works too.
Wrong Leave the valid bit out of the match.
An entry that was never written, or was deleted, still compares its old bits and can match.
Fix AND every match line with the entry's valid bit, and clear the valid bit to delete an entry.
Wrong Use a CAM where a RAM lookup would do.
Every entry has its own comparator, and a priority encoder over every entry adds logic levels. For 16 entries in the lab style: 533 cells and 20 levels, against 361 and 7 for a RAM.
Fix Use a CAM only when the search must be by content in one cycle. Otherwise hash into a RAM or search over several cycles.
Remember
- A CAM is searched by content: a key in, the matching address out.
- Every entry compares the key at once and drives a match line; a priority encoder picks one.
- A ternary CAM adds a care mask: a care bit of 0 matches anything.
- AND each match line with the valid bit, so empty and deleted entries never match.
- CAMs cost a comparator per entry: use them for small tables such as TLBs and routes.