突破内容可寻址存储的扩展性瓶颈：一种用于大键关联搜索的概率化替代方案

摘要
人工智能总结：要查看此由人工智能生成的总结，您需要拥有高级访问权限。了解更多信息并登录。

摘要内容
内容可寻址存储器（CAM）具备高速、确定的查询能力，但在处理超过100比特的大型输入键时面临严重的扩展性挑战，从而导致过高的能耗、芯片面积和内存成本。本文介绍了概率CAM（P-CAM），这是一种新型架构，通过放弃严格的确定性以换取内存效率与扩展性来克服这些限制。P-CAM利用哈希技术将高维输入压缩为固定大小的指纹，从而使内存需求与键长无关。它在保持CAM的恒定时间查询优势的同时，还能支持那些传统CAM难以处理的大键应用，如网络通信、生物信息学和机器学习领域。在Xilinx UltraScale+设备上的FPGA实现表明，当处理384比特键时，P-CAM能够保持恒定的查询延迟，并在资源效率方面比专为较窄输入设计的现有最佳确定性CAM高出15倍。尽管P-CAM的概率特性会导致轻微且可控的误报率，但其在特定约束条件下也可配置为完全确定性的操作方式。据我们所知，P-CAM是首个将基于指纹的概率数据结构作为关联查询主要存储机制的CAM架构，这使其有别于那些仅限于集合成员检测的先前概率方法，为现代数据密集型系统提供了强大且可扩展的替代方案。

人工智能总结

人工智能生成的总结（实验版）：该总结是通过自动化工具生成的，并非由文章作者撰写或审核。它旨在帮助人们发现相关内容、评估文章相关性，以及便于相关研究领域的读者理解本文内容。它是对作者提供的摘要的补充，而作者提供的摘要仍是论文的核心总结。完整文章才是最具权威性的版本。点击此处了解更多信息。点击此处对这篇总结的准确性、清晰度及实用性发表意见，您的反馈将有助于改进未来的生成版本。要查看此由人工智能生成的通俗语言总结，您需要拥有高级访问权限。

1 引言
内容可寻址存储器（CAM）是一种专用关联存储器，用于高速执行成员查询和内存查找，尤其广泛应用于硬件领域。与传统随机存取存储器（RAM）不同，RAM是通过特定的内存地址来检索数据，而CAM则是根据数据内容本身来确定存储数据字的地址。CAM会并行搜索整个内存阵列以找到数据字并返回存储的地址，从而实现O(1)的恒定查询时间复杂度[38]。这种并行搜索能力使得CAM在需要确定性强、低延迟响应时间的网络应用中极为重要，例如数据包分类、IP路由、防火墙过滤、访问控制列表（ACL）以及网络中的服务质量保障[27, 28, 38, 54]。除了网络领域外，CAM还应用于数据库索引、缓存管理、模式识别，以及计算生物学中的高通量应用，比如DNA/RNA序列比对[22, 25]。

从历史上看，CAM最初出现在网络设备中，尤其是路由器和交换机中，因为这些设备需要以线速处理数据包，必须快速将数据包头部与路由表或访问控制表进行匹配。它们的单周期性能、确定性行为以及适合硬件实现的特性，使其成为实时系统的理想选择。然而，这些优点也伴随着诸多挑战。CAM以其较高的动态和静态功耗、庞大的芯片面积需求、复杂的硬件结构、较大的内存占用以及有限的扩展性而著称[38]。在诸如太比特以太网这类高速网络环境，以及数据中心交换机这类大规模部署场景中，这些问题尤为严重。而在现场可编程门阵列（FPGA）这类对功耗和资源要求极高的平台上，这些问题更为关键，因为FPGA越来越被用于硬件加速和网络内计算[40, 56]。

根据匹配能力的不同，CAM架构大致可分为两类。最基本的类型是二进制CAM（BCAM），它仅使用0和1存储数据，并进行精确匹配。为了支持更复杂的搜索模式，三进制CAM（TCAM）在传统BCAM架构的基础上引入了“无关状态”，用于处理部分匹配，从而支持前缀匹配和通配符搜索。图1展示了RAM、BCAM和TCAM在操作行为上的差异。TCAM的三进制特性对于IP路由中的子网匹配、数据包分类以及ACL评估等应用至关重要。不过，TCAM也加剧了BCAM的缺点，因为三进制逻辑使得存储复杂度增加三倍，功耗上升，而且由于需要额外的匹配和掩码存储电路，进一步限制了其扩展性[9]。由于BCAM和TCAM都以固定长度的位向量存储完整条目，因此随着键宽和数据集规模的增加，它们的扩展性会逐渐下降[43]。这会导致路由延迟增加、工作频率降低，同时在现代高速硬件平台上实现时序约束也变得更加困难[21]。

图1. RAM、BCAM和TCAM在操作上的差异[42]。RAM返回存储在输入地址处的数据。BCAM返回输入数据与存储数据完全匹配的地址。TCAM则存储（数据，掩码）对，并返回所有满足输入数据与存储数据匹配条件的地址，同时考虑掩码的作用（即通配符匹配）。

应用领域与新兴需求
除了传统的网络应用之外，CAM也在一些新兴领域重新受到关注。例如在网络安全领域，CAM被用于识别大量数据流[3]、检测入侵模式[19, 29]或执行深度数据包检测[58]。这些应用通常需要对总共104比特的IPv4五元组字段，或IPv6中更大规模的字段进行匹配[53]。在生物信息学领域，大规模的序列比对任务常常需要在DNA/RNA序列中搜索基因模式。一个64个碱基的DNA序列，若每个碱基用2比特编码，则需要128比特；而一个64个残基的氨基酸序列，若用5比特编码，则需要320比特[10]。这些需求远远超出了CAM通常优化的输入规模。更大的模式还会增加复杂性，因为它们需要分割处理，并通过多次CAM操作才能完成整体匹配。此外，在机器学习硬件、图分析以及边缘人工智能等领域，人们也越来越倾向于使用关联存储原语来实现快速最近邻搜索、输入模式匹配和特征向量比较，从而拓展了类似CAM的结构在数据密集型、基于模式计算中的应用范围[24]。

这些应用领域可以根据其对错误的容忍程度进行大致分类：
确定性应用场景：如IP路由、防火墙过滤和ACL等任务要求严格的正确性保证，任何误报或漏报都是不可接受的。传统的BCAM和TCAM架构由于其确定性行为，非常适合这类应用场景。
概率性与统计性应用场景：其他领域，如大规模网络流量监控、近似集合成员检测、生物信息学序列匹配以及机器学习模式匹配等，往往可以容忍一定程度的错误，以此换取更高的扩展性和资源效率。

尽管BCAM和TCAM架构在处理确定性任务时表现良好，但由于其结构的僵化性，以及随着输入宽度增加而出现的扩展性和实现方面的挑战，它们已难以满足现代应用的需求。这些架构不适合那些需要低功耗、动态键值关联，或能够将多个键映射到同一标签/类别的应用场景——这在分类、异常检测和流量聚合等任务中是必不可少的。

贡献
为了解决传统CAM的局限性，本研究提出了一种概率CAM（P-CAM）架构，它提供了一种可扩展、资源效率高的设计，尤其适用于需要容错的应用。此处所说的“传统CAM”指的是常规的BCAM设计；不过，由于TCAM的内存成本更高，它同样存在扩展性难题。P-CAM还提供了在特定运行约束或静态工作负载下支持确定性应用的机制，从而将其适用范围扩展到不仅仅是纯概率领域。

本研究的主要贡献如下：
—提出了P-CAM，这是一种基于概率关联存储的新型CAM架构，它仅存储紧凑的指纹而非完整键值，通过放弃严格的确定性来克服CAM在键宽扩展性方面的局限。这使得能够在保持恒定时间查询性能的同时大幅节省内存，并通过同步更新/查询操作以及多键到类别的映射，支持现代的动态工作负载。
—通过基于哈希的指纹技术实现了固定内存占用设计，使内存需求与输入键宽解耦，从而为那些输入键极大以至于传统CAM无法使用的应用，提供可扩展且高效的硬件加速搜索方案。
—该架构具有灵活性，能够在精度与资源使用之间实现可控的权衡，并可通过可调参数满足特定应用的对误差容忍度要求。它还可以在受限条件下配置为确定性操作，从而使其能够应用于关键任务。
—通过对P-CAM进行了基于FPGA的全面实现与评估，证明了其在实际应用中的可行性、恒定时间延迟以及相比现有最佳CAM设计更高的资源效率，尤其是在处理宽输入数据时。

2 背景与动机
2.1 CAM架构及其局限性
由于具有单周期延迟和良好的硬件兼容性，CAM几十年来一直是优化工作的重点。虽然目前大多数研究集中在晶体管级改进和节能电路设计上，但这些方法忽视了扩展性和对新应用场景的适应性等根本性挑战[8, 18, 25, 30, 38, 41, 44]。对于前缀匹配和IP查找等网络任务，基于字典树的方法和哈希表等软件替代方案虽能实现内存高效，但受限于顺序内存访问速度，因此不适用于高速应用[46]。一些混合方法，如将字典树方法与基于哈希的成员查询相结合[4, 31]，通过仅在哈希查询结果为正时才进行片外内存访问，从而减少了此类访问。尽管如此，对片外内存的依赖仍会导致较高延迟，因此这类方法在资源受限设备上的延迟敏感型应用中适用性较差。分层CAM[37]和分区架构试图将搜索范围限制在较小的块中，从而降低部分查询的延迟，但随着数据集规模的扩大，扩展性依然是个瓶颈。

在FPGA上的一些内存优化型CAM架构，如DSCAM+ [55]、HLSCAM [1]和SplitBucket [47]，通过牺牲FPGA上的查找表（LUT）资源来有效减少内存使用。其中SplitBucket和HLSCAM完全消除了内存的使用，而DSCAM+则采用混合方式平衡LUT和内存的使用，对于低比特宽度的输入较为有效。SplitBucket和DSCAM+主要用于IPv4路由表的前缀匹配，因为其前缀长度通常限制在32比特以内。但由于其架构复杂性，当输入规模增大时，其性能会下降，因此这类架构并不适合处理更大规模的输入。HLSCAM的目标输入宽度为150比特，但其逻辑资源效率较低。这些架构可能难以很好地扩展，以适应IPv6头部、五元组流量记录或编码后的生物序列中所常见的非常大型的输入宽度。关于这些架构在资源效率方面的详细讨论见第4.3节。

5.2.2 概率性方法
布隆过滤器[5]、库库过滤器[15]以及哈希表[26, 36, 49]等概率数据结构，已被视为潜在的CAM替代方案，尤其适用于处理较大规模的输入。虽然这些结构在输入比特宽度和表大小方面具有更好的扩展性和内存效率，但它们也存在明显缺陷，因为它们需要在精度与确定性之间做出妥协。布隆过滤器和库库过滤器虽能实现紧凑存储和快速的成员检测，但却无法检索关联的数据或内存地址，因此在键值存储或表查询场景中的实用性有限。包括库库[36]和孔雀变体[26]在内的哈希表虽然可作为键值存储使用，但由于严重的哈希冲突，它们需要更大的内存空间才能获得可接受的精度[49]。此外，尤其是在高负载情况下，它们非确定性的内存访问延迟也使其不适合作为高速应用的选择[51]。

虽然概率方法为提升扩展性提供了一条路径，但有必要区分不同的架构目标。其中一类是近似关联存储器，专为相似性搜索而设计。诸如基于汉明距离的CAM[17]以及利用局部敏感哈希的技术[33]，都是为了识别与查询项相似但不一定完全相同的项而设计的。通过刻意增加相似输入之间的哈希冲突，这类技术在模式识别和近似最近邻搜索任务中表现出色。然而，由于它们本质上就是为降低精度而设计的，因此不适合那些需要精确匹配的临界应用，如IP路由。这类数据结构既无法复制CAM的核心功能，也无法实现良好的精度与内存消耗之间的平衡。因此，当前仍迫切需要创新的CAM架构，以便在扩展性、低延迟运行以及硬件兼容性等方面满足现代应用的需求。

此前已有研究尝试将概率数据结构用于增强CAM的功能。不过，这些研究主要侧重于概率性的成员检测，而CAM架构本身仍采用传统设计。Ooka等人[35]在一种以内容为中心的路由器中，用布隆过滤器增强了基于传统CAM的名字查找引擎。不过，其概率性功能仅限于使用布隆过滤器进行成员预检测，而实际的匹配操作仍由传统CAM来完成。同样，Pontarelli和Ottavi[39]将布隆过滤器与传统的TCAM结合使用以实现错误检测/纠正，而TCAM的常规查找依然保持精确性。pbCAM[52]则采用多个带有哈希索引的传统CAM存储单元以及布隆过滤器来检测某个条目的存在性。尽管这种基于概率的存储设计能够节省能源，但一旦选定正确的存储单元，实际的CAM查找仍会进行精确匹配。Byun等人[6]更进一步，完全用向量布隆过滤器替代CAM来执行IP查找。不过它仅能进行类似布隆过滤器的成员查询，功能类似于压缩后的查找表，无法提供能够检索与匹配键相对应的地址或值的关联内存功能。基于忆阻器的近似CAM方案[19, 45]则试图通过模拟方式实现类似BCAM或TCAM的功能，但其行为本质上仍是确定性的，任何观察到的误差都源于模拟过程中的不确定性，而非基于哈希的刻意概率设计。总而言之，这些研究均未实现完全基于概率架构的内容寻址存储器或关联内存阵列。它们要么在传统CAM的基础上加入概率算法，要么将概率效应视为需要最小化的错误，而非作为一项功能加以利用。相比之下，P-CAM独特地提出通过其架构使CAM的匹配操作本身具有概率性，并将这种不确定性作为正常操作的一部分来提升效率。这意味着P-CAM的行为和贡献与以往的研究有本质区别，因为它在匹配和存储过程中都刻意引入了概率性，而其他方案要么提供严格确定的匹配结果，要么仅在辅助机制中引入概率性，而非在核心CAM架构中。

2.3 P-CAM方法：一种概率性替代方案

鉴于CAM存在的这些局限性，人们越来越需要可扩展、低功耗且可重配置的关联内存架构。为克服CAM在可扩展性和效率方面的限制，本研究探讨了一种根本性的权衡方案：放弃传统CAM的确定性保障，采用概率性方法，在保持恒定时间查找速度的同时实现大规模扩展。我们提出的P-CAM基于SPArch[50]架构，该架构具有出色的内存效率和可扩展性，非常适合大规模应用场景。与以往仅支持集合成员检测的概率结构不同，P-CAM采用了一种独特的架构设计，以基于指纹的概率数据结构作为其主要存储和匹配机制，用于关联查找。据我们所知，这是首个完全整合此类设计的CAM架构。P-CAM利用基于哈希的技术将高维输入数据编码为紧凑的固定长度指纹。与传统CAM存储完整宽度的键不同，P-CAM的内存占用与输入键的宽度无关，这大大降低了能耗、芯片面积和计算复杂度。通过容忍一定比例的可控误报，并利用硬件友好的哈希技术的固有并行性，P-CAM在速度、可扩展性和灵活性之间实现了平衡，同时保持了恒定时间（O(1)）的查找性能。这些特性使得P-CAM尤其适合处理键长度极大的应用场景，比如网络、生物信息学和机器学习领域，因为在这些领域中传统CAM会受到面积和功耗的限制。由于P-CAM采用灵活的哈希方案，通过草图数组将键映射到内存位置，而非为每个条目分配固定的专用存储空间，因此它天然支持多键到类别的关联以及动态更新，非常适合那些需要超越简单精确匹配功能的现代动态工作负载。草图是一种二维内存数组，它利用多个独立的哈希函数紧凑地存储输入数据，从而支持带有有限误差的近似查询操作，如成员检测、频率估算或相似性检测[11]。草图以牺牲精确性为代价换取空间和时间效率，特别适用于高速数据流处理。作为一种基于草图的架构，P-CAM非常适合实时处理数据的应用场景，因为这些场景要求对输入数据进行实时处理和汇总。因此，P-CAM的硬件实现支持同时进行更新和查询操作，提升了其在实时网络流量监控[13]及类似数据密集型应用中的性能。表1提供了传统BCAM、TCAM和P-CAM的高层对比。还需要注意的是，概率CAM与近似匹配CAM是不同的概念。后者是一种旨在在指定距离度量标准（如汉明距离）范围内查找匹配项的架构，而概率CAM则是通过具有内在且可控误差概率（误报率）的算法数据结构来模拟CAM的行为。第3.3节和第3.4节将分析P-CAM的误差概率及其对精度要求较高的应用的影响，包括降低误报率并保证正确性的相关机制。

表1. 特性
BCAM TCAM 概率CAM
匹配类型 精确匹配 精确匹配+通配符 带误差概率的精确匹配
查找延迟（周期数） 非常低（1周期） 非常低（1周期） 低（恒定，几周期）
查找延迟（微秒） ∝ CAM大小 ∝ CAM大小 恒定（与CAM大小无关）
可扩展性 低 非常低 高
结果确定性 是 是 否（允许误报）
查找时间复杂度 O(1) O(1) O(1)
搜索电路复杂度 O(n) O(n) O(1)
内存效率 中等 低 高
硬件复杂度/面积 高 非常高 低
功耗 高 非常高 非常低
主要应用场景 数据库、缓存 IP路由、ACL、深度包检测、防火墙过滤 网络流量监控、大规模相似性搜索、机器学习、生物信息学

BCAM、TCAM与概率CAM的比较
n——CAM中存储的条目总数。加粗的条目表示在各自类别中表现最佳或最有利的结果。

3 P-CAM的架构

P-CAM的设计借鉴了SPArch[50]的核心草图机制，而SPArch原本是为网络流量测量设计的架构。通过有策略地省略SPArch的计数器数组并修改其草图组件，P-CAM被转化为一种新型的轻量级架构，可作为通用关联内存使用，与其概念上的前身有着截然不同的应用场景。图2展示了P-CAM的架构。草图组件被实现为一个尺寸为m×d的二维内存数组，其中d表示行数，m表示每行的单元格数。对于给定的元素x，它通过d个独立的哈希函数hi(x)（i=1,…,d）映射到草图中每一行i的某个单元格中。对于每个x∈X，hi(x)的值是一个介于0≤j≤m−1之间的整数，其中X是所有元素（或键）的集合。P-CAM的一个核心组成部分就是哈希函数。由于P-CAM的内存需求与输入条目的大小无关，因此由哈希函数来应对输入大小的差异。只要哈希函数能够处理最大的输入宽度即可，因为较小的条目可以通过填充零来匹配哈希函数的输入块大小。P-CAM中使用的哈希函数将在第4.1节中详细说明。图2展示了P-CAM架构的框图，其中包含了哈希函数、草图数组（指纹-地址单元）、地址生成器以及值存储部分。所提出的P-CAM架构包括由指纹-地址单元组成的草图数组、哈希函数、地址生成器以及值存储内存。草图中的每个单元格被称为指纹-地址单元（FAC），它存储一个由元素的指纹f和对应地址A组成的元组(f,A)。在我们的设计中，草图指的是那些共同实现P-CAM的概率匹配和压缩存储功能的FAC数组。指纹是通过指纹函数f(x)计算得出的，该函数利用哈希函数将键映射为简短的固定长度二进制表示形式。地址则由一个简单的计数器模块AdGen生成，每次新增条目时该计数器都会递增，其计算公式为Axnew=Axprev+1，其中Axprev是上一个分配的地址。由于地址仅在新增条目时递增，因此它可以作为逻辑时间戳，用来标记每个条目的相对年龄。为了实现键值存储的功能，还专门分配了一块内存区域V用于存储值。该内存区域的深度即为要存储在P-CAM中的元素数量n，这一数值也相当于AdGen的最大值。一旦达到最大值，就会触发内存已满的标志，阻止进一步的插入操作。由于计数器不会回绕，因此避免了因地址重复使用而导致最新条目被误判为旧条目的风险。值是通过FAC中对应元素的地址映射到内存中的：V[Ax]→元素x的值。单个内存数组的总内存需求为m×(k+a)比特，其中k和a分别表示f和A的比特大小，a=log2⁡(n)。表2列出了P-CAM架构中使用的各种符号规范。表2. x 输入键 b 输入比特宽度 d 草图深度/草图内存数组数量 m 草图宽度 n P-CAM中不同条目的数量 A 值存储内存位置的地址 a 地址的比特大小（log2⁡Nc） FAC 指纹-地址单元 f 指纹 k 指纹的比特大小 hi 用于索引草图第i行的哈希函数 f(x) 指纹函数 V 值存储内存 Pfp 误报概率 α 负载因子（nm） c 置信度值 T 表大小（=m） w LUTRAMs的权重因子 E 标准化效率指标

P-CAM架构及分析中使用的符号规范

P-CAM的更新、查询和删除操作将在后续章节中详细介绍。算法1.3.1给出了P-CAM中更新、查询和删除操作的伪代码。

3.1 P-CAM的核心操作

更新。要向P-CAM中添加新元素x，首先需要计算它的指纹（fx = f(x)），然后确定d个由哈希索引标识的FAC，即FAC[i,hi(x)]，其中i=1,…,d。如果这些哈希索引对应的FAC中有任何一个为空，那么就直接用新的指纹以及AdGen生成的地址（Ax）来更新该FAC（算法1，第5–9行）。此时该FAC的内容变为(fx,Ax)。如果所有被索引的FAC都不为空，且没有找到匹配的指纹，则需要考虑以下两种情况：(i)相同指纹对：如果有多个FAC包含相同的指纹-地址对，那么可以随机选择一个相同的FAC，或者选择数组中第一个匹配的FAC，然后用新的指纹和地址来更新它（算法1，第11–14行）。(ii)不同指纹对：如果所有的指纹-地址对都是唯一的，那么就选择地址最小的FAC来替换，因为地址相当于逻辑时间戳，可用于记录条目的插入顺序，而被替换的FAC对应的条目就是最旧的条目（算法1，第15–18行）。虽然当内存大小分配合理时，出现这种情况的概率较低，但如果不想覆盖现有的FAC，也可以通过设置内存已满的标志来拒绝插入操作，从而避免出现误报的情况。原来的SPArch算法允许通过替换最旧的条目来进行插入，因为对于那些需要检测频繁出现的流量之类的应用来说，较旧或过时的网络流量其实并不重要。关于误报现象及其消除方法的更多讨论见第3.5节。每次完成更新后，AdGen的值都会递增。如果至少有一个FAC包含匹配的指纹，那么该元素就被视为已经存在，无需再采取其他操作（算法1，第20–21行）。

查询。图3展示了P-CAM查询操作的工作流程图。要查询元素x，首先需要计算它的指纹（fx=f(x)），然后找出所有由哈希索引标识的单元格，即FAC[i,hi(x)]，其中i=1,…,d。如果这些哈希索引对应的FAC中有任何一个为空，或者所有FAC都已满但不存在匹配的指纹（∀(ft,At)∈FAC[i,hi(x)],ft≠fx），那么该元素就被视为不存在（算法1，第24–25行）。图3展示了P-CAM查询过程的工作流程图。首先将输入数据得到的指纹（FP）与哈希索引对应的FAC进行比较，然后返回与匹配指纹相对应的地址（A）。如果所有的FAC都被占用，且存在至少一个匹配的指纹，那么只有当所有对应的指纹-地址对都完全相同时，该元素才被视为存在（{(ft,At)∈FAC[i,hi(x)]∣ft=fx}），此时就会返回对应的地址（算法1，第26–28行）。而在所有FAC都已占满，且存在多个匹配指纹，但至少有一个对应的地址不相同的情况下（即存在多个(fx,At)，其中At并不唯一），则需要考虑以下两种情况：(i)在所有不相同的指纹-地址对中，如果某个地址A∗出现的次数最多，那么就选择它作为查询结果（算法1，第30–31行）。(ii)如果不存在出现次数最多的地址，那么就选择地址最大的那个配对作为查询结果，即max{At∣(ft,At)∈FAC[i,hi(x)] ∧ft=fx}（算法1，第32–33行）。这是因为较旧的条目在多个FAC中被复制的概率要高于最新的条目。由于地址同时也可作为逻辑时间戳，因此地址最大的条目对应最新的输入。若要删除某个条目x，首先需按照查询操作中的步骤执行查询，以定位对应的FAC。随后再清除这些已识别FAC中的内容（算法1，第35–39行）。

3.2 作为键值存储的功能
为使其能充当键值存储，还需增加一个用于存储值的额外内存块V，如图2所示。存储在FAC中的地址则用作访问存储内存的索引。在添加新元素时，需遵循算法1中的updateCAM流程，并使用生成的地址来更新对应的内存位置。如果该元素已存在，则会获取匹配的地址，并在该地址对应的内存位置更新相关值。在执行查询时，则会获取V中与该元素地址相对应的值。图4进一步展示了在此场景下P-CAM与传统CAM的区别。与传统CAM将每个键映射到固定地址位置不同，P-CAM支持更灵活的键与值之间的关联方式，允许多个不同的键映射到同一个地址或类别。这种多键对应单一类别的特性在分类任务中尤为有用，因为语义上相近的键可以共享相同的输出和内存位置，从而降低存储开销。图4展示了(a)传统CAM与(b)P-CAM架构的对比，说明了P-CAM如何支持将多个键分类到同一值类别中。在该示例中，键x1和x2都被映射到相同的类别值（VAL=1）。

3.3 错误阳性概率分析
P-CAM的错误阳性概率由三个因素决定：哈希碰撞（即两个不同元素被映射到同一位置）、指纹碰撞（即两个不同元素生成相同的指纹），以及FAC中的地址不匹配问题。当两个或多个不同元素通过哈希函数被映射到同一行的同一索引位置时，就会发生哈希碰撞。若出现指纹碰撞，还必须对应地址也相同，才会导致错误阳性结果。地址不匹配则仅可能在更新过程中，在指纹碰撞之后发生。如果两个元素拥有相同的指纹但地址不同（这种情况出现在某个元素首次出现时，此时至少有一个已存在的FAC包含该指纹，而另一些FAC为空，说明该元素是新的），这种差异有助于在更新和查询操作中区分它们。这样的区分机制增加了额外的验证层，大幅降低了错误阳性的可能性，确保仅靠指纹碰撞不足以引发错误阳性结果。

在所研究的结构中，设d为该行中的元素数量，m为每行中的FAC数量，n为整个结构中的总条目数。每个条目都会通过d个独立的哈希函数被映射到所有d行中。根据生日问题[57]，并在均匀哈希的假设下，单行中不发生哈希碰撞的概率为：P(无哈希碰撞，行)=∏i=0^n−1(1−im)。当m远大于n时，可通过指数近似简化该表达式：当n≪m时，P(无哈希碰撞，行)≈e^−n(n−1)^2/m。这一近似成立的前提是插入的元素数量远小于可用行的总数，这样才能保证概率值介于[0,1]之间。某行中至少发生一次哈希碰撞的概率则为：P(有哈希碰撞，行)=1−e^−n(n−1)^2/m。（1）

对于指纹碰撞的概率，设指纹长度为k位。在插入n个元素后仍不发生指纹碰撞的概率为：P(无指纹碰撞)=∏i=0^n−1(1−i^2/k)。对于较大的2k值，可利用生日问题近似公式，得到：P(无指纹碰撞)≈e^−n(n−1)^2/k+1。因此至少发生一次指纹碰撞的概率为：P(有指纹碰撞)=1−e^−n(n−1)^2/k+1。（2）

在单行中，哈希碰撞与指纹碰撞同时发生的综合概率为：P(综合碰撞，行)=P(有哈希碰撞，行)×P(有指纹碰撞)。至于FAC中的地址不匹配概率，设地址长度为a位，则该概率为：P(地址不匹配，行)=1/2^a。（3）

整体而言，在所有d行中，假设各哈希函数相互独立，P-CAM的错误阳性概率Pfp为哈希碰撞、指纹碰撞及地址不匹配概率的综合值，即：Pfp=(P(综合碰撞，行)×P(地址不匹配，行))^d。将上述两个概率表达式代入后可得：Pfp=((1−e^−n(n−1)^2/m)×(1−e^−n(n−1)^2/k+1)×1/2^a)^d。（4）

同样的公式也适用于采用P-CAM的键值存储架构的错误概率计算。此处重点分析错误阳性问题，是因为P-CAM完全可以被配置为完全避免错误阴性结果。基于草图的结构在正常运行情况下本身就不会出现错误阴性结果；而当P-CAM在未启用覆盖功能且运行负荷未达满载状态时（参见3.5节），每个插入的键的指纹都会被保存在所有相关的FAC中。因此，在没有删除操作或插入时不会发生条目被移除的情况下，查询时总能检测到有效条目，这使得错误概率天然地只可能偏向某一侧。仅在高负荷且允许覆盖操作的场景下，才可能因条目被移除而出现错误阴性结果，不过这种权衡是可选的，且取决于具体应用需求。关于如何在确定性场景下减少P-CAM中的错误阴性问题，将在3.5节3.4小节中详细讨论。

3.4 利用置信向量控制准确性
在内存阵列中的FAC中找到的匹配数量可以被编码为一个长度为d的比特数组，即置信向量。该向量反映了出现错误阳性的可能性：设置位越多，说明对查询结果的置信度越高。用户可以设定一个阈值，根据置信向量的数值来判断是否接受该结果。例如，当d=4时，只有当置信向量中至少有两个比特被设置为1时，才接受该查询结果。在那些将数据存储在外部内存的混合系统中，对于置信度较低的查询结果，还可通过在外部内存中进行额外查找来加以验证。由于匹配数量是在查询过程中实时计算出的，因此报告置信向量不会带来额外的计算开销。关于查询置信度的更详细评估内容可见4.3.4节。在那些对准确性要求极高的应用领域，比如IP路由系统中，仅依赖概率匹配可能会因错误阳性结果而不够可靠。在这种情况下，置信向量就起到了可靠性过滤的作用：置信度较高的结果（例如匹配了所有d个数组的结果）会立即被接受，而置信度较低的匹配结果则会触发进一步的验证步骤，通过速度稍慢但更为精确的备份内存来进行确认。这种选择性确认机制有效地降低了错误阳性带来的影响，使系统能够始终保持100%的功能准确性。从设计角度来看，如果事先已知总条目数n，那么就可以通过调整指纹长度k、FAC数量m以及内存阵列数量d等参数，来限制错误阳性概率，正如公式（4）所示。通过这样的参数优化，P-CAM既能在保证准确性的同时，又能合理控制资源使用效率。

3.5 确定性操作与错误缓解
当内存接近满载状态时（即负载因子α=nm趋近于1.0），P-CAM的行为会出现一些关键变化。如算法1中所描述的，如果一个新的条目经过哈希处理后被映射到d个位置，却找不到空闲或匹配的FAC，那么更新策略就会用地址最小的那个最旧条目来替代它。这种移除策略源自SPArch架构，它在处理类似网络中高频出现的动态数据流时十分有效，因为那些较旧、相关性较低的条目会自然被丢弃。然而，对于通用型的CAM应用来说，这种替换方式却可能导致错误阴性结果。这种情况只有在所有d个候选位置都被不同的、不匹配的指纹占据时才会发生，此时就不得不移除其中最旧的那个条目。因此，某个特定条目被移除的概率取决于负载因子、新条目的插入速度以及该条目的存在时长。需要强调的是，移除操作并不总是会导致错误阴性结果，因为由于初始哈希碰撞较少，较旧的条目往往会被存储在多个位置上。

为了满足那些不能容忍错误阴性结果的应用需求，P-CAM提供了一种可配置的机制。如3.1节中的更新算法所述，可以通过设置内存已满标志来拒绝新的条目插入，而无需覆盖现有的条目。系统只需监控这一标志，就能在内存未满之前保持确定性运行。对于那些数据集较为静态或准静态的应用，比如已经收敛的IP路由表，可以先将P-CAM预加载，之后再关闭后续的更新功能，这样一来就能完全避免出现错误阴性结果。只要数据集的大小在配置的内存容量范围内，P-CAM就能为这类需要确定性运行的应用提供支持。

4 硬件实现与性能评估
我们使用Verilog HDL在FPGA上实现了P-CAM，并从延迟、资源利用率以及准确性等方面对其性能进行了评估。P-CAM的硬件架构框图如图5所示。我们在96位和384位两种不同的输入规模下对该实现方案进行了测试。输入数据通过专门的96位和384位哈希函数进行处理，单个哈希函数实例即可生成所需的哈希比特，这些哈希输出会被进一步拆分，从而得到将输入x映射到草图内存中的哈希值。地址选择逻辑则会输出被查询输入的存在状态、其地址以及置信向量。地址生成器则采用计数器实现，其最大计数值设置为n，即需要存储的元素总数。图5展示了P-CAM的硬件架构，其中的草图存储模块采用了双端口BRAM实现，同时为更新操作和查询操作设置了独立的数据路径，从而支持实时进行查询和插入操作。

4.1 架构特点
同时支持更新与查询。P-CAM的硬件架构能够同时处理更新和查询操作，这提升了它在高吞吐量场景下的适用性，尤其适合实时网络流量监控之类的应用。传统的概率数据结构通常只有一条用于更新和查询的数据路径，这不仅限制了并行操作的速度，还会在流水线处理过程中引入数据冲突问题。相比之下，P-CAM架构则包含了两个独立的哈希函数模块以及两条分别用于更新和查询的独立数据路径，这两条数据路径都由两个有限状态机来控制。由于草图存储部分采用了双端口BRAM，且为读写操作配备了专用端口，因此才得以实现这种同步操作。此外，这种设计还能通过减少关键数据路径的数量，提升系统的运行频率，进而优于传统的单数据路径架构。

哈希函数。依赖哈希机制会带来一定的安全风险。具体来说，攻击者有可能刻意构造特殊的输入，从而引发哈希碰撞，进而提高错误阳性率或破坏已存储的条目。为降低这类风险，P-CAM采用了具有强雪崩特性的哈希函数，以确保输入数据能够均匀分布。虽然我们假设使用d个独立的哈希函数，但这在硬件实现上效率极低。一种常见的优化方法是采用基于两个基础哈希函数的更复杂的哈希方案[23]，不过更为高效的做法则是使用一个输出宽度较大的单一哈希函数，然后通过对该函数的输出进行分割，从而得到多个几乎独立的哈希值。不过，整个方案的有效性最终还是取决于所选哈希函数的统计特性。

通常人们会使用哈希函数将一个较大的键压缩为一个较小的地址值（例如log2(m)位），而这正是导致哈希碰撞的根本原因。P-CAM则避免了这个问题，它使用的哈希函数不会对输入数据进行压缩，同时还具备强大的雪崩特性。为此，我们采用了Xoodoo-NC[48]作为哈希函数，这是一种经过简化的、非加密版本的Xoodoo排列算法[12]，属于轻量级设计。Xoodoo-NC具有很强的雪崩特性，包括较高的熵值、权重以及较好的依赖性，而且其输出块大小至少与输入块大小相当，因此它实际上是一种抗碰撞的映射机制，而非容易引发碰撞的压缩工具。采用这种单一哈希函数的方式，不仅是一种硬件层面的优化，更是一种更为可靠的概率设计思路，它用高精度的排列操作取代了有损的压缩步骤。

在[48]中提出了Xoodoo-NC的96位版本，该版本仅基于Xoodoo排列状态表中的一层数据进行生成。Xoodoo算法的一轮处理仅包含移位、与运算以及异或运算，因此其逻辑复杂度较低，处理延迟也较小。这些运算通过完全展开的架构实现，全部由组合逻辑构成，使得整个哈希值能够在单个时钟周期内计算完成。Xoodoo-NC可通过增加运算轮数（超过满足雪崩效应所需的轮数），并将得到的输出结果拼接起来，从而生成任意96位倍数的输出宽度。我们进一步改进设计，让384位输入版本的哈希函数能够充分利用384位的Xoodoo排列状态。96位版本的Xoodoo-NC哈希函数仅需2.5轮排列即可满足雪崩效应要求，而384位版本则需要4轮。在我们的实现中，96位Xoodoo-NC采用了3轮运算。384位输入宽度下的哈希计算延迟仅为2.86纳秒，且该哈希函数可在每个时钟周期处理一个输入。由于其逻辑深度较低且无需使用内存，与常用的非加密哈希函数如FNV-1a和Murmur hash相比，它所消耗的资源和能量更少[14, 16]。雪崩特性通过三个指标来体现，即雪崩依赖度（Dav）、雪崩权重（w―av）以及雪崩熵（Hav），分别代表相关性、扩散性和随机性。表3展示了在Kintex Ultrascale+ FPGA上该哈希函数的雪崩特性及硬件性能表现。关于Xoodoo-NC的详细硬件分析、雪崩指标的定义及其计算方法，可参考原始论文[48]。

表3. 特性　雪崩数值　硬件测试结果（Kintex UltraScale+）
轮数　Dav　w―av　Hav　LUT　BRAM　延迟（纳秒）　fmax
384位Xoodoo-NC　4　384　19　1.8338　3.9915　360　2.86　349兆赫兹
96位Xoodoo-NC　3　964　7.31　195.87　3840　1.96　510兆赫兹

4.2 评估环境
评估在两种FPGA平台上进行：Kintex Ultrascale+（xcku5p-ffvb676-2-e）和Virtex Ultrascale+（xcvu9p-flga2104-2L-e）。由于Kintex芯片的片上内存容量有限，对于规模较大的表格数据，我们使用Virtex Ultrascale+ FPGA进行测试。所有硬件测试结果均使用Xilinx Vivado 2022.2工具生成。评估准确率时使用了两个数据集：合成数据集和真实世界数据集。合成数据集包含唯一的键值对，其中键值是通过截取SHA-256的256位输出[32]或SHA-384的384位输出（将其从256位或512位的随机输入中截取为24位或96位十六进制字符）而生成的96位或384位加密值。对应的值则是按顺序排列的32位整数，之后会经过随机打乱以消除排序偏差。这类数据集模拟了现实世界中具有均匀分布键值且值不连续的内存访问模式，能够形成高熵值的键值关联。而真实世界数据集则选用了RouteViews的前缀到AS映射数据集pfx2as[7]，该数据集根据从全球各地的RouteViews收集器获得的BGP路由数据，将IPv4/IPv6地址前缀与其对应的自治系统编号联系起来。这一映射有助于确定负责处理特定IP范围流量的网络或自治系统。需要注意的是，自治系统编号并非唯一对应某个地址前缀，一个前缀可能关联多个自治系统，因此该数据集特别适合用于评估在复杂多类现实场景下的系统性能。这类数据集反映了IP路由、流量监控以及ACL查询等数据包处理应用中的常见工作负载，这类应用中以精确匹配的关联查询为主。

4.3 测试结果
4.3.1 准确率分析
由于仅存在匹配键并不足以保证结果的正确性，因为可能存在指纹冲突，因此我们采用P-CAM的键值存储架构来衡量准确率。在这种架构中，需要取出存储的值并与预期值进行比较，以此判断正确性。我们会根据不同的负载因子α和指纹大小来评估准确率。负载因子表示内存的占用程度，其值为存储元素数量与总内存容量之比。图6展示了使用合成数据集时，不同负载因子下准确率与指纹大小之间的关系。如图6所示，随着负载因子的增加，图表趋于饱和，从而导致更多的哈希冲突，准确率下降。当负载因子低于0.5且指纹大小为8位时，只要d大于2，准确率就能保持在100%左右。但在更高的负载因子下，较低的d值会导致准确率出现更明显的下降，这是因为FAC中的冲突增加了。即便如此，当负载因子为1.0时，d=2时的准确率仍能保持在95%以上。此外，无论负载因子如何，d=4时都能保持100%的准确率，而d=3在负载因子为1.0时也能达到99.6%的准确率。
图6. P-CAM的准确率与指纹大小的关系。(a) 使用合成数据集，在负载因子α=0.5和α=1.0时，d分别为2、3、4时的准确率。(b) 对比合成数据集与pfx2as数据集在d=2、3、4时的准确率差异。(c) 比较96位和384位输入尺寸下，d=2、3、4时的准确率差异。
虽然在负载因子为0.5时，6位指纹就已足以达到最高准确率，但当负载因子提升到1.0时，则需要8位指纹。在较低的负载因子下，为了节省内存，可以适当减小指纹大小而不影响准确率。图6(a)显示，与d=3和d=4相比，d=2的准确率最低。不过，无论负载因子如何，只要指纹大小为8位或更大，d=4的准确率就能接近100%。同样地，当指纹大小为8位或更大时，d=3在负载因子为0.5时也能达到近100%的准确率。
由于合成数据集仅包含唯一的键值对，其准确率略高于真实的pfx2as数据集，如图6(b)所示。出现这种差异的原因是，pfx2as中的自治系统编号并非唯一对应某个地址前缀，这意味着一个键可能对应多个值，反之亦然。因此，P-CAM会根据数据到达的顺序，将某个键的现有值更新为最新的值。尽管如此，使用pfx2as数据集得到的准确率依然接近使用合成数据集时的最高值。我们还测试了384位输入版本的准确率，结果显示其与96位版本相当，见图6(c)。

准确率与资源消耗的平衡。在P-CAM中，准确率取决于参数d、α和f，而硬件逻辑资源的消耗则与α无关。在典型配置下（例如d≥4且f≥8），准确率在各种负载因子下都能保持稳定，数值在99.9%以上，如图6(a)所示。而进一步增加f值虽然能提升准确率，但会带来更多内存消耗，如图7所示。因此，将系统配置为d=4且f=8，可以在准确率和资源消耗之间实现近乎最优的平衡。虽然较小的d和f值在负载增加时会导致准确率略有下降，但降低负载因子就能恢复较高的准确率。例如，当d=3且f=4时，即使在负载因子为0.25的情况下，P-CAM仍能保持超过99.9%的准确率。与确定性CAM不同，后者虽然能保证完美准确率，但随着输入规模的增大，会带来显著的内存和逻辑开销（参见4.3.3节），而P-CAM则具备可调节的准确率，同时还能实现可调控的内存使用量以及与输入规模无关的存储方式。这种可调性使得它在高吞吐量或资源受限的环境中也能高效运行，无需面对严格的准确率与资源之间的权衡。
图7. 在负载因子恒定为0.5的情况下，P-CAM的准确率与内存使用量随指纹大小变化的关系。

4.3.2 资源利用率与延迟分析
图8、9和10展示了随着内存阵列大小m的增加，FPGA上的延迟和资源使用情况，这里的m也代表着条目数n或表格大小。该架构的总延迟为三个时钟周期，对应其三个流水线阶段。随着表格大小的增加，关键路径的延迟也会逐渐上升。如图8所示，这种延迟增加主要源于路由延迟。值得注意的是，无论表格大小如何，关键路径中的逻辑延迟部分几乎保持不变。因此，关键路径延迟的增加与路由延迟的增加成正比。由于关键路径延迟决定了系统的最高工作频率和吞吐量，保持逻辑延迟不变就能让P-CAM在面对更大规模的输入和表格时仍能维持高吞吐量。这里的时序分析基于自动布局布线技术，该技术已能考虑逻辑延迟的细微差异，通过手动布局布线还可以进一步优化性能。
图8. 随着表格大小增加，FPGA实现的临界路径延迟变化情况。
图9. 96位和384位输入时，P-CAM的硬件资源使用情况与临界路径延迟关系。
图10. 随着表格大小增加，LUT和BRAM的使用情况变化。
对于P-CAM而言，随着表格大小的增加，LUT的使用量增长幅度很小，因为其计算开销主要局限于哈希计算。不过，当表格大小变得非常大时（比如从2¹⁵增加到2¹⁷），LUT的使用量会出现明显上升，如图9和图10所示。这主要是因为表格的地址宽度（log₂m）增加了，这就需要更多的多路复用器、用于数据访问的解码/控制逻辑，以及为满足更高内存需求而进行的BRAM复制或级联操作，同时还存在并行处理或流水线带来的额外开销。不过，这类开销在其他内存架构中也普遍存在。
BRAM的用量（36千字节）也会随着表格大小的增加而逐渐上升，因为它既要存储指纹信息，也要存储地址信息。不过，与传统CAM相比，它的内存需求要低得多，尤其是在处理较大键值时，因为传统CAM必须存储完整的键值，而非压缩后的指纹。关于输入规模和内存需求影响的更详细分析将在后续章节中介绍。

4.3.3 可扩展性与内存效率
无论输入条目的规模如何，P-CAM的内存需求都是固定的。图11展示了当指纹大小固定为8位时，P-CAM与传统BCAM在不同输入规模下的内存占用情况。可以看出，输入规模越大，P-CAM的内存效率就越高，这一优势明显优于传统CAM。相反，当输入规模较小时，每个FAC每条目所需的内存比特数相对输入规模来说会很高，尤其是对于大型表格而言。例如，当输入规模为24位，表格大小为65,536时，每个FAC就需要24位内存，这一数值与输入规模相同。随着d值的增加，整体内存需求也会随之上升。
图11. 对比二元CAM和P-CAM在不同输入规模下的内存需求情况，可见P-CAM的内存需求与输入规模无关，而二元CAM的内存需求则会随输入规模增加而上升。
关于BCAM和P-CAM的内存需求与输入规模的关系：对于P-CAM而言，输入规模没有限制，其内存需求也与输入规模无关。图11中的红点标出了当输入规模为96位、指纹大小为8位时，P-CAM的最大表格大小。该红点代表了CAM和P-CAM内存需求之间的交点。超过这个点后，P-CAM的内存需求就会超过传统CAM。这个交点mmax表示P-CAM比传统CAM更具内存效率时的最大表格大小，其计算公式为：mmax=2(bd−k)，其中b代表输入比特宽度，d代表内存阵列的数量，k代表指纹大小。
不过，通过缩小指纹大小或限制表格大小，还是可以降低P-CAM的内存使用量。重要的是，即便在mmax之后P-CAM的内存使用量略高于传统CAM，其计算复杂度依然保持不变，延迟也不会受到影响，这一点与传统CAM有很大不同，因为传统CAM在面对更大规模的输入或表格时，延迟和复杂度都会上升。随着输入规模和表格大小的不断增加，传统CAM由于需要存储完整的输入键值，会变得越来越不可用。而P-CAM则能保持固定的内存需求，不受输入规模影响。这一固定内存需求对于将其移植到其他硬件平台来说极具优势。只要选择一种能够处理最大预期输入规模的哈希函数，并明确所需的表格大小，P-CAM的架构就不会发生变化，因此它可以轻松移植到各种平台，尤其是ASIC芯片上。在网络应用领域，这种优势尤为突出，因为可编程交换机中广泛使用了CAM技术。

4.3.4 查询置信度评估
如3.4节所述，d位置信度向量用于表示查询操作的置信程度，其中置1的位数就代表了匹配的FAC数量。置信度值c=d对应最高的置信水平，而c=1则表示最低的置信度。P-CAM查询的置信度是在负载因子α=0.5和1.0、指纹长度从3到10比特以及内存阵列数量d=4的条件下进行评估的。所得到的置信度百分比如图12所示。图12展示了不同负载因子下P-CAM查询的置信度水平与精确度随指纹长度的变化情况，说明了随着指纹长度的增加，置信度分布和精确度会有所提升。对于d=4的情况，在负载因子α=0.5和α=1.0时，分别展示了P-CAM查询的置信度水平及整体精确度与指纹长度的关系。设conf(c)表示恰好有c个FAC匹配的查询的置信度百分比。在较低的负载因子（α=0.5）下，由于FAC冲突较少，查询的置信度较高。例如，对于8比特的指纹，conf(4)和conf(3)的合计百分比约为78%，而conf(1)则仅为5.4%左右。当负载因子增加到α=1.0时，FAC冲突变得更加频繁，导致整体查询置信度下降，这从较低的conf(4)和conf(3)数值中可以看出。指纹长度对置信度的影响也很明显。较小的指纹会导致更多的冲突，从而略微降低置信度。不过，随着指纹长度的增加，置信度会趋于稳定。具体而言，当指纹长度达到7比特或更长时，conf(4)和conf(3)的数值会下降并趋于饱和。相反，conf(2)和conf(1)则呈现相反的趋势，即在小尺寸指纹时数值较低，但随着指纹长度的增加而上升并趋于稳定。精确度图表验证了置信度向量的有效性。它表明，在冲突较少的情况下（即α=0.5或使用较大尺寸的指纹时），精确度较高且稳定，这证实了置信度向量是精确度的正确指标。4.3.5 与现有最先进架构的比较。表4展示了P-CAM与现有最先进架构的对比情况。需要明确的是，这种比较有其局限性。目前的P-CAM采用的是概率性精确匹配，而像DSCAM+和Comp-TCAM这样的设计则提供确定性精确匹配以及通配符（三进制）匹配功能。因此，这并非一种逐项对比的架构基准测试。据我们所知，还没有任何基于FPGA的类CAM架构是完全按照P-CAM那种基于概率数据结构的方式构建的，所以无法进行直接的逐项对比。不过，我们之所以要对比这些架构，是因为它们代表了目前基于FPGA实现的、在内存效率、延迟以及关联搜索的可扩展性方面表现最佳的优化型CAM设计，同时它们也与传统的CAM架构有所不同。尽管它们的功能有所差异，但它们仍可作为有意义的基准，用来衡量在那些只需近似精确匹配功能的场景下，比如数据包处理领域，采用像P-CAM这样的概率引擎所带来的显著资源节省和可扩展性优势。正如我们在4.4节中讨论的，未来的一项工作方向是拓展P-CAM以支持三进制运算。表4.架构FPGA表格大小输入LUTs BRAMLUTRAM最大频率延迟每秒查询次数EL EM E总体比特宽度（36Kb）（MHz）（ns）（百万）Xilinx BCAM [1]Virtex-US+10241502.9千120333––52.070.360.46HLSCAM BCAM [1]Virtex-US+102415054.6千00374––2.81–0.01Comp-TCAM [20]Kintex US512362.2千161536585––7.830.030.05SplitBucket [47]Virtex-718,0013622千0018427.136.929.46–0.06Virtex-7524,28736282.3千0010348.520.666.86–0.13DSCAM+ [55]Kintex US+20,0003212.6千0.5029220.548.850.7935.5635.66（BRAM成本=100）Kintex US+524,2873245.5千274023525.539.2368.731.702.44DSCAM+Kintex US+512321.2千106589.1109.913.650.460.48（BRAM成本=20）Kintex US+20,000324.1千43032718.354.6156.100.410.73Kintex US+524,2873239.1千315.5025123.941.8429.081.482.34P-CAM（我们的成果）Kintex US+512960.8千1.503927.6131.661.440.911.03（d=3，α=1.0，Kintex US+20,000961.2千40.503039.9101.01600.001.324.52精确度=99.42）Virtex US+524,287967.0千115201003033.37190.221.2115.59P-CAM（我们的成果）Kintex US+512961.2千203478.6116.240.960.680.77（d=4，α=1.0，Kintex US+20,000961.9千54027011.190.11010.530.993.01精确度=99.85）Virtex US+524,287969.8千1536010129.633.85135.870.9111.18P-CAM（我们的成果）Kintex US+5123842.9千203149.5105.367.802.732.87（d=4，α=1.0，Kintex US+20,0003843.8千54025611.785.52021.053.957.99精确度=99.83）Virtex US+524,28738411.6千1536010029.933.417355.713.6438.35P-CAM与现有最先进的基于FPGA的CAM架构的比较最大频率，即所合成硬件的最高工作频率，该频率被用于计算延迟和吞吐量数值。像Comp-TCAM [20]、SplitBucket [47]以及DSCAM+ [55]这类设计的主要目标都是减少芯片上的内存使用量。这些设计采用LUTs或LUTRAMs作为存储元素，以此降低对FPGA中BRAM的依赖。例如，SplitBucket完全依靠LUTs来运行，从而避免了使用BRAM；而DSCAM+则采用了一种混合策略，通过一个名为BRAM成本的参数来平衡LUTs和BRAM的使用比例。虽然这些方法减少了BRAM的使用，但却导致了计算复杂度的显著上升。另外，值得注意的是，SplitBucket和DSCAM+支持的输入宽度相对较小，分别为36比特和32比特。若要将这些架构扩展到更大的输入宽度，内存和逻辑复杂度将会呈指数级增长，这使得它们不适用于高容量应用。DSCAM+是为前缀匹配应用而设计的，但在处理通用CAM应用时，Bitmap（BM）结构会成为一个重大瓶颈，因为其内存需求会随着子词BM大小的增加而呈指数级增长（2的s次方）。如果输入大小从32比特增加到96比特，且s也按比例增加，那么BM的内存需求可能会超出硬件实现的承受能力。另一种做法是减小s的值，但这又可能导致后续阶段需要更大的子词尺寸，进而增加LUT的使用量以及MUX阶段的复杂性，最终由于关键路径变长而导致更高的延迟和更低的时钟频率。从表4中我们可以看出，对于更大的表格规模，P-CAM所需的BRAM数量会比DSCAM+更多。出现这一结果主要有两个原因。首先，DSCAM+支持32比特的条目，而P-CAM则支持96比特或更高。其次，对于96比特的输入规模，即便在表格大小达到65,536的情况下，P-CAM的内存占用仍低于BCAM（详见4.3.3节）。值得注意的是，P-CAM在面对更大输入规模时依然具有很好的扩展性；例如，在384比特的输入情况下，只有当表格大小超过288时，P-CAM的内存需求才会超过BCAM，这充分体现了它的出色扩展性。硬件效率指标。为了定量比较P-CAM与现有最先进架构的性能，我们采用了反映架构效率而非绝对数值的标准化资源使用指标。具体来说，我们定义了两个指标：内存效率（EM）和逻辑效率（EL），它们通过将总信息容量（表格大小×键宽）与所消耗的FPGA资源进行对比来体现效率，其中表格大小指的是内存阵列的规模m。对于这两个指标而言，数值越高意味着硬件的使用效率越高。这些指标还能帮助我们了解设计的可扩展性。那些具有较高EM和EL值的架构，能够在资源增长较少的情况下处理更大的表格或更宽的键。此外，这些效率指标所反映出的较低逻辑和内存占用通常意味着更短的处理管线和更快的时钟速度，从而在实际应用中降低访问延迟。这种标准化处理使得我们能够公平地比较那些具有不同表格大小和比特宽度的设计，因为它将性能简化为每个LUT或BRAM所存储比特数的基本单位。虽然这种比较并非逐项对比，因为P-CAM为了实现更高的密度而放弃了三进制功能，但这种标准化处理能够凸显出架构开销，并量化确定性带来的硬件成本。它们揭示了传统架构为支持严格的精确匹配或三进制匹配而付出的资源代价，相比之下，P-CAM的概率化设计则更为紧凑。内存效率。内存效率用于衡量实际BRAM使用情况与给定表格大小T和比特宽度b所需的理想存储容量之间的契合程度：EM=b×TUBRAM×SBRAM，（6）其中UBRAM是指实际使用的BRAM块数量，SBRAM则是一个BRAM块的存储容量（以比特为单位）。逻辑效率。逻辑资源效率用于以每个LUT对应的比特数为单位来量化逻辑开销：EL=b×TULUT+w×ULUTRAM，（7）其中ULUT是指使用的LUT数量，ULUTRAM是指使用的LUTRAM单元数量，w（0将这类性能与传统分类器在准确性、延迟及能效方面进行对比，是另一个具有前景的研究方向。此外，若能扩展P-CAM框架以支持多维和分层数据结构，或许能为实时信号处理、生物信息学以及安全系统等领域开辟新的应用空间，这些领域都非常需要高速且灵活的模式匹配功能。另一个值得探索的方向是研究P-CAM如何加速有限自动机的发展，比如确定性有限自动机或非确定性有限自动机，这类自动机在深度数据包检测和正则表达式匹配中起着关键作用。传统的基于FPGA的确定性有限自动机存在状态爆炸问题，往往需要借助速度较慢的片外DRAM来存储庞大的状态转换表，从而导致延迟瓶颈。而P-CAM凭借其紧凑且并行的关联存储器结构，可作为一种高效的片上状态转换存储器。通过将有限自动机的状态和转换映射到P-CAM基于BRAM的结构上，或许能够构建出专为流式工作负载设计的高吞吐量、低空间开销的自动机处理器。不过，这也带来了概率转换这一新挑战，即错误的查找可能会导致自动机进入错误状态。未来的研究将探讨这类系统的稳定性，并寻找相应的缓解方法，以确保在概率性行为下的正确性。

5 结论
本文介绍了P-CAM这种全新的关联存储器架构，它通过放弃确定性的单周期查找方式，转而采用高度可扩展且能效更高的概率性方法，从而解决了传统CAM存在的可扩展性限制问题。与传统CAM随输入宽度增加而出现的可扩展性瓶颈不同，P-CAM通过基于哈希的指纹技术，将内存需求与密钥大小分离开来。它还支持动态更新、多密钥关联以及并行插入/查询操作，因此非常适合高吞吐量、低延迟的工作负载。我们在Ultrascale+ FPGA上的硬件测试表明，即便面对输入键位较多的大型表格，P-CAM也能保持出色的资源利用效率，并维持较低的稳定延迟。对于384位输入且表格规模为219的情况，与仅支持32位输入的最佳现有确定性设计相比，P-CAM的整体硬件效率提升了15倍，逻辑效率提升了47倍，内存效率则提升了2倍。虽然概率特性会导致一定程度的可控误报率，但我们通过置信向量机制有效降低了这一问题。重要的是，即使在高负载情况下，P-CAM也能保持纳秒级的查找延迟，且不会增加LUT的复杂度。因此，对于高速网络监控和生物信息学等那些传统精确匹配存储器无法应用的场景而言，P-CAM无疑是一种强大且具备可扩展性的替代方案。