精确匹配算法：内容可寻址存储器（CAM）原理

说到精确匹配，大家第一反应可能是哈希表。但在硬件里，哈希有冲突，有概率问题。我更喜欢用CAM——内容可寻址存储器。说白了，它就是个“反向”的存储器。

普通RAM你给我地址，我给你数据。CAM反过来：你给我数据，我给你地址。如果匹配上了，就告诉你“找到了”，同时输出对应的索引。

我在项目中用过一次CAM做MAC地址表。那时候交换芯片的查表延迟要求很苛刻，哈希搞不定，最后上了CAM。嗯，效果立竿见影。

CAM的基本结构

一个典型的CAM单元，由存储单元和比较器组成。每个bit都存一个值，同时能跟输入的数据做比较。所有bit的比较结果“与”起来，就是整个word的匹配结果。

你想想看，这相当于每个word都在并行做比较。所以CAM的查表速度是O(1)的，一个时钟周期就能出结果。代价呢？面积大、功耗高。

TCAM（三态CAM）架构

TCAM比CAM多了一个“三态”的概念。普通CAM只能存0和1，TCAM还能存“don't care”（X）。这个X在路由表里太有用了——前缀匹配本质上就是高位精确匹配，低位don't care。

我记得第一次接触TCAM是在做核心路由器的项目。路由表里几十万条路由，每条都是前缀形式。如果用普通CAM，得把每个前缀展开成完整的32位IP地址，那存储量直接爆炸。TCAM一条就能搞定一个前缀。

TCAM存储单元

TCAM的存储单元比CAM更复杂。每个bit需要两个SRAM单元来存：一个存数据，一个存mask。mask为1时，这个bit参与比较；mask为0时，这个bit被忽略。

模式	数据位	Mask位	比较结果
存0	0	1	输入为0时匹配
存1	1	1	输入为1时匹配
Don't care	X	0	总是匹配

TCAM的优先级编码器设计

TCAM查表时，可能多条条目同时匹配。比如你有一条/8的路由和一条/24的路由，目标IP可能同时匹配两者。这时候就需要优先级编码器来选出“最匹配”的那条。

优先级编码器的设计思路很简单：地址越小的条目优先级越高。所以路由表里，更精确的条目（更长的前缀）要放在地址更小的位置。

优先级编码器结构

我常用的优先级编码器是“树形”结构。把匹配信号逐级往上合并，同时传递优先级信息。这样做的好处是延迟可控，适合高速设计。

// 简化版优先级编码器逻辑
// match_lines: 各条目的匹配信号
// priority_addr: 输出最高优先级匹配的地址

wire [N-1:0] match_lines;
reg [log2(N)-1:0] priority_addr;

always @(*) begin
  priority_addr = 0;
  for (int i = N-1; i >= 0; i--) begin
    if (match_lines[i]) begin
      priority_addr = i;
    end
  end
end

TCAM的功耗优化策略

TCAM的功耗是出了名的大。每条条目都在并行比较，所有比较器同时翻转，那电流简直吓人。我在一个项目里测过，TCAM模块的功耗占了整个芯片的40%。

所以功耗优化是TCAM设计的必修课。我总结了几条实用的策略：

分段匹配

把TCAM分成多个bank，每次只激活可能匹配的bank。比如根据输入的前几位，先判断属于哪个bank，再只激活那个bank做比较。其他bank保持休眠。

我做过一个设计，用分段匹配把功耗降到了原来的1/3。代价是增加了些控制逻辑，但值得。

预比较技术

在正式比较之前，先做一个快速的“预比较”。比如只比较前8位，如果前8位都不匹配，那后面的就不用比了。这样可以提前关掉大部分比较器。

时钟门控

这个比较基础了。没在查表的时候，直接把TCAM的时钟关掉。我习惯在TCAM的输入加一个“valid”信号，valid无效时自动关时钟。

嗯，这里要注意：时钟门控的使能信号要小心处理，避免产生毛刺。我曾经吃过这个亏，芯片回来后TCAM偶尔会误匹配，查了好久才发现是时钟门控的glitch导致的。

数据翻转率优化

TCAM的功耗跟输入数据的翻转率直接相关。如果输入数据频繁变化，比较器也跟着频繁翻转，功耗就上去了。我试过在输入加一个“变化检测”电路，如果输入跟上个周期一样，就不触发比较。

这个方法在路由表场景下特别有效。因为路由查表的输入通常是连续的IP流，相邻包的目的IP往往很相似，变化不大。

好了，TCAM这块的内容就这些。从CAM的基本原理，到TCAM的三态架构，再到优先级编码器和功耗优化，每一步都有不少坑。我踩过的那些坑，希望能帮大家少走弯路。

---