**基于Verilog的TCAM硬件实现**
一、 背景
路由器是网络设备的关键组成部分，它需要接收数据包，然后决定将数据包发送到何处，以便进行IP转发或IP路由。今天的路由器需要在大量数据中进行非常快的查找，以实现快速的数据包路由。其他需要高速搜索的应用程序包括翻译后备缓冲区(TLB)和cpu、数据库引擎和神经网络中的完全关联缓存控制器。虽然设计人员可以从许多选项中选择执行这些搜索，但最有效的方法涉及使用内容寻址存储器(CAMs)。CAMs将搜索数据与存储的数据表进行比较，并返回匹配数据a1的地址。CAM的搜索功能比软件的搜索功能运行得快得多，因此CAM正在取代搜索密集型应用中的软件，如互联网路由器中的地址查找、数据压缩和数据库加速。
二、 原理
我们可能就已经熟悉了哈希表是最有效的搜索实现。CAMs被认为是这种构造的硬件实现。列表的线性搜索类似于在串行搜索中遍历内存的所有位置并与一个键进行比较。基于cam的搜索相当于并行地比较所有内容，然后返回成功比较的地址。这本质上要快得多，尽管构建起来更复杂。其中TCAM支持带掩码的三元匹配,TCAM采用更有效的X/Y编码格式且TCAM支持CPU读写，TCAM中的优先级编码器确保只输出第一个匹配的条目。
通常TCAM/CAM是有对应的Ram_wrapper 库的，但是芯片设计过程中对于比较小的查表，我们完全可以使用寄存器搭建一个TCAM/CAM. 还可以做的更加灵活，这就类似于寄存器搭建RAM一样。如下图所示，TCAM内部实现主要分为三个部分：Seach broadcast（广播）、 Match lines(匹配比较)、Priority encoder（优先级编码）
三、 实现
3.1 模块接口
如下图所示，key以及随路的key_vld信号是待查找的键值，比如48bit的mac地址。TCAM模块对应的cpu接口完成表项的配置，输出接口tcam_vld是key_vld的delay,（查表消耗的周期）。hit_vld 表示命中有效信号（0：未命中，1：命中），命中的结果则是index。而hit_vector 是所有表项的命中信号（hit_vld = | vector），用于debug使用，尤其是在多个命中情行下。
特别注意的是，cpu_wdat的内容是{data,mask},假设key的位宽为WIDTH,则cpu_wdat/cpu_dout位宽为WIDTH+WIDTH. Mask 0 表示不进香港vps行比较，Mask所示进行比较。
3.2 编码
TCAM还允许对搜索词中的一个或多个位使用第三个匹配状态X或“不关心”, 比如一个TCAM可能有“10XX0”作为它的一个存储词,TCAM灵活匹配四个搜索词中的任意一个——“10000”、“10010”、“10100”或“10110”。通过为每个存储单元添加一个掩码位来添加“不关心”状态，从而进一步增加了复杂性。TCAM中的优先级编码器确保只输出第一个匹配项。X的灵活编码减少了存储条目的数量，从而进一步提高了搜索效率。
***标准编码：***标准的数据/掩码编码的真值表如表3.1所示，可以看到给定key、 data以及mask必然有一个结果：1：命中，0：不命中.逻辑表达式为Hit=~( (Data|Key) &Mask））这种编码方式缺陷在于只有两种状态。而我们在逻辑设计中常常设计一个vld来指示逻辑是否在工作状态.
Table 3.1 标准编码
Key Data Mask Hit
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
XY编码：
在逻辑设计中我们常常使用XY编码格式替代标准编码格式，以达到最高密度（含有0、1和无效三种态），相当于比标准编码多了一个vld开关。使用{entry_Y,entry_X}替换{key,mask}的XY编码的真值表如表3.1所示。{Y,X}={0,0}表示始终没有命中，{Y,X}={1,1}表示不关心(等于被屏蔽)。逻辑表达式是Hit = （（~Key）& X）| (Key&Y) 。这里的表达式也就是一个2mux1电路单元。
Table 3.2 XY编码
Key Y X Comment Hit
0 0 0 Never hit. 0
0 0 1 1
0 1 0 0
0 1 1 don’t care 1
1 0 0 never hit. 0
1 0 1 0
1 1 0 1
1 1 1 don’t care 1
注意：本文定义mask为0 不进行比较，mask为1进行比较。
四、 仿真
