1. 引言
随着互联网行业的快速发展，网络的不断升级，从2G、3G、4G、到现如今的5G，网络传输的速度越来越快，在现如今的5G通信网络中，因为性能的提高，所以其中包含的路由器等转发路由设备也需要发展，为了适配通信网络重数据量增大的趋势，既要保证数据链路的完整性，又要保证其流畅性，因此对路由器，交换机机等设备提出了更高的要求——在通信中如何快速路由。传统的网络查找技术都需要通过软件，但通过软件，就必然需要CPU的指令操作，那样就会浪费时间，降低效率，随着市面上Altera和Xilinx的FPGA芯片的性能越来越高，发展的技术越来越成熟，因此FPGA在网络中也被使用的频率越来越高。
CAM (Content Address Memory)是一种与RAM完全相反的缓存机制，当我们使用RAM的时候，每个数据存在某一个地址下，当我们想读取数据时，索引地址来读取数据，但CAM是相反的，想要查询某个地址是否存在，通过索引数据来查询这个地址是否存在。CRC32是一种循环冗余校验码，在数据搜索和数据处理中经常会用到，经常用于保护数据的正确性和完整性时会采用，通常的CRC32用于计算一帧数据包的CRC数值，其CRC数值是通过对每个数据的CRC反复运算得到的，最终累计计算出结果，将CAM与CRC32相结合，这样就能保证，每一个存进CAM的数据都有一个属于自己的CRC值，如果把这个计算出的CRC值当作该数据的地址进行缓存，那么每个数据的自己的地址具有相关性，这样查找起来方便很多 [1]。
文献 [2] 基于FPGA的低功耗预比较策略实现CAM，实现CAM的读写功能，CAM的写功能将缓存设置成M*N的坐标轴，按照坐标写入，读取的时候依次比较进行读取，虽然查找功能实现，但是查找过程需要一次比较，查找周期过长。文献 [3] 一种基于FPGA的内容可寻址存储器的设计，对CAM的实现做了具体的阐述，但是其中编解码的算法没有具体说明，因此无法判断该CAM的读写性能是否优良。
2. 功能介绍
FPGA中有BRAM，即block ram，一种存储器。可以给数据地址写入数据，并且给地址读出对应的数据。相反地，给数据和地址写入数据之后，如果给数据来读出对应的地址，这样的存储结构就是CAM表，CAM表既可以用硬件电路做出也可以用FPGA来实现。在FPGA没有被广泛应用的时期，CAM在早些年在软件中是一种昂贵的设备，主要用途是CPU的cache中。最近这些年，互联网和物联网的高速发展，早期使用软件匹配算法实现的路由器、防火墙、入侵检测等技术，已经不能适用于当代这个网路技术，在FPGA的基础上实现CAM的功能是目前解决路由问题的主要方法。
CRC校验经常使用的方法是多项式。一个n阶2进制的多项式子可以一次被处理：(an-1)*(n-1) + (an-2)*(n-2) + … + a0。比如目前有一个8bit的进制数字表示为10110100：1*7 + 0*6 + 1*5 + 1*4 + 0*3 + 1*2 + 0*1 + 0*0。多项式乘除法运算过程与普通代数式的乘除法相同。多项式的加减法运算以2为模，加减时不进位、错位，和逻辑异或运算一致 [4]。
3. CAM的一般方法
目前，实现CAM的方法有很多种，但都有利有弊，对应不同场景选用不同的方法，像最初的顺序查找法，这种方法应用的原理与ram基本一致，想找到其中一个数据对应的地址，就要遍历所有的数据，随着CAM的深度增加，遍历的时间越长，此方法仅使用于一些对时间性能要求不高的场景。因为顺序查找法的延迟很大，也伴随着Hash查找法的产生，对原有数据进行Hash算法，经过Hash后，将数据存放到固定的位置上，下此查找时一次就能找到，虽然此方法查找速度较快，但是此方法容易产生Hash冲突，并且Hash算法在FPGA中实现较复杂，容易出现时序违例，布局布线复杂，从而有时会选择降低频率，从而影响整个模块。
3.1. 顺序查找法
顺序查找又称为线性查找，就是先将一些数据依次写入一张表中，每一个数据会有相应的地址对应，当我们想查找这个表中是否存在某一个数据的时候，就要从头开始依次比较，第一个比较不对，就比较第二个数据，以此类推到第n个数据，如果在查找的过程中，比对成功了，要么返回该数据所对应的地址，要么显示查找成功 [5]。
3.2. Hash查找法
Hash方法的主要原理是查找Hash表，Hash表中的数据，都是经过各种Hash算法后，每一个数据都有一个固定的位置存放，当我们进行Hash查找时，只需要将数据再通过Hash函数的计算后，便可求得数据的位置，即可进行一次的数据的比较即找到欲查找数据。在Hash结构中，我们称输入数据的值为键值(Key) [6]。
在Hash查找中必须要选择Hash函数，常见的几种Hash函数有：随机数运算法、旋转运算法、中间平均运算法、直接运算法、余数运算法、折迭运算法，数值抽出运算法。
在Hash查找中，利用Hash函数所产生的数据的位置可能会发生数据位置已存在有一笔数据的情形，此时我们称为Hash碰撞。发生Hash碰撞时，我们必须提供一些解决方法，才能让数据有对应的存储位置，否则会造成数据流失的错误。常见的Hash碰撞解决法有下列几种：
1) 线性开放寻址法；
2) 差值解决法；
3) 链表解决法；
4) 分桶Hash法 [7]。
3.3. 优化CAM查找方法
在我们进行CAM表查找的过程，我们怎样能将顺序查找法的实现简单，与Hash查找的速度相结合，经过长时间的研究，想到一种既实现简单，查找速度又快的方法，准备将顺序查找法与CRC32算法相融合。
CRC (Cyclic Redundancy Check)纠错校验经常使用在数据缓存和5G通信领域，因为要确保数据的完整性，流畅性和正确性为，所以我们必须对每一帧数据都要采取纠错的手段。在目前校验检错的方法中，CRC被用的次数是最多的、最频繁的，因为它是最稳定的，最可靠的 [8]。CRC32虽经常用于数据校验，但是我们也乐意用在CAM查找中，假设64 bit的数据进行CRC32后就变成了32 bit，每一个64 bit数字进行编码后都会有一个独特的32 bit数字，但是这里肯定有人认为64 bit变32 bit那肯定会产生冲突的，没错，理论上是这样的，只要超过有2的32次方的数次，那么就会产生冲突，但是2的32次方是一个多么大的数字，FPGA的缓存容量本来就不多，所以我们基本可以忽略冲突，为什么要选择CRC32呢，目前CRC32技术非常成熟，它的算法都是异或来实现，要比Hash简单的多。
以下是我基于CRC32算法的基础上进行优化的CAM表查找架构图，如图1所示。
具体功能是这样实现的：
写入过程：首先我要么将里面的缓存进行初始化，全部清0，然后将输入进来的数据进行CRC32运算，得到一个32 bit的数据，但是我们只取其中低12 bit，为什么只取低12 bit呢，因为12 bit位宽也可以表达2的12次方个数字了，在实际应用中已经是一个很大的数字，这12 bit的数据将作为冲突计算模块的输入，在conflict calculate中具有一个检测功能，会将这个12 bit的数据的最高位拼接上一个00，达到一个14位宽bit的数据。将这个数据作为conflict ram的基础地址进行查询，如果查询到该地址是有数据对应的，那么证明产生了冲突，那么我就在这个12 bit数据前面补上01，然后去查绚这个地址下面是否有数据，如果该地址下面依然存在数据，那么表示存在了二级冲突，那么就要在12 bit数据前面补上10，以此类推，根据前面补位数不同，所以支持的冲突级数也不相同，12 bit可以表示很多数字，所以当一个缓存器如果实时更新里面的数据内容，那么在实际情况下产生的冲突数量几乎为0，并且这样做做法的好处就是每一个数据与它的地址是有相互关系的，查找的过程速度很快，以下为写入状态机，如图2。
查找过程：如果我们想查找CAM表中是否存在某个数据，要将输入进来数据做CRC32得到一个64 bit的数据，将64 bit的数据截断，取它的低12 bit，将这12 bit数据发送给conflict calculate检查是否有多个数据经过CRC32后会产生这12 bit数据，就是检查是否存在冲突，将这12 bit数据前面补上00，然后当作conflict ram的地址去进行查询，如果该地址下对应的数据为1，证明已经存在了一级冲突，那么我们就将12 bit数据前面补上01去查询，如果该地址下显示为0，那就证明没有存在2级冲突，所以就要取data ram中对应的这两个地址位去比较，两个数据中有一个就是我们想要查询的数据，最多比较两次得到结果，以下为读出状态机，如图3。
4. 功能验证
4.1. FPGA验证
在我们将design设计完成后，一般都要进行仿真测试，主要分为前仿真和后仿真，前仿真指的就是不考虑时序和布局布线等问题，基于仿真工具，通过仿真波形和测试用例来比对结果是否正确，功能是否达到，常用的仿真工具有modelsim、VCS等，后仿真就是看我们的设计是否有时序违规，布局布线是否合理，建立时间和保持时间是否达到要求，有时一些毛刺也是在后仿真时候发现的，后仿真相对来说是和真实情况符合的，最反应实际工作情况的仿真，一般当我们前方真没有问题后再进行后仿真。
4.2. 验证方法
要测试CAM的功能是否实现，以及测试写入功能需要的始终周期，以及发生冲突时写入时钟周期，测试查找功能的时钟周期，以及发生冲突的情况下查找需要的时钟周期。因为当数据量足够大的时候，才会产生冲突，所以要不断增加发包数量直到产生冲突后，再测试冲突模式下写入和查找需要的时钟周期，根据测试结果与顺序查找法和Hash查找法进行比较结果，以此可以直观的看出优化的好处。
基于以上考虑，要逐渐增加发包数量，产生冲突，来判断在常规时候和极限状态下，写入和查找模式下的CAM性能，因此我做了以下三次发包实验来做数据分析：
连续写入100个64 bit的数据，这些数据的内容是随机的，是不相同的，然后依次将数据读出来与输入数据对比是否存在丢包，然后开启查找模式，查找第100个数据；
连续写入1000个64 bit的数据，这些数据的内容是随机的，是不相同的，然后依次将数据读出来与输入数据对比是否存在丢包，然后开启查找模式，查找第1000个数据；
连续写入10000个64 bit的数据，这些数据的内容是随机的，是不相同的，然后依次将数据读出来与输入数据对比是否存在丢包，然后开启查找模式，查找第1000个数据；
测试部分代码如下：
4.3. 验证结果
验证工具Questasim 10.6c上，通过Verilog建立的验证环境对CAM控制器的功能进行了完整测试。并通过写测试tb，对CAM表产生大量随机数，进行数据写入，从仿真波形中可以看出CAM控制器状态机跳转过程，从初始化——数据算法——冲突计算——数据写入——数据读取——数据比对，可以看到各个过程，最后我们我在tb中将比较结果产生了输出文件，以及发包数量由少变多的情况下，冲突数量的变化的记录，如图4。
我们将测试结果与顺序查找法和Hash查找法从几个维度做了清晰直观的比较，包括写入，查找所用时钟周期对比，从而反应性能的好坏，通过对内存资源的使用进行对比，从而反应资源情况的好坏。
我们通过测试结果可以发现，在资源使用上，如图5，优化查找法，相比于顺序查找法的使用资源会相对多一些，但是明显少于Hash查找法的资源，在写入和查找时钟周期上，顺序查找法需要一一比较，当查找后面数据的时候，时钟周期明显变多，与Hash查找法相比，如果没有存在冲突的情况下，如图6和如图7，没有产生冲突，写入和查找时钟周期相同，如图8中，在极限情况下，因为连续写入大量数据，产生了冲突，所以查找周期会比Hash查找法多一些。
通过实验我们可以得出结论，优化查找法是一种相对折中的办法，虽相比于顺序查找法多了一些资源，但是性能明显提升，相比于Hash查找法，只有在极限情况下，性能会稍微降低，但是会少了很多资源，因此优化查找法完全具备可行性。
5. 结束语
用FPGA设计CAM存储器，方法简便、使用灵活、匹配速度快，本文基于FPGA设计CAM存储器，在传统的查找算法上，基于CRC32算法的原理，将其融入在CAM查找算法的机制里，实现了查找速度快，实现简单的原理，将设计代码，基于xilinx的开发板，使用modelsim进行仿真，使用verilog和systemverilog写testbench进行性能测试，测试性能完全达到预期效果。