突破内容可寻址存储器（CAM）的可扩展性瓶颈：一种用于大键关联搜索的概率方法

《ACM Transactions on Reconfigurable Technology and Systems》：Breaking the Scalability Barrier of Content Addressable Memories: A Probabilistic Alternative for Large-Key Associative Search

　　摘要
要查看此由AI生成的摘要，您必须具有高级访问权限。了解更多信息请登录。

**摘要**
内容可寻址存储器（CAM）提供了高速、确定性的查找功能，但在处理大型输入键（>100位）时面临显著的可扩展性挑战，导致功耗、硅面积和内存成本过高。本文介绍了概率CAM（P-CAM）这一新型架构，它通过牺牲严格的确定性来提高内存效率和可扩展性，从而克服了这些限制。P-CAM使用哈希将高维输入压缩成固定大小的“指纹”，使内存需求与键长度无关。P-CAM保留了CAM的常数时间查找优势，同时支持网络、生物信息学和机器学习等需要处理大型键的应用场景，在这些场景中传统CAM并不实用。在Xilinx UltraScale+设备上的FPGA实现表明，P-CAM在处理384位键时，查询延迟保持不变，并且资源效率提高了15倍，相比为较窄输入设计的最先进确定性CAM而言。尽管P-CAM的概率特性引入了可控制的小错误率，但在特定约束下可以配置为完全确定性的操作。据我们所知，P-CAM是第一个将基于指纹的概率数据结构作为关联查找主要存储机制的CAM架构，这使其区别于仅限于集合成员检查的先前概率方法，为现代数据密集型系统提供了强大且可扩展的替代方案。

**AI生成的摘要（实验性）**
此摘要是使用自动化工具生成的，并非由文章作者编写或审核。它旨在帮助发现、评估相关性，并协助来自相关研究领域的读者理解该工作。它旨在补充作者提供的摘要，后者仍然是论文的权威版本。点击此处了解更多信息。点击此处评论该摘要的准确性、清晰度和实用性。您的反馈将有助于改进和未来版本的生成。要查看此由AI生成的通俗语言摘要，您必须具有高级访问权限。

**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]。

**应用领域和新兴需求**
除了传统的网络角色外，CAM还在新兴领域得到重新考虑。例如，在网络安全中，CAM用于识别大型数据流 [3]、检测入侵模式 [19, 29] 或执行深度数据包检查 [58]。这些应用通常需要在总共104位的5元组字段上进行匹配（对于IPv4）或更大的IPv6字段 [53]。在生物信息学中，大规模序列比对任务经常需要在DNA/RNA序列中搜索基因模式。一个64个碱基的DNA字符串需要2位编码，而一个64个残基的氨基酸序列则需要320位编码 [10]。这些需求远远超出了CAM通常优化的输入大小。更大的模式进一步增加了复杂性，因为它们需要分割和多次CAM操作来匹配完整模式。此外，机器学习硬件、图分析和边缘AI应用越来越多地探索关联存储器原语，用于快速最近邻搜索、输入模式匹配和特征向量比较，扩展了类似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 背景和动机**
由于单周期延迟和固有的硬件兼容性，CAM几十年来一直是优化工作的重点。虽然大多数现有研究集中在晶体管级改进和节能电路设计上，但这些方法忽略了可扩展性和适应新用例等基本挑战 [8, 18, 25, 30, 38, 41, 44]。基于trie的方法和哈希表等软件替代方案为前缀匹配和IP查找等网络任务提供了内存高效的解决方案，但受到顺序内存访问时间的限制，不适合高速应用 [46]。混合方法（如将基于trie的方法与基于哈希的成员查询结合 [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头部、5元组流记录或编码的生物序列等非常大的输入宽度。关于这些架构在资源效率方面的详细讨论见第4.3.5节。

**2.2 概率方法**
概率数据结构，如Bloom过滤器 [5]、Cuckoo过滤器 [15] 和哈希表 [26, 36, 49]，已被探索作为潜在的CAM替代方案，特别是用于处理较大输入。尽管这些结构在输入位宽度和表大小方面提供了可扩展性和内存效率，但它们在准确性和确定性之间做出了权衡。虽然Bloom和Cuckoo过滤器提供了紧凑的存储和快速的成员资格测试，但它们无法检索关联数据或内存地址，限制了它们在键值存储或表查找场景中的实用性。哈希表（包括Cuckoo [36] 和Peacock变体 [26]）作为键值存储，但由于显著的哈希冲突，需要更大的内存占用才能达到可接受的准确性 [49]。此外，它们的非确定性内存访问延迟，特别是在高负载下，使其不适合高速应用 [51]。

虽然概率方法提供了可扩展性的途径，但区分不同的架构目标至关重要。一类是近似关联存储器，专为相似性搜索而设计。例如基于汉明距离的CAM [17] 和使用局部敏感哈希 [33] 的方法旨在识别相似但不一定完全相同的项。通过故意最大化相似输入的哈希冲突，它们在模式识别和近似最近邻任务中表现出色。然而，这种固有的不精确性设计使它们不适合需要精确匹配的临界任务，如IP路由。这些数据结构既不能复制CAM的基本功能，也无法实现高精度-内存权衡。因此，仍然迫切需要创新的CAM架构，以平衡可扩展性、低延迟操作和硬件兼容性，以满足当代应用的需求。

虽然之前有一些关于概率数据结构的工作用于增强CAM，但这些工作主要集中在概率成员资格检查上，而CAM架构仍然保持传统。Ooka等人 [35] 在以内容为中心的路由器中用Bloom过滤器增强了传统的基于CAM的名称查找引擎。然而，概率行为仅限于使用Bloom过滤器的成员资格预检查，而匹配操作仍使用传统的CAM。同样，Pontarelli和Ottavi [39] 将Bloom过滤器与传统的TCAM结合使用，用于错误检测/校正，而TCAM的正常查找仍然保持精确性。pbCAM [52] 使用多个传统的CAM银行和哈希索引以及Bloom过滤器来检测条目的存在。虽然这种基于概率的银行设计能够节省能源，但一旦选择了正确的银行，实际的CAM查找仍然使用精确匹配。Byun等人[6]更进一步，完全用向量Bloom过滤器替换了CAM用于IP查找。但它只执行类似于Bloom过滤器的成员查询，类似于压缩的LUT，并不提供检索与匹配键相关联的地址或值的关联内存功能。基于忆阻器的近似CAM提案[19, 45]侧重于使用模拟近似来实现BCAM或TCAM类似的功能，但其行为本质上是确定性的，任何观察到的不准确性都是由于模拟变异性而不是基于哈希的故意概率设计造成的。

总之，这些工作没有一个在架构上实现了完全概率性的内容可寻址内存或关联内存阵列。它们要么在传统的CAM周围结合概率算法，要么将概率效应视为需要最小化的错误，而不是将其作为一种特性。相比之下，P-CAM独特地提出通过其架构使CAM的匹配操作本身具有概率性，并将这种不确定性作为正常操作的一部分来管理，以提高效率。这意味着P-CAM的行为和贡献与以往的工作有根本的不同，因为它在匹配和存储中包含了故意的概率性，而其他工作要么提供严格的确定性匹配，要么只在支持机制中引入概率性，而不是在核心CAM架构中。

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

鉴于CAM的这些限制，对于可扩展、低功耗和可重构的关联内存架构的需求正在增长。为了克服CAM的可扩展性和效率限制，本研究探索了一种基本的权衡，即牺牲传统CAM的保证确定性，采用概率性方法来实现大规模的可扩展性，同时保持常数时间的查找。我们提出了基于SPArch [50] 架构的P-CAM，它实现了显著的内存效率和可扩展性，使其适用于大规模应用。

与仅支持集合成员检查的先前概率结构不同，P-CAM引入了一种独特的架构方法，使用基于指纹的概率数据结构作为其主要存储和匹配机制进行关联查找。据我们所知，这使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的行为，并具有固有的和可控的错误概率（误报）。P-CAM的错误概率及其对精度关键应用的影响在第3.3节和第3.4节中进行了分析，包括减轻误报和保持正确性的机制。

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

3 P-CAM架构

P-CAM的设计采用了SPArch [50] 的核心草图机制，该架构最初是为网络流量测量设计的。通过战略性地省略SPArch的计数器数组并修改其草图组件，P-CAM被转变为一种新型的轻量级架构，作为通用关联内存，与其概念前身不同。图2显示了P-CAM的架构。草图组件实现为一个维度为m×d的二维内存数组，其中d表示行数，m表示每行的单元格数。给定一个元素x，它使用d个独立的哈希函数hi(x)，对于i=1,…,d，映射到草图中的每一行i的一个单元格。对于每个x∈X，值hi(x)是某个整数j，0≤j≤m?1，其中X是所有元素（或键）的集合。P-CAM的一个核心组件是哈希函数。由于P-CAM的内存需求不随输入条目的大小而变化，因此哈希函数负责处理输入大小的变异性。一个能够容纳最大可能输入宽度的哈希函数就足够了，因为较小的条目可以用零填充以匹配哈希函数的输入块大小。P-CAM中使用的哈希函数在第4.1节中有详细说明。

图2. P-CAM架构的框图，显示了哈希函数、草图数组（指纹-地址单元格）、地址生成器和值存储。

P-CAM的架构由指纹-地址单元格（FACs）、哈希函数、地址生成器和值存储内存组成。草图中的每个单元格称为指纹-地址单元格（FAC），存储一个元组（f,A），包括元素的指纹（f）和相应的地址（A）。在我们的设计中，草图指的是共同实现P-CAM的概率匹配和压缩存储逻辑的FACs数组。指纹是使用指纹函数f(x)计算的，该函数使用哈希函数将键映射到一个短的固定长度的二进制表示。地址是使用简单的计数器模块AdGen生成的，每次新插入时递增，计算公式为Axnew=Axprev+1，其中Axprev是最后一个分配的地址。由于地址仅在新插入时递增，它作为一个逻辑时间戳，用于跟踪每个条目的相对年龄。为了提供键值存储的功能，分配了一个专用内存块V来存储值。内存块的深度是在P-CAM中要存储的元素数量n，这也是AdGen的最大值。一旦达到最大值，就会设置一个内存满标志，拒绝进一步的插入。由于计数器不会回绕，因此避免了由于地址重用而将最近条目错误分类为旧条目的风险。值使用与FACs中元素对应的地址映射到内存：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?N） |
|--------|-----------|------------------|------------------|------------------|----------------------|
| |-------------|------------------|------------------|------------------|----------------------|

P-CAM的架构采用了SPArch [50] 的核心草图机制，该架构最初是为网络流量测量设计的。通过战略性地省略SPArch的计数器数组并修改其草图组件，P-CAM被转变为一种新型的轻量级架构，作为通用关联内存，与其概念前身不同。图2显示了P-CAM的架构。草图组件实现为一个维度为m×d的二维内存数组，其中d表示行数，m表示每行的单元格数。给定一个元素x，它使用d个独立的哈希函数hi(x)，对于i=1,…,d，映射到草图中的每一行i的一个单元格。对于每个x∈X，值hi(x)是某个整数j，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的概率匹配和压缩存储逻辑的FACs数组。指纹是使用指纹函数f(x)计算的，该函数使用哈希函数将键映射到一个短的固定长度的二进制表示。地址是使用简单的计数器模块AdGen生成的，每次新插入时递增，计算公式为Axnew=Axprev+1，其中Axprev是最后一个分配的地址。由于地址仅在新插入时递增，它作为一个逻辑时间戳，用于跟踪每个条目的相对年龄。为了提供键值存储的功能，分配了一个专用内存块V来存储值。内存块的深度是在P-CAM中要存储的元素数量n，这也是AdGen的最大值。一旦达到最大值，就会设置一个内存满标志，拒绝任何进一步的插入。由于计数器不会回绕，因此避免了由于地址重用而将最近条目错误分类为旧条目的风险。值使用与FACs中元素对应的地址映射到内存：V[Ax]→元素x的值。单个内存数组的总内存需求将是m×(k+a)比特，其中k和a分别是f和A的大小（以比特为单位），a=log2?(n)。表2提供了P-CAM架构中使用的符号约定的完整列表。

P-CAM的操作——更新、查询和删除——在以下部分中描述。P-CAM中的更新、查询和删除操作的伪代码在算法1中提供。

3.1 核心P-CAM操作

更新。要使用新元素x更新P-CAM，我们首先计算其指纹（fx?=?f(x)），并确定一组d个哈希索引的FACs，FAC[i,hi(x)]，对于i=1,…,d。如果一个或多个哈希索引的FACs为空，它们直接用新的指纹和来自AdGen的地址（Ax）更新（算法1，第5-9行）。FAC的内容变为（fx,Ax）。如果没有索引的FACs为空且没有找到匹配的指纹，则考虑两种情况：
(i) 相同的对：如果多个FACs包含相同的指纹-地址对，则随机选择一个或数组中的第一个匹配项，用新的指纹和地址更新（算法1，第11-14行）。
(ii) 不同的对：如果所有指纹-地址对都不同，则用最小地址的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）。如果至少有一个哈希索引的位置（FACs）为空或所有位置都满了但没有匹配的指纹（?(ft,At)∈FAC[i,hi(x)],ft≠fx），则认为该元素不存在（算法1，第24-25行）。

图3. P-CAM查询操作的操作图。从输入数据派生的指纹（FP）与哈希索引的FACs进行比较，并返回与匹配指纹相关联的地址（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行）。这是因为较旧的条目在多个FACs中被复制的概率比最新的条目要高。由于地址同时也充当逻辑时间戳，因此最高的地址对应于最新的条目。要删除一个条目x，首先需要执行查询操作来定位匹配的FACs（如算法1的第35-39行所述），然后清除这些FACs的内容。

3.2 作为键值存储的功能
为了实现键值存储的功能，如图2所示，增加了一个额外的内存块V来存储值。存储在FACs中的地址作为存储内存的索引。在添加新元素时，遵循算法1中的updateCAM过程，并使用生成的地址更新相应的内存位置。如果元素已经存在，则检索匹配的地址并在该地址对应的内存位置更新相关值。在查询过程中，会检索存储在V中的与该元素地址对应的值。图4进一步展示了P-CAM与传统CAM的不同之处。与传统CAM将每个键映射到固定地址位置不同，P-CAM允许灵活的键值关联，使多个不同的键可以映射到同一个地址或类别。这种多键到类别的能力在分类任务中特别有益，因为语义上等价的键可以共享一个共同的输出和内存位置，从而减少存储开销。

3.3 假阳性概率分析
P-CAM的假阳性概率（Pfp）由三个因素决定：哈希碰撞（两个不同的元素必须哈希到同一个位置）、指纹碰撞（两个不同的元素产生相同的指纹）以及FAC中的地址不匹配。当两个或更多不同的元素通过哈希函数映射到同一行的同一个索引时，就会发生哈希碰撞。如果发生指纹碰撞，相关地址也必须匹配才能产生假阳性。地址不匹配仅在更新过程中发生指纹碰撞之后才会出现。如果两个元素具有相同的指纹但地址不同（这种情况发生在元素首次出现时，至少有一个已存在相同指纹的FAC为空，但至少有一个FAC是空的，表明传入的元素是新的），这种差异有助于在更新和查询操作中区分它们。这种区分增加了额外的验证层，显著降低了假阳性的可能性，确保仅凭指纹碰撞不足以导致假阳性。

3.4 管理准确性
通过置信向量
在内存数组中找到的匹配数量可以编码为一个大小为d的位数组，称为置信向量。该向量表示假阳性的可能性：设置的位越多，对查询结果的信心越大。可以对置信向量应用用户定义的阈值来决定是否接受结果。例如，当d=4时，只有当置信向量中至少有两个位被设置时，结果才被接受。在值存储在外部内存的混合系统中，可以通过对外部内存的额外查找来验证低置信度的结果。由于匹配数量是在查询过程中计算的，因此报告置信向量不会产生额外的计算开销。第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个候选位置都被不同的、不匹配的指纹占用时，迫使其中最旧的条目被淘汰。因此，特定条目被淘汰的概率是负载因子、新插入率以及条目相对年龄的函数。重要的是，淘汰并不总是导致假阴性，因为较旧的条目通常由于初始碰撞较少而存储在多个位置。

4 硬件实现和性能评估
我们使用Verilog HDL在FPGA上实现了P-CAM，并从延迟、资源利用和准确性方面评估了其性能。P-CAM的硬件架构框图如图5所示。实现和评估针对两种不同的输入大小进行了测试，分别为96位和384位。输入使用专用大小的96位和384位哈希函数处理。单个哈希函数实例生成所需的哈希位，哈希输出被分割以产生将输入x映射到草图内存的哈希值。地址选择逻辑输出查询输入的存在和地址以及置信向量。使用最大值为n（要存储的元素数量）的上计数器作为地址生成器。

4.1 架构特性
P-CAM的硬件架构支持同时更新和查询操作，提高了其在高吞吐量场景中的适用性，特别是在实时网络流监控等应用中。传统的概率数据结构通常使用单个数据路径进行更新和查询，这限制了并行操作并在流水线过程中引入数据风险。相比之下，P-CAM架构由两个独立的哈希函数模块和两个用于更新和查询的不同数据路径组成，由两个有限状态机控制。这种同时操作通过使用双端口BRAM作为草图内存实现，具有专用的读写端口。与传统的单数据路径架构相比，这种设计通过减少关键数据路径提高了操作频率。

4.2 架构特性
同时更新和查询
P-CAM的硬件架构支持同时更新和查询操作，增强了其在高吞吐量场景中的适用性，特别是在实时网络流监控等应用中。传统的概率数据结构通常使用单个数据路径进行更新和查询，这限制了并行操作并在流水线过程中引入数据风险。相比之下，P-CAM架构由两个独立的哈希函数模块和两个用于更新和查询的不同数据路径组成，由两个有限状态机控制。这种同时操作通过使用双端口BRAM作为草图内存实现，具有专用的读写端口。这种设计还通过减少关键数据路径提高了操作频率。

4.3 管理准确性
在内存数组中找到的匹配数量可以编码为一个大小为d的位数组，称为置信向量。该向量表示假阳性的可能性：设置的位越多，对查询结果的信心越大。可以对置信向量应用用户定义的阈值来决定是否接受结果。例如，当d=4时，只有当置信向量中至少有两个位被设置时，结果才会被接受。在混合系统中，如果值存储在外部内存中，可以通过对外部内存的额外查找来验证低置信度的结果。由于匹配数量是在查询过程中计算的，因此报告置信向量不会产生额外的计算开销。

4.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个候选位置都被不同的、不匹配的指纹占用时，迫使其中最旧的条目被淘汰。因此，特定条目被淘汰的概率是负载因子、新插入率以及条目相对年龄的函数。重要的是，淘汰并不总是导致假阴性，因为较旧的条目通常由于初始碰撞较少而存储在多个位置。

4.5 硬件实现和性能评估
我们使用Verilog HDL在FPGA上实现了P-CAM，并从延迟、资源利用和准确性方面评估了其性能。P-CAM的硬件架构框图如图5所示。实现和评估针对两种不同的输入大小进行了测试，分别为96位和384位。输入使用专用大小的96位和384位哈希函数处理。单个哈希函数实例生成所需的哈希位，哈希输出被分割以产生将输入x映射到草图内存的哈希值。地址选择逻辑输出查询输入的存在和地址以及置信向量。使用最大值为n（要存储的元素数量）的上计数器作为地址生成器。

4.6 架构特性
P-CAM的硬件架构支持同时更新和查询操作，增强了其在高吞吐量场景中的适用性，特别是在实时网络流监控等应用中。传统的概率数据结构通常使用单个数据路径进行更新和查询，这限制了并行操作并在流水线过程中引入数据风险。相比之下，P-CAM架构由两个独立的哈希函数模块和两个用于更新和查询的不同数据路径组成，由两个有限状态机控制。这种同时操作通过使用双端口BRAM作为草图内存实现，具有专用的读写端口。这种设计还通过减少关键数据路径提高了操作频率。

4.7 安全性考虑
依赖哈希引入了潜在的安全问题。具体来说，敌对输入可能被设计为诱导哈希碰撞，增加假阳性率或损坏存储的条目。为了缓解这些风险，P-CAM使用具有强雪崩特性的哈希函数来确保输入的均匀分布。虽然我们假设使用d个独立的哈希函数，但在硬件中实现这一点非常低效。一种常见的优化是使用从两个基础哈希[23]派生的更复杂的哈希方案，但更高效的硬件方法是使用单个宽输出哈希函数，并将其大输出分割为多个几乎独立的哈希。然而，整个方法的有效性取决于所选哈希函数的统计质量。

4.8 性能优化
使用哈希函数将大键压缩为小地址（例如，log2(m)位）是哈希碰撞的根本原因。P-CAM通过使用不压缩输入且具有强雪崩特性的哈希函数来避免这个问题。为此，我们使用Xoodoo-NC [48]作为哈希函数，它是Xoodoo排列[12]的一个轻量级、减少轮次的非加密版本。Xoodoo-NC具有强雪崩特性（熵、权重和依赖性）和输出块大小等于或大于输入块大小，作为抗碰撞的映射，而不是易碰撞的压缩。这种单一哈希函数方法不仅是一种硬件优化，而且是一种更健壮的概率设计，它用高保真度的排列替换了有损压缩步骤。

4.9 硬件实现
我们在[48]中提出了一个96位的Xoodoo-NC版本，仅使用Xoodoo排列状态的一个表来派生。一个Xoodoo轮次仅包含移位、AND和XOR操作，从而具有低逻辑深度和延迟。这些轮次是使用完全展开的架构实现的，完全由组合逻辑构成，允许在整个时钟周期内计算出整个哈希值。通过增加轮次数量（超出满足雪崩特性所需的轮次）并连接结果输出，Xoodoo-NC可以生成任何96位倍数的输出宽度。我们将设计扩展为使用整个384位的Xoodoo排列状态来处理384位输入版本的哈希函数。96位的Xoodoo-NC哈希函数只需要2.5轮排列就能满足雪崩特性，而384位版本则需要4轮。在我们的实现中，我们使用3轮来处理96位的Xoodoo-NC。384位输入宽度的哈希计算延迟仅为2.86纳秒，并且哈希函数可以在每个时钟周期内处理一个输入。由于其逻辑深度低且不使用内存，与常用的非加密哈希函数（如FNV-1a和Murmur哈希[14, 16]）相比，它引入的资源开销和功耗非常小。雪崩特性通过三个指标来表示，即雪崩依赖性（Dav）、雪崩权重（w_av）和雪崩熵（Hav），分别代表相关性、扩散性和随机性。表3显示了在Kintex Ultrascale+ FPGA上的雪崩特性和硬件性能。有关Xoodoo-NC的详细硬件分析、雪崩指标的描述及其计算方法，请参考原始论文[48]。

4.2 评估设置
评估在两个FPGA平台上进行：Kintex Ultrascale+（xcku5p-ffvb676-2-e）和Virtex Ultrascale+（xcvu9p-flga2104-2L-e）。Kintex Ultrascale+ FPGA用于评估较小的P-CAM配置，并允许与之前的工作进行公平比较。对于较大的表大小，由于Kintex设备上的片上内存有限，因此使用Virtex Ultrascale+ FPGA。所有硬件结果都是使用Xilinx Vivado 2022.2获得的。
使用两个数据集来评估准确性：一个合成数据集和一个真实世界数据集。合成数据集包含唯一的键值对，其中键是通过截断SHA-256的256位输出[32]或SHA-384的384位输出（到24或96个十六进制字符）从256位或512位随机输入生成的。相应的值是按顺序排列的32位整数，然后随机打乱以消除排序偏差。这个数据集模拟了具有均匀分布的键和非连续值的真实世界内存访问模式，提供了高熵的键值关联。
使用的真实世界数据集是RouteViews前缀到AS映射（pfx2as）[7]，它根据从全球分布的RouteViews[34]收集器收集的BGP路由数据，将IPv4/IPv6前缀映射到它们的原始自治系统（AS）编号。这种映射有助于识别负责特定IP范围路由流量的网络或AS。值得注意的是，AS编号并不唯一地绑定到单个前缀，一个前缀可能与多个AS相关联，这使得该数据集特别适合在具有挑战性的多类真实世界场景下评估系统性能。

4.3 结果
4.3.1 准确性分析
准确性是使用P-CAM的键值存储架构来测量的，因为仅存在匹配的键并不足以确保正确性，因为可能存在指纹冲突。在这种设置中，存储的值被检索出来并与预期值进行比较以验证正确性。准确性是根据不同的负载因子（α）和指纹大小来评估的。负载因子表示内存的满度，表示为存储的元素数量与总内存大小（nm）的比率。图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) d=2,3,4时，合成数据集和pfx2as数据集之间的准确性比较。(c) d=2,3,4时，96位和384位输入大小之间的准确性比较。
虽然在负载因子为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中的AS编号并不唯一地绑定到单个前缀，这意味着一个键可以映射到多个值，反之亦然。因此，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时，P-CAM在负载因子为0.25时仍能实现>99.9%的准确性。与确定性CAM不同，确定性CAM在输入宽度增加时保证完美准确性，但会带来大量的内存和逻辑开销（参见第4.3.3节），P-CAM提供了可配置的准确性和可调的内存使用以及与宽度无关的存储。这种可调性使得在高吞吐量或资源受限的环境中高效部署成为可能，而无需严格的准确性-资源权衡。
图7. 在恒定负载因子0.5下，P-CAM的准确性与时指纹大小的关系。

4.3.2 资源利用和延迟分析
FPGA的延迟和资源使用情况随着内存数组大小m的增加而变化，m也被视为条目数量n或表大小。该架构的总体延迟为三个时钟周期，对应于其三个流水线阶段。随着表大小的增加，关键路径延迟逐渐增加。这种增加主要归因于路由延迟，如图8所示。值得注意的是，关键路径中的逻辑延迟组件几乎不受表大小的影响。因此，关键路径延迟的增加与路由延迟的增加成正比。由于关键路径延迟决定了最大操作频率和吞吐量，保持恒定的逻辑延迟使P-CAM即使在较大的输入和表大小下也能维持高吞吐量。时序分析基于自动布局和路由，这考虑了逻辑延迟的微小变化。通过手动布局和路由可以实现进一步的优化。
图8. 随着表大小增加的FPGA实现的关键路径延迟。
图9. 96位和384位输入的P-CAM的硬件资源使用和关键路径延迟。
图10. 随着表大小增加的LUT和BRAM使用情况。
对于P-CAM来说，随着表大小的增加，LUT的使用增加很小，因为计算开销主要限于哈希计算。尽管如此，当表大小变得非常大（例如，当表大小从2^15变为2^17）时，LUT的使用会有明显增加，如图9和10所示。这主要是由于表地址宽度（log2m）的增加，需要更多的多路复用器、解码/控制逻辑来进行数据访问、BRAM复制或级联以满足更高的内存需求，以及并行性或流水线开销。尽管如此，这些开销在其他内存架构中也很常见。
随着表大小的增加，BRAM（36 Kb）的使用也会逐渐增加，因为它同时存储指纹和地址。然而，与传统的CAM相比，内存需求显著较低，特别是对于较大的键大小，因为CAM必须存储完整的键而不是压缩的指纹。关于输入大小和内存需求的更详细讨论将在下一节中提出。

4.3.3 可扩展性和内存效率
P-CAM的内存需求不随输入大小的变化而变化。图11绘制了固定指纹大小为8位的P-CAM与传统BCAM在不同输入大小下的内存占用情况。输入大小越大，P-CAM的内存效率越高，与CAM相比有显著差异。相比之下，对于较小的输入大小，每个FAC所需的每条目的位数相对于输入大小来说会很大，特别是对于较大的表。例如，对于24位的输入大小和65,536的表大小，每个FAC需要24位，等于输入大小。随着d值的增加，总体内存需求也会增加。
图11. 比较Binary CAM和P-CAM的内存需求与输入大小的关系，显示P-CAM的内存需求与输入大小无关，而Binary CAM则随输入大小变化。
对于P-CAM，输入大小不受限制，内存需求与输入大小无关。红点表示输入大小为96位和指纹大小为8位时的最大表大小。
对于输入大小为96位和指纹大小为8位的情况，P-CAM的最大表大小为65,536，如图11中的红点所示，该点指出了CAM和P-CAM内存需求的交点。超过这一点，P-CAM的内存需求超过了CAM。交点mmax定义了P-CAM比CAM更节省内存的最大表大小，由以下公式给出：mmax=2^(bd?k)，(5)其中b、d和k分别代表输入位宽度、内存数组数量和指纹大小。
然而，通过减小指纹大小或限制表大小，可以减少P-CAM的内存使用。重要的是，即使P-CAM的内存使用略超过CAM的mmax，其计算复杂性仍然保持不变，且延迟不受影响，这与传统CAM不同，传统CAM在输入或表大小增加时会增加延迟和复杂性。随着输入和表大小的增加，CAM变得不切实际，因为它需要存储完整的输入键。相比之下，P-CAM保持固定的内存需求，不受输入大小的影响。这种固定的内存需求特别有利于移植到其他硬件平台。通过选择能够处理最大预期输入大小的哈希函数，并知道所需的表大小，P-CAM架构可以在各种平台上保持不变，特别是在ASIC中。这种优势在网络等应用中非常相关，因为在这些应用中CAM被广泛用于可编程交换机。

4.3.4 查询置信度评估
如第3.4节所述，d位置信度向量表示查询操作的置信度，其中设置的位数表示匹配的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时进行了绘制。

设conf(c)表示恰好有c个FACs匹配的查询的置信百分比。在较低的负载因子（α=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 与最先进架构的比较。P-CAM与最先进架构的比较在表4中呈现。需要澄清的是，这种比较的范围。P-CAM在其当前形式下执行概率精确匹配，而像DSCAM+和Comp-TCAM这样的设计提供确定性精确匹配和通配符（三态）匹配。因此，这不是一个直接的特性对特性的架构基准测试。据我们所知，没有其他基于FPGA的CAM架构完全像P-CAM那样建立在概率数据结构之上，因此无法进行直接的匹配对比。相反，我们比较这些架构是因为它们代表了在FPGA上实现的最新内存优化CAM设计，解决了相同的问题领域，即内存效率、延迟和关联搜索的可扩展性，同时偏离了传统的CAM架构。尽管它们的功能能力不同，但它们作为有意义的基准，可以量化在使用概率引擎P-CAM的场合中，当近似精确匹配功能足够时，在数据包处理等应用中可以实现的大量资源和可扩展性优势。正如我们在4.4节中讨论的，将P-CAM扩展以支持三态操作是未来工作的一个方向。

表4. 架构 | FPGA | 表大小 | 输入 | LUTs | BRAM | LUTRAM | 最大频率 | 延迟 | 每秒搜索次数 | 总位数（36Kb）（MHz）（ns）（百万） | Xilinx BCAM [1] | Virtex-US+10 | 24150 | 2.9K | 120 | 333 | --- | 52.07 | 0.36 | 0.46 |
| HLSCAM BCAM [1] | Virtex-US+10 | 24150 | 54.6K | 00 | 374 | --- | 2.81 | –0.01 |
| Comp-TCAM [20] | Kintex US | 512 | 362.2K | 1615 | 3658 | --- | 7.83 | 0.03 | 0.05 |
| SplitBucket [47] | Virtex-7 | 18,001 | 3622K | 00 | 184 | 27.13 | 6.92 | –0.06 | Virtex-7 | 524,287 | 3628 | 2.3K | 00 | 103 | 48.52 | 0.66 | 6.86 | –0.13 |
| DSCAM+ [55] | Kintex US+20,000 | 3212.6K | 0.50 | 292 | 20.54 | 8.85 | 0.79 | 35.56 | 35.66 | （BRAM成本=100） |
| Kintex US+524,287 | 3245.5K | 2740 | 235 | 25.53 | 9.23 | 68.73 | 1.70 | 2.44 |
| DSCAM+ | Kintex US+512 | 321.2K | 106 | 589.1 | 109.9 | 13.65 | 0.46 | 0.48 | （BRAM成本=20） |
| Kintex US+20,000 | 324.1K | 430 | 327 | 18.35 | 4.61 | 156.10 | 0.41 | 0.73 | Kintex US+524,287 | 3239.1K | 315.50 | 251 | 23.94 | 1.84 | 29.08 | 1.48 |
| P-CAM（我们的工作） | Kintex US+512 | 960.8K | 1.50 | 392 | 761 | 131.66 | 1.44 | 0.91 | 1.03 | （d=3, α=1.0） |
| Kintex US+20,000 | 961.2K | 40.50 | 303 | 9.91 | 101 | 0.00 | 1.32 | 4.52 | 准确性=99.42 |
| Virtex US+524,287 | 967.0K | 1152 | 100 | 303 | 33.37 | 190.22 | 1.21 | 15.59 | P-CAM（我们的工作） |
| Kintex US+512 | 961.2K | 2034 | 78.61 | 116.24 | 0.96 | 0.68 | 0.77 | （d=4, α=1.0） |
| Kintex US+20,000 | 961.9K | 540 | 270 | 11.19 | 0.11 | 101 | 0.53 | 准确性=99.85 |
| Virtex US+524,287 | 969.8K | 1536 | 101 | 29.93 | 33.85 | 135.87 | 0.91 | 11.18 | P-CAM（我们的工作） |
| Kintex US+512 | 3842.9K | 2031 | 49.51 | 105.36 | 7.80 | 2.73 | 2.87 | （d=4, α=1.0） |
| Kintex US+20,000 | 3843.8K | 540 | 256 | 11.78 | 5.52 | 21.05 | 3.95 | 准确性=99.83 |
| Virtex US+524,287 | 3841 | 11.6K | 1536 | 100 | 29.93 | 33.41 | 735 | 5.71 | 3.64 |

表4中的架构比较了P-CAM与最先进FPGA架构的性能。例如，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大小（s）呈指数级增长。如果输入大小从32位增加到96位，并且s按比例增加，BM的内存需求可能变得不可行。或者，减少s可能需要在后期增加子词大小，从而导致MUX阶段的LUT使用和复杂性增加，最终导致更高的延迟和时钟频率降低。从表4中我们可以观察到，对于较大的表大小，P-CAM所需的BRAM比DSCAM+更多。这是由于两个主要原因：首先，DSCAM+支持32位条目，而P-CAM支持96位或更多；其次，对于96位的输入大小，P-CAM在表大小达到65,536之前保持比BCAM更低的内存占用（见4.3.3节）。值得注意的是，P-CAM能够很好地扩展到更大的输入大小；例如，在384位输入时，只有当表大小超过288时，P-CAM的内存需求才会超过BCAM，这展示了其出色的可扩展性。

为了定量比较P-CAM与最先进架构，我们关注反映架构效率的标准化资源使用指标，而不是绝对数字。具体来说，我们定义了两个指标：内存效率（EM）和逻辑效率（EL），它们将总信息容量（表大小×键宽度）与消耗的FPGA资源进行标准化。对于这两个指标，更高的值表示更高效的使用硬件。这些指标还提供了关于可扩展性的见解。具有更高（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
总体硬件效率。为了提供一个用于比较不同设计的单一优点指标，我们定义了一个综合硬件效率指标，该指标结合了逻辑效率和质量效率。这个指标反映了fpga性能取决于可用逻辑资源（luts和lutrams）和片上内存（brams）之间的平衡。一种直接的方法是计算加权总和：eoverall=wl×el+em，（8）其中wl是一个权重因子，反映了目标设备上逻辑资源与bram的相对重要性或稀缺性。一个6输入的lut可以配置为64位ram [2]，这意味着大约需要600-700个lut，包括解码逻辑，来复制一个bram的存储容量。然而，bram是粗粒度的，即如果它们没有得到充分利用，就会浪费一些容量。相比之下，lut是细粒度的，非常适合实现小缓冲区。在cam、缓存和其他内存密集型设计中，将大存储块映射到bram以最大化面积效率是更优的选择。考虑到这些因素，我们将lut权重因子wl设置为1500，这是一个保守且合理的估计，同时也考虑了fpga资源的可用性。然而，在lut是关键资源的设计中，大约需要500个lut来复制一个bram的容量，这突显了使用lut进行存储的高成本。因此，在评估资源效率时，lut的使用应该比bram的使用给予更大的权重。使用加权总和提供了更大的可解释性，并允许根据特定的fpga架构或应用需求优先考虑资源。表4中呈现的定量结果展示了p-cam与现有解决方案相比在可扩展性和资源效率方面的优越性。这种优势在处理宽输入时尤为明显，这是先前架构的一个关键限制。例如，对于384位条目，p-cam的总体效率（eoverall）约为38，比其他在最窄输入宽度上运行的最先进架构高出一个数量级。这一显著的优势主要是由于p-cam的卓越逻辑效率（el），超过17,000比特/每个lut等效，突显了其高度优化的架构。相比之下，像comp-tcam和dscam+这样的设计逻辑效率要低得多，反映了它们对逻辑资源的严重依赖和有限的可扩展性。当需要更大的存储容量时，这种情况变得更加问题重重，因为bram提供了更高的效率。类似地，像splitbucket这样的架构完全消除了bram，但代价是逻辑消耗显著增加，导致整体效率降低。总的来说，这些结果表明p-cam对逻辑和内存资源的平衡使用为现代高容量cam应用提供了更实用和可扩展的解决方案。

4.4 未来工作。目前提出的架构支持（概率）精确匹配；然而，许多实际应用，如前缀匹配，需要掩码或三态查找功能。为了满足这些需求，可以集成掩码技术来模拟tcam的功能，实现灵活的前缀和精确模式匹配。支持三态逻辑可能需要修改fac匹配机制，例如引入掩码感知的指纹编码或支持多模式比较。根本挑战在于哈希函数依赖于雪崩效应，改变单个输入位会导致完全不同的哈希结果。为了克服这一点，可以探索两种潜在的方法：—前缀分割p-cam（用于最长前缀匹配）：并行部署多个p-cam实例，每个实例处理固定的前缀长度（例如/16、/24、/32），类似于最长前缀匹配设计中的布隆过滤器链式。—键分解（用于acl中的掩码匹配）：将输入键分成较小的子字段（例如16位块），在每个字段上独立进行精确的概率匹配，并通过逻辑操作聚合结果以解决通配符语义问题。未来的工作应该探索这些掩码方案的高效硬件实现，同时最小化面积和功耗开销。

对于涉及噪声模式匹配或dna序列分析用例，基于汉明距离的近似查找方法提供了有效的解决方案来识别突变。传统的cam和tcam由于其严格的精确或掩码匹配，不适合这种宽容的比较。此外，近似查找也适用于分类任务，特别是当数据集较小且缺乏足够的多样性来有效利用机器学习模型时。在这种情况下，具有基于汉明距离的近似查找能力的p-cam可以复制经典机器学习模型的行为，如k最近邻分类器，提供类似的功能，同时所需的内存显著减少。未来的工作将探索支持可配置距离阈值的高效硬件机制，以实现容错应用的适应性。此外，未来的研究可以探索结合精确、三态和近似匹配模式的混合架构，进一步提高对多样化工作负载的适应性。此外，集成容错编码方案可以进一步增强在噪声环境中的鲁棒性。 fpga中，一个合理的假设是lutram大约是lut的4×到16×高效。因此，一个好的权重因子是w=0.1。这两个指标允许通过标准化到理论上的理想要求，对不同参数配置的实现进行公平比较。 总体硬件效率。为了提供一个用于比较不同设计的单一优点指标，我们定义了一个综合硬件效率指标，该指标结合了逻辑效率和质量效率。这个指标反映了fpga性能取决于可用逻辑资源（luts和lutrams）和片上内存（brams）之间的平衡。一种直接的方法是计算加权总和：eoverall=wL×EL+EM，（8）其中wL是一个权重因子，反映了目标设备上逻辑资源与BRAM的相对重要性或稀缺性。一个6输入的LUT可以配置为64位RAM [2]，这意味着大约需要600-700个lut，包括解码逻辑，来复制一个bram的存储容量。然而，bram是粗粒度的，即如果它们没有得到充分利用，就会浪费一些容量。相比之下，lut是细粒度的，非常适合实现小缓冲区。在cam、缓存和其他内存密集型设计中，将大存储块映射到bram以最大化面积效率是更优的选择。考虑到这些因素，我们将lut权重因子wl设置为1500，这是一个保守且合理的估计，同时也考虑了fpga资源的可用性。然而，在lut是关键资源的设计中，大约需要500个lut来复制一个bram的容量，这突显了使用lut进行存储的高成本。因此，在评估资源效率时，lut的使用应该比bram的使用给予更大的权重。使用加权总和提供了更大的可解释性，并允许根据特定的fpga架构或应用需求优先考虑资源。表4中呈现的定量结果展示了p-cam与现有解决方案相比在可扩展性和资源效率方面的优越性。这种优势在处理宽输入时尤为明显，这是先前架构的一个关键限制。例如，对于384位条目，p-cam的总体效率（eoverall）约为38，比其他在最窄输入宽度上运行的最先进架构高出一个数量级。这一显著的优势主要是由于p-cam的卓越逻辑效率（el），超过17,000比特 每个lut等效，突显了其高度优化的架构。相比之下，像comp-tcam和dscam+这样的设计逻辑效率要低得多，反映了它们对逻辑资源的严重依赖和有限的可扩展性。当需要更大的存储容量时，这种情况变得更加问题重重，因为bram提供了更高的效率。类似地，像splitbucket这样的架构完全消除了bram，但代价是逻辑消耗显著增加，导致整体效率降低。总的来说，这些结果表明p-cam对逻辑和内存资源的平衡使用为现代高容量cam应用提供了更实用和可扩展的解决方案。 4.4 未来工作。目前提出的架构支持（概率）精确匹配；然而，许多实际应用，如前缀匹配，需要掩码或三态查找功能。为了满足这些需求，可以集成掩码技术来模拟tcam的功能，实现灵活的前缀和精确模式匹配。支持三态逻辑可能需要修改fac匹配机制，例如引入掩码感知的指纹编码或支持多模式比较。根本挑战在于哈希函数依赖于雪崩效应，改变单个输入位会导致完全不同的哈希结果。为了克服这一点，可以探索两种潜在的方法：—前缀分割p-cam（用于最长前缀匹配）：并行部署多个p-cam实例，每个实例处理固定的前缀长度（例如 16、 24、 32），类似于最长前缀匹配设计中的布隆过滤器链式。—键分解（用于acl中的掩码匹配）：将输入键分成较小的子字段（例如16位块），在每个字段上独立进行精确的概率匹配，并通过逻辑操作聚合结果以解决通配符语义问题。未来的工作应该探索这些掩码方案的高效硬件实现，同时最小化面积和功耗开销。>
总体硬件效率。为了提供一个用于比较不同设计的单一优点指标，我们定义了一个综合硬件效率指标，该指标结合了逻辑效率和质量效率。这个指标反映了fpga性能取决于可用逻辑资源（luts和lutrams）和片上内存（brams）之间的平衡。一种直接的方法是计算加权总和：eoverall=wl×el+em，（8）其中wl是一个权重因子，反映了目标设备上逻辑资源与bram的相对重要性或稀缺性。一个6输入的lut可以配置为64位ram [2]，这意味着大约需要600-700个lut，包括解码逻辑，来复制一个bram的存储容量。然而，bram是粗粒度的，即如果它们没有得到充分利用，就会浪费一些容量。相比之下，lut是细粒度的，非常适合实现小缓冲区。在cam、缓存和其他内存密集型设计中，将大存储块映射到bram以最大化面积效率是更优的选择。考虑到这些因素，我们将lut权重因子wl设置为1500，这是一个保守且合理的估计，同时也考虑了fpga资源的可用性。然而，在lut是关键资源的设计中，大约需要500个lut来复制一个bram的容量，这突显了使用lut进行存储的高成本。因此，在评估资源效率时，lut的使用应该比bram的使用给予更大的权重。使用加权总和提供了更大的可解释性，并允许根据特定的fpga架构或应用需求优先考虑资源。表4中呈现的定量结果展示了p-cam与现有解决方案相比在可扩展性和资源效率方面的优越性。这种优势在处理宽输入时尤为明显，这是先前架构的一个关键限制。例如，对于384位条目，p-cam的总体效率（eoverall）约为38，比其他在最窄输入宽度上运行的最先进架构高出一个数量级。这一显著的优势主要是由于p-cam的卓越逻辑效率（el），超过17,000比特/每个lut等效，突显了其高度优化的架构。相比之下，像comp-tcam和dscam+这样的设计逻辑效率要低得多，反映了它们对逻辑资源的严重依赖和有限的可扩展性。当需要更大的存储容量时，这种情况变得更加问题重重，因为bram提供了更高的效率。类似地，像splitbucket这样的架构完全消除了bram，但代价是逻辑消耗显著增加，导致整体效率降低。总的来说，这些结果表明p-cam对逻辑和内存资源的平衡使用为现代高容量cam应用提供了更实用和可扩展的解决方案。

4.4 未来工作。目前提出的架构支持（概率）精确匹配；然而，许多实际应用，如前缀匹配，需要掩码或三态查找功能。为了满足这些需求，可以集成掩码技术来模拟tcam的功能，实现灵活的前缀和精确模式匹配。支持三态逻辑可能需要修改fac匹配机制，例如引入掩码感知的指纹编码或支持多模式比较。根本挑战在于哈希函数依赖于雪崩效应，改变单个输入位会导致完全不同的哈希结果。为了克服这一点，可以探索两种潜在的方法：—前缀分割p-cam（用于最长前缀匹配）：并行部署多个p-cam实例，每个实例处理固定的前缀长度（例如/16、/24、/32），类似于最长前缀匹配设计中的布隆过滤器链式。—键分解（用于acl中的掩码匹配）：将输入键分成较小的子字段（例如16位块），在每个字段上独立进行精确的概率匹配，并通过逻辑操作聚合结果以解决通配符语义问题。未来的工作应该探索这些掩码方案的高效硬件实现，同时最小化面积和功耗开销。

对于涉及噪声模式匹配或dna序列分析用例，基于汉明距离的近似查找方法提供了有效的解决方案来识别突变。传统的cam和tcam由于其严格的精确或掩码匹配，不适合这种宽容的比较。此外，近似查找也适用于分类任务，特别是当数据集较小且缺乏足够的多样性来有效利用机器学习模型时。在这种情况下，具有基于汉明距离的近似查找能力的p-cam可以复制经典机器学习模型的行为，如k最近邻分类器，提供类似的功能，同时所需的内存显著减少。未来的工作将探索支持可配置距离阈值的高效硬件机制，以实现容错应用的适应性。此外，未来的研究可以探索结合精确、三态和近似匹配模式的混合架构，进一步提高对多样化工作负载的适应性。此外，集成容错编码方案可以进一步增强在噪声环境中的鲁棒性。>将这些功能与传统的分类器在准确性、延迟和能效方面进行对比，是另一个有前景的研究方向。此外，扩展P-CAM框架以支持多维和分层数据结构可能会开辟新的应用领域，包括实时信号处理、生物信息学和安全系统，在这些领域中，高速和灵活的模式匹配至关重要。另一个令人兴奋的研究方向是探讨P-CAM如何加速有限自动机（如确定性有限自动机DFA或非确定性有限自动机）的运行，这些自动机是深度数据包检测和正则表达式匹配的基础。传统的基于FPGA的DFA存在状态爆炸问题，通常需要慢速的片外DRAM来存储庞大的转换表，这会导致延迟瓶颈。P-CAM凭借其紧凑且并行的关联存储结构，可以作为高效的片上状态转换存储器。通过将FA的状态和转换映射到P-CAM基于BRAM的结构上，有可能构建出适用于流式工作负载的高吞吐量、空间效率高的自动机处理器。然而，这也引入了新的挑战，即概率转换问题——错误的查找可能导致自动机进入错误的状态。未来的工作将研究这类系统的鲁棒性，并探索缓解技术，以确保在概率行为下的正确性。

**5 结论**

本文介绍了P-CAM，这是一种新颖的关联存储架构，它通过有意识地放弃确定性、单周期查找的方式，转而采用高度可扩展、内存效率高的概率方法，从而解决了传统CAM的可扩展性限制。与传统CAM不同，P-CAM通过基于哈希的指纹识别技术将内存需求与键大小解耦。它支持动态更新、多键关联以及并行插入/查询操作，非常适合高吞吐量、低延迟的工作负载。我们在Ultrascale+ FPGA上的硬件评估表明，P-CAM具有出色的资源效率，即使对于具有宽输入键的大型表也能保持低且恒定的延迟。对于384位输入和2^19大小的表，P-CAM的整体硬件效率（Eoverall）比仅支持32位输入的最佳已知确定性设计提高了15倍。它还实现了47倍更高的逻辑效率和2倍更好的内存效率。虽然概率特性引入了可控制的小概率误报率，但我们通过置信向量机制来缓解这一问题。重要的是，P-CAM即使在高负载因素下也能保持纳秒级的查找延迟，而不会增加LUT的复杂性。因此，P-CAM成为数据密集型领域（如高速网络监控和生物信息学）中的一种稳健、可扩展的替代方案，在这些领域中，传统的精确匹配存储器是不可行的。