一种基于FPGA的内容可寻址存储器的设计

(杭州电子科技大学电子信息学院，浙江 杭州310018)

0 引 言

内容可寻址存储器(Content Addressable Memory，CAM)是一种特殊的存储器件，不仅能存储数据，而且能将输入数据与内部所有数据进行比较，从而判定输入数据是否已经存在于存储器内。CAM可以在单个时钟周期内并行完成所有比较查找运算，相比其他基于硬件或软件的搜索系统，具有更高的查找效率，因而被广泛运用于网络协议包分类与发送、数据包内容检测过滤、高速缓存和数据加密等众多领域[1]。传统CAM的设计与实现通常依靠专用集成电路技术(Application Specific Integrated Circuit，ASIC)，相关产品具有容量大、集成度高、速度快等优点，但也存在价格昂贵、功耗偏高等不足[1-3]，这显然不利于在更多的场合灵活地应用CAM的强大功能。近年来，多种基于现场可编程逻辑阵列(Field Programmable Logic Array，FPGA)的CAM 等效功能块构建方案[4-6]出现。大多数方案成功模拟实现了传统CAM 器件的高速查找特性，但在实用中却普遍存在片内资源开销过多的缺点。本文在一种现有电路[5]的基础上进行了改进，提出了一种新颖的等效逻辑电路。电路简洁易行，可根据实际存储的单位数据字长和数据控制精度调整数据寄存器与状态寄存器的组成比例，从而在实现CAM 功能的同时减少逻辑资源的开销。

1 CAM的传统电路模型

单个CAM 单元实现两种功能:1)存储1 bit 预设数据;2)将当前输入数据与预设数据进行比较并输出比较结果。在传统电路模型中，一般使用单个SRAM 单元实现功能1，再在此基础上额外添加若干晶体管实现功能2，如图1所示。图1中，两个背靠背的反相器即构成了一个SRAM 存储单元，晶体管M1和M3以及晶体管M2和M4 分别构成了两条互补的查找电路，分别用于查找存储在SRAM 单元中的数据“1”和数据“0”。查找成功时，数据匹配线ML为高电平，反之则为电平。由于SRAM 中预设存储数据非‘0’即‘1’，该类CAM 单元总处于两种状态之一，因此通常被称为二态内容可寻址存储器(Binary Content Addressable Memory，BCAM)。BCAM 只能存储查找固定长度的数据，为了避免为同时存储不同长度的数据而反复搭建不同长度规格的BCAM 电路，可以使用长度规格统一的三态内容可寻址存储器(Ternary Content Addressable Memory，TCAM)。TCAM 相比BCAM，优势在于多出一个“无关”状态，即从“二态”变为了“三态”。被设置为“无关”状态的TCAM 单元不会对最终匹配结果产生影响，因此通过灵活调整设置不同TCAM 单元满足对不同长度数据的存储与查找需求。典型的TCAM 单元结构电路如图2所示。图2中，当两个SRAM 单元中存储数据不一致时，分别表示BCAM 中已存在的两种数据存储状态;当两个数据同时为“1”时，表示TCAM 特有的“无关”状态;不允许两个数据同时为“0”。

图1 BCAM 单元传统结构电路

图2 TCAM 单元传统结构电路

2 CAM 基于FPGA的等效逻辑电路

本文提出一种CAM 基于FPGA的等效逻辑电路，电路在实现传统TCAM 单元逻辑功能的同时，根据不同数据单位字长和数据控制精度要求优化对寄存器和组合逻辑函数等片内逻辑资源的开销，从而获得更高的资源利用效率。

2.1 CAM 单元结构组成

等效逻辑电路主要包含:预存数据寄存器组、“无关”状态寄存器、“已使用”状态寄存器、数据比较器、掩码电路和查找结果输出寄存器。预存数据寄存器组的中寄存器的数量等于单位数据的字长，还可按照实际需求进行调整;数据比较器用于判定输入待查找数据和预存数据的是否相同;“无关”状态寄存器指示该CAM 单元的数据寄存器中相应数据段是否处于“无关”状态，其中数据为“1”表示处于“无关”状态，“0”表示处于“相关”状态;“已使用”状态寄存器记录指示当前CAM 单元是否已被启用，即是否被写入了有效数据，从而避免将未启用单元中的初始数据误认为有效数据，进而导致查找错误;掩码电路对数据比较器的输出和“无关”状态寄存器中内容进行求“或”运算，再将结果与“已使用”状态寄存器中内容求“与”，只有在当前CAM 单元已被启用，且输入数据与预设数据完全相同，或者不同部分已被设为“无关”，才会计算得出匹配成功的结果;最后的计算结果经查找结果输出寄存器寄存后，作为该CAM 单元的最终查找匹配结果输出。

相比文献[5]中的电路，新电路的改进在于数据寄存器与“无关”状态寄存器的数量比值不再被固定为1∶1，而是可以根据实际应用需求灵活调整，该比值被称为“无关”状态寄存器的控制粒度。控制粒度越大，表示单个“无关”状态寄存器可以控制更多的数据寄存器，从而减少“无关”状态寄存器的数量。现有电路的控制粒度固定为1，每个“无关”状态寄存器只控制一个数据寄存器，控制精度达到最高，但却未必是所有应用都需要的。例如使用CAM 查找字符串，由ASCII 码描述的单个字符的字长为8 bit，一旦将CAM 中某字符串的一个字符设置为“无关”，则相应的8 bit数据总是同时受到掩蔽，因此完成上述功能只需使用一个“无关”状态寄存器。可以使用控制粒度为8的新CAM 单元实现相同的功能，每个CAM 单元中，“无关”状态寄存器的数量只相当于现有单元电路中数量的1/8。图3中显示了一个经综合后生成的控制粒度为8，单位数据字数为4的新型CAM 单元，新电路中每1 bit“无关”状态码都可以通过或门(虚线框内所示)掩蔽8 bit数据码的比较结果，而现有电路中则只能掩蔽1 bit数据码的比较结果，因此节省了逻辑资源开销。

图3 新型CAM 单元实例

综合生成1个控制粒度为n，单位数据字数为k的新型CAM 单元所需的寄存器总量Areg为:

组合逻辑函数的开销总量Alut可通过以下经验归纳公式得到近似估算:

2.2 CAM 单元功能时序

首先执行电路复位。执行写入操作时，读写模式使能端wren 置为高电平，使能预存数据寄存器组、“无关”状态寄存器和“已使用”状态寄存器，然后在下一个时钟上升沿到来时通过预存数据输入端wdata和“无关”状态设置端dncare 对二者中数据进行更新，“已使用”状态寄存器中写入“1”，表示该CAM 单元以得到使用，其中存储的数据有效;同时通过掩码电路中的多路选择器，将查找匹配结果锁定在低电平，表示未执行查找操作;执行查找操作时，wren 置为低电平，允许掩码电路正常工作，然后从查找数据输入端sdata 写入数据，在下一个时钟上升沿到来时，查找匹配结果输出端mhit 输出相应的查找结果，高、低电平分别表示“找到”和“未找到”。对图3中电路执行写入操作和查找操作的功能时序如图4所示。其中，执行写入操作1时未将CAM 单元中任何数据段置为“无关”状态，因此执行查找操作1时CAM 单元报告只能找到数据“abcd”而未找到数据“abce”;执行写入操作2时将CAM 单元中最后8 bit数据置为“无关”状态，因此执行查找操作2时CAM 单元报告既可以找到数据“abcd”也可以找到数据“abce”。

图4 实例CAM 单元的操作功能时序图

2.3 完整的CAM 模块

完整的CAM 功能模块主要包括:CAM 单元矩阵、预设数据寄存器、预设地址译码器、命中信号生成器和查找地址编码器。CAM 单元矩阵用于存储特定规格的预设数据，它的列数即为预设单位数据的字长，行数即为预设单位数据的最大可能存储量，行内CAM 单元的数据匹配线级联，行内所有CAM 单元的同时匹配成功才等价于当前完整输入数据的匹配成功，行间CAM 单元并联，以实现对所有行的并行查找;数据寄存器用于在预设数据和查找数据时暂时寄存输入内容;预设地址译码器工作于预设数据阶段，它将输入的二进制地址转变为独热码，然后激活相应的CAM 单元行，使之接受数据写入操作;命中信号生成器和查找地址编码器都工作于数据查找阶段，前者指示当前输入内容是否得到匹配，后者负责将CAM 单元矩阵输出的独热码转变为二进制地址输出。完整的CAM 模块图如图5所示。

图5 完整的m×n CAM 模块图

3 电路综合与分析

为了分析构建本文提出的新电路所需的资源开销及其性能，使用Altera 公司出品的Quartus II 12.0软件在该公司生产的FPGA 芯片EP2C35F484C8 上构建规格为m×128的完整CAM 模块，其中m 分别取值为8 bit、16 bit、24 bit和32 bit，“无关”状态寄存器的控制粒度g 分别取值为2、4、8。同时，使用文献[5]的方法，在同一芯片上构建相同规格的CAM 模块以供比较。电路分析和综合的过程中选择的优化策略都为“平衡”。不同规模下寄存器、组合逻辑函数和逻辑单元(Logic element，LE)等3种资源的开销对比显示在图6、图7和图8中，最高工作时钟频率的比较则记录在表1中。

通过分析上述图表中的数据可知，实现相同规格的CAM 模块，新电路的逻辑资源消耗明显少于现有电路，且随着控制粒度g的增大，优势愈发明显。此外，经过相同强度的时钟约束优化，新电路的最高工作时钟频率也普遍高于现有电路，且不会随着g值变化出现较大的起伏，具有较好的稳定性。当单位数据字长为32 且g=8时，新电路的最高工作时钟频率为152.74 MHz，电路的最高吞吐量可达到4.9 Gbps，足以满足大部分应用需求。上述数据分析表明，新电路特别适合于存储和查找具有较大单位数据字长且所需控制精度不高的数据，如ASCII 字符和字符串。

图6 寄存器开销对比

图7 组合逻辑函数开销对比

图8 逻辑单元开销对比

表1 最高工作时钟频率比较

4 结束语

本文提出了一种内容可寻址存储器的等效逻辑电路。本电路可以根据实际数据字长需求灵活地调节基本单元的电路组成，在实现CAM 功能的同时显著减少寄存器等逻辑资源的开销，提高FPGA 片内逻辑资源的使用效率，同时还可以运行在较高的工作频率，在较高的工作频率，因此具有一定的工程实用价值。

[1]Kostas P，Ali S.Content-addressable memory (CAM)circuits and architectures:a tutorial and survey[J].IEEE Journal of Solid-State Circuits，2006，41(3):712-727.

[2]Yang B D，Lee Y K，Sung S W，et al.A low power content addressable memory using low swing search lines[J].IEEE Transactions on Circuits and Systems，2011，58(12):2 849-2 858.

[3]Igor A，Travis H，Daniel D，et al.A 32 nm 0.58-fJ/bit/search 1-GHz tenary content addressable memory compiler using silicon-aware early predict late-correct sensing with embedded deep-trench capacitor noise mitigation[J].IEEE Journal of Solid-State Circuits，2013，48(4):932-939.

[4]Brelet J L.Using Block RAM for High Performance Read/Write CAMs[EB/OL].http://www.xilinx.com/support/documentation/application_notes/xapp204.pdf，2000-05-02.

[5]Altera Corporation.Advanced Synthesis Cookbook[EB/OL].www.altera.com/literature/manual/stx_cookbook.pdf，2011-07-01.

[6]Zahid U，Kim I，Sanghyeon B.Hybrid Partitioned SRAM-based ternary content addressable memory[J].IEEE Transactions on Circuits and Systems，2012，59(12):2 969-2 979.