基于SRAM的TCAM设计与FPGA实现

◆张 磊 吴中军 康令州 郭志君 卢宇浩



基于SRAM的TCAM设计与FPGA实现

◆张 磊 吴中军 康令州 郭志君 卢宇浩

（中国电子科技集团公司第三十研究所 四川 610041）

三态内容可寻址存储器TCAM是一种基于内容查找地址的特殊存储器，本文提出了在Kintex-7 FPGA芯片上，基于SRAM实现了512×36 TCAM的设计方法，突破了传统TCAM不能在FPGA上实现的限制，而且给出了4种不同设计方法的所需资源数量、时延和功耗。因此，SR-TCAM是传统CAM的实用且有效的替代方案，可以在硬件防火墙、入侵检测等网络安全领域广泛应用。

网络安全；TCAM；FPGA；匹配地址

0 引言

CAM是基于内容查找匹配地址的存储器，CAM因其高速搜索性能受到欢迎。CAM最初是在交换路由设备中应用[1]，目前广泛应用于网络安全系统的硬件防火墙的五元组匹配、入侵检测、病毒识别中的模式匹配[2]。

然而，CAM的速度是以高功耗，低有效bit密度和每bit成本高为代价的[3]。三态CAM（TCAM）的每bit成本比DDR SRAM高出约30倍，每bit耗电量比SRAM高150倍。表1说明SRAM在bit密度，速度和功耗方面优于TCAM[4]。

表1 TCAM和SRAM的比较

因此，需要一种创新的TCAM设计，在较低成本、较低功耗时，实现可以实用的搜索性能[5]。本文旨在介绍这种解决方案，使用SRAM存储器实现TCAM功能，称这种架构为SR-TCAM（基于SRAM的TCAM），并可以在FPGA芯片上将其实现。

1 架构设计

首先提出一个垂直分区VP的概念，VP的意思是将宽度为W位的TCAM字被分成n个子字，每个子字的宽度为w位。

图1 SR-TCAM的体系架构

SR-TCAM垂直分区VP将TCAM表按照列划分为n个子表，这些子表被处理存储在相应的SRAM块中。SRAM块被称做地址位置表APT(Address Position Table)和比特位置表BPT(bit Position Table)。图1所示的SR-TCAM体系结构的主要组成部分包括n个BPT、n个APT、n个APT地址（APTA）发生器、优先级编码器（PE）和AND运算。每个垂直分区都有其对应的BPT、APTA生成器和APT。

w个位的最大可能组合是2w，其中每个组合代表一个子字。我们的目标是将2w个子字映射到2w个比特，使得每个子字在其对应的存储器中由单个比特表示。

如图2所示，在BPT中，存储器的2w个比特被排列成2w-b行，每行有2个或更多比特。每行补充一个长度为w + 1位的称为最后索引（LI）值。输入子字的w-b高位用于选择BPT中的特定行，从而充当地址BPTA。比特位置指示符（BPI）的b个低位比特用于指示所选行中的特定比特位置，如果BPI指示的比特位置为高，则意味着存在该输入子字，否则不存在。

图2 比特位置表BPT

APTA生成器生成一个地址，称为APTA，用于在相应的APT中对这一行进行索引。APTA生成器包含1的计数器和加法器。1的计数器在选定的BPT行指定比特位置，然后将该信息转发给加法器，然后加法器加1，将所选行的LI的输出。

APT的大小为2w× K，其中2w代表行数，K代表每行中代表地址位置的位数，该地址位置对应于其初始地址，如图3所示。

图3 地址位置表APT

2 工作流程

SR-TCAM按照如下所述的步骤完成搜索操作。

步骤1：将待搜索的字输入进SR-TCAM；

步骤2：将字分成n个子字，这些子字然后并行输入到它们对应的BPT；

步骤3：然后将一个子字分为两部分：BPTA和BPI。步骤3并行发生在所有的子字上；

步骤4：读取由BPTA选择的行里面，由BPI指示的BPT中的比特位置。如果读出的位为高，则表明输入子字被认为存在，但是在哪个地址仍然是未知的。步骤4也针对所有BPT并行执行；

步骤5：对步骤4中所有BPT的读出位都进行了“与”运算。步骤5对应于图1中的1位与运算。此1位与运算的结果指定搜索操作是继续还是停止。如果1位“与”结果为低，则意味着发生了不匹配并显示搜索阶段结束，否则TCAM将继续搜索操作并进入步骤6；

步骤6：APTA生成器通过将所选行中的1的数目加到BPI所指示的比特位置（包括BPT所选行）的LI和LI的数目来计算APTA。为了计算所有的APTA，步骤6也并行进行；

步骤7：从步骤6开始，APTA同时从相应的APT中读出行；

步骤8：与图1中的K-bit与相对应的比特进行与运算。在步骤7中读出的所有行的相应位都进行与运算。在与运算后，地址位置保持高位被认为是可能的匹配地址PMA；

步骤9：这是最后一步。PE解码输出匹配地址MA。

3 基于FPGA实现

在Xilinx Kintex-7 FPGA开发平台上实现并验证了512×36 SR-TCAM的设计[6]。该设计的功能已经通过大量测试用例，并使用ModelSim SE验证工具得到了广泛的验证。

首先将36位的输入字分成三个子字，每个子字是12位。然后将每个子字作为地址应用于其相应的BPT，其大小为512×21位。对于该设计，总共需要三个BPT。每个BPT的大小通过将子字细分为9bit和3bit位两部分来决定，因此需要29 = 512的地址空间和23 + 13（LI）= 21位的字大小。每个APT的大小为4096×512位，来自所有行APT的读出随后被逐位进行“与”运算，以使用PE解码得到匹配地址MA。

表2列出了4种不同设计参数的设计细节。我们在FPGA上使用了两种BRAM的综合优化方式[7]。在FPGA开发板xc7k325tffg900上，我们已经使用了182个BRAM[8]。 Kintex-7上的每个BRAM最大容量可以是36Kbit，并且可以通过多种方式进行配置。

表2 各种设计所需资源和功耗

在设计1的情况下，通过使用综合选项BRAM-AUTO，为所有三个APT使用了182个BRAM，并使用分布式BRAM创建了三个BPT。

在设计2的情况下，通过使用综合选项BRAM = BLOCK POWER2，其仅使用163个BRAM用于APT，而3个BRAM用于BPT。除了使用的BRAM数量外，这两种设计在LUT数量和延迟方面也有一些折衷。因此，用户可以选择合适的设计参数。

使用Xilinx X-Power工具来测量SR-TCAM搜索操作活动的功耗数据。我们通过以在100MHz时钟速率时，1000次搜索操作的平均值来计算功耗，以获得更好的功耗估计。

4 结束语

本文研究了在Xilinx Kintex-7 FPGA芯片上实现512×36 SR-TCAM，给出了设计架构和工作流程，并给出了4种不同的设计方法，以验证SR-TCAM的可行性和实用性。下一步的工作会将SR-TCAM应用于网络安全设备的深度包过滤、应用协议识别、病毒检测等功能的硬件实现。

[1]彭坤杨.基于TCAM的高速可扩展的正则表达式匹配技术[D].安徽:中国科学技术大学，2013.

[2]屠振，梁进山，杨奎武. TCAM在高速路由查找中的应用及其FPGA实现[J].微计算机信息，2015.

[3]张建伟.一种低功耗、抗软错误的TCAM系统设计[J].微电子学与计算机，2015．

[4]陈世文，黄万伟.一种深度包检查引擎的FPGA硬件实现[J].测控技术，2014.

[5]刘潇， 高峻.用FPGA实现较大规模的CAM[J].电子工程师，2013.

[6]徐欣，李宗华.基于FPGA的内容可寻址存储研究设计与应用[J].国防科技大学学报，2011.

[7]K.Pagiamtzis.Content-Addressable Memory (CAM) Circuits and Architectures[J].IEEE Journal of Solid-State Circuits，2012.

[8]Xilinx. ModelSim SE User Guide.http://www.xilinx.com.