内容可寻址内存

内容可寻址内存(content-addressable memory, CAM) 是一种特殊类型的存储器,用于某些超高速搜索应用程序。它也称为关联内存关联存储,将输入搜索数据与存储数据表进行比较,并返回匹配数据的地址。 [1]

内容可寻址内存

数据字识别单元是由达德利·艾伦·巴克英语Dudley Allen Buck于 1955年提出的[2]

CAM 经常用于网络设备中,它可以加速转发信息库路由表操作。这种关联存储器也用于高速缓存。在相联高速缓存中,地址和内容并排存储。当地址匹配时,从缓存中取出相应的内容。

硬件相联数组

编辑

标准计算机内存随机存取存储器(RAM) 工作方式为用户提供内存地址,RAM 返回存储在该地址的数据字。而CAM与RAM不同。CAM 的设计使得用户提供数据字,而 CAM 搜索其整个内存,查看该数据字是否存在。如果找到数据字,CAM 会返回一个包含一个或多个找到该字的存储地址的列表。因此,CAM 是软件术语中称为关联数组的硬件体现。

标准

编辑

CAM 和其他网络搜索引擎的主要接口定义在网络处理器论坛开发的称为Look-Aside Interface(LA-1 和 LA-1B)的互操作性协议中指定。Integrated Device Technology赛普拉斯半导体IBM博通有限等公司已经生产了许多符合互操作性协议的设备。2007年12月11日,OIF发布了串行后备(SLA)接口协议。

半导体实现

编辑
 
CMOS 二元 CAM 单元由 6T SRAM 单元和 4 个比较晶体管组成。当搜索线 (SL) 上的数据与通过位线 (BL) 存储在单元中的数据不同时,匹配线 (ML) 将被拉低以指示不匹配。如果匹配线上的单元格均未指示位不匹配,则匹配线将在预充电电平上保持高电平以指示字匹配。两条搜索线都可以保持为逻辑“0”,作为don't care的搜索条件。搜索线和位线可以合并为一对数据线。

在数据搜索应用程序中,CAM 比 RAM 快得多。然而,CAM 存在成本劣势。与具有简单存储单元的 RAM芯片不同,完全并行 CAM 中的每个单独的存储都必须有自己的比较电路,以检测存储位和输入位之间的匹配。此外,必须组合数据字中每个单元的匹配输出以产生完整的数据字匹配信号。额外的电路增加了 CAM 芯片的物理尺寸和制造成本。额外的电路还增加了功耗,因为每个比较电路在每个时钟周期都处于活动状态。因此,CAM 仅适合于无法使用成本较低的方法实现搜索速度的专用应用场景。一个成功的早期实施是通用关联处理器IC和系统。[3]

在 2000 年代初期,包括赛普拉斯半导体IDTNetlogic 、Sibercore [4]MOSAID在内的几家半导体公司推出了针对网络应用的CAM产品。这些产品包装为网络搜索引擎(NSE)、网络搜索加速器(NSA)和基于知识处理器 (KBP),但本质上是具有针对网络优化的专用接口和功能的CAM。目前, 博通有限提供多个 KBP 家族。[5]

替代实现

编辑

为了在速度、内存大小和成本之间实现平衡,一些实现通过在硬件中使用标准树搜索或散列设计来模拟 CAM 的功能,使用复制或流水线等硬件技巧来加速有效性能。这些设计通常用于路由器吕勒奥算法是Internet 路由表中所需的最长前缀匹配搜索的有效实现。

三元 CAM

编辑
 
CMOS 三元 CAM 单元由两个 6T SRAM 单元和 4 个比较晶体管组成。 通常情况下,相反的逻辑电平,即 “0” 和 “1” 或 “1” 和 “0” 将存储在两个单元中。 对于无关的逻辑,“0” 将存储在两个单元格中,以便匹配线 ML 不会因搜索线 (SL) 数据的任何组合而被拉低。

二进制 CAM 是最简单的CAM类型,使用完全由1 与 0 组成的搜索词。 三元 CAM (Ternary CAM, TCAM)[6] 允许在存储的字中对一个或多个比特一种使用 X无关三值逻辑 进行搜索, 因此增强了搜索的灵活性。

例如,三元 CAM 中存储的字 “10XX0” 与 “10000”、“10010”、“10100”、“10110” 这四个搜索词均能匹配。 与二进制 CAM 相比,由于搜索灵活性的增加带来了额外的成本,因为内部存储单元现在必须编码 3 种可能的状态,而不是二进制 CAM 的 2 种。 这些附加状态通常通过向每个存储单元添加掩码位(“相关”或“无关”位)来实现。

应用示例

编辑

内容可寻址存储器通常用于计算机网络设备。例如,当网络交换机从其端口之一接收数据帧,它会使用帧的源MAC地址和接收它的端口更新内部表,然后它在表中查找目标 MAC 地址以确定帧需要转发到哪个端口,并在该端口上将其发送出去。MAC地址表通常使用二元 CAM实现,因此可以非常快速地找到目标端口,从而减少交换机的延迟。

三元CAM 通常用于网络路由器,其中每个地址都有两部分:网络前缀(大小取决于子网配置),以及占据其余位的主机地址。每个子网都有一个网络掩码,用于指定地址的哪些位是网络前缀,哪些位是主机地址。路由是通过查询由路由器维护的路由表来完成的,该表包含每个已知的目的地网络前缀、相关的网络掩码以及将数据包路由到该目的地所需的信息。在简单的软件实现中,路由器将要路由的数据包的目标地址与路由表中的每个条目进行比较,对网络掩码执行按位与运算,并将其与网络前缀进行比较。如果相等,则使用相应的路由信息转发数据包。路由表使用三元 CAM 使查找过程非常高效。地址使用不关心地址的主机部分存储,因此在 CAM 中查找目标地址会立即检索正确的路由条目;屏蔽和比较都是由 CAM 硬件完成的。如果(a)条目按网络掩码长度递减的顺序存储,并且(b)硬件仅返回第一个匹配条目,则此方法有效;因此,使用具有最长网络掩码的匹配(最长前缀匹配)。 [7]

CAM的其他应用包括:

参见

编辑

参考资料

编辑
  1. ^ K. Pagiamtzis* and A. Sheikholeslami, Content-addressable memory (CAM) circuits and architectures: A tutorial and survey, IEEE Journal of Solid-State Circuits, pp. 712-727, March 2006. (PDF). [2022-12-23]. (原始内容存档 (PDF)于2007-03-15). 
  2. ^ TRW Computer Division 互联网档案馆存档,存档日期August 5, 2011,., 1963, p. 17.
  3. ^ C. Stormon, N. Troullinos, E. Saleh, A. Chavan, M. Brule and J. Oldfield, "A general-purpose CMOS associative processor IC and system", IEEE Micro, vol. 12, no. 6, pp. 68-78, December 1992.. [2022-12-23]. S2CID 206432751. doi:10.1109/40.180249. (原始内容存档于2022-04-08). 
  4. ^ Sibercore Technologies - Silicon Solutions for Cyberspace. (原始内容存档于2003-04-19). 
  5. ^ 16nm Heterogeneous Knowledge-Based Processors (KBPs). [2022-12-23]. (原始内容存档于2017-05-19). 
  6. ^ Hucaby, David. CCNP BCMSN Exam Certification Guide: CCNP Self-study. 2004. ISBN 9781587200779. 
  7. ^ Varghese, George, Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, Morgan Kaufmann, 2005
  8. ^ Hinton, Geoffrey E. Distributed representations. 1984 [2022-12-23]. (原始内容存档于2016-05-02). 

参考书目

编辑
  • Anargyros Krikelis, Charles C. Weems (editors) (1997). Associative Processing and Processors, IEEE Computer Science Press. ISBN 0-8186-7661-2ISBN 0-8186-7661-2
  • 6823434 
  • Pagiamtis, K.; Sheikholeslami, A. Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey (PDF). IEEE Journal of Solid-State Circuits. 2006, 41 (3): 712–727 [2022-12-23]. Bibcode:2006IJSSC..41..712P. doi:10.1109/JSSC.2005.864128. (原始内容存档 (PDF)于2022-12-23). 
  • Stormon, C.D.; Troullinos, N.B.; Saleh, E.M.; Chavan, A.V.; Brule, M.R.; Oldfield, J.V.; A general-purpose CMOS associative processor IC and system, Coherent Research Inc., East Syracuse, NY, USA, IEEE Micro, Dec. 1992, Volume: 12 Issue:6.
  • TRW Computer Division. (1963). First interim report on optimum utilization of computers and computing techniques in shipboard weapons control systems. (BuWeps-Project RM1004 M88-3U1). Alexandria, Virginia:Defence Documentation Center for Scientific and Technical Information.

外部链接

编辑