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.

Only the Exact Entry Ever MatchesEach column is one search. match has one bit per entry, entry 0 on the right.
012keya5a73cmatch00010000hitindexshould hit entry 1should hit entry 2
Scroll horizontally ↔
  1. Cycle 0

    Key a5 matches entry 0 exactly. That works, because entry 0 cares about every bit.

  2. 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.

  3. 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.

Three Searches of the Fixed CAMEach column is one search. match has one bit per entry, entry 0 on the right.
012keya5a73cmatch011101100100hitindex012
Scroll horizontally ↔
  1. Cycle 0

    a5 matches entries 0, 1 and 2. Entry 0 is the most specific, and it wins.

  2. Cycle 1

    a7 matches entries 1 and 2. Entry 1 wins.

  3. 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 bitsCAM search: cells, levelsRAM read: cells, levels
4123, 865, 3
16533, 20361, 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

UseKeyResult
Fully associative cachethe address tagthe line that holds it
TLBthe virtual page numberthe entry with the physical frame
Network routerthe destination addressthe best route, through a TCAM
Packet filterthe packet header fieldsthe 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
  1. 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.

  2. 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.

  3. 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.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: search a5: match=0001 hit=1 index=0 search a7: match=0000 hit=0 index=0 search 3c: match=0000 hit=0 index=0

Original 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

Spot the bugEach option is the body of the priority encoder, after index = 2'd0;. The bench writes four entries and expects the lowest match to win. Which option fails?
ConceptWhat does a CAM take in, and what does it give back?
ConceptWhy does a router put its most specific routes at the lowest TCAM index?
Predict the outputThe same four entries are searched with the key 12. What exact line does the program print, if the key in the loop is 8'h12?
module tb;
  logic [7:0] value [4], care [4];
  logic [3:0] match;
  initial begin
    value[0] = 8'h12; care[0] = 8'hff;   // exactly 12
    value[1] = 8'h10; care[1] = 8'hf0;   // 1 followed by anything
    value[2] = 8'h02; care[2] = 8'h0f;   // anything followed by 2
    value[3] = 8'h00; care[3] = 8'h00;   // anything
    for (int i = 0; i < 4; i++) match[i] = (((8'h12 ^ value[i]) & care[i]) == 8'h00);
    $display("match=%b", match);
  end
endmodule

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.

Before
match[i] = valid[i] && ((key ^ value[i]) == 8'h00);
After
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.

Practice

Report a problem with this page