CN105474181B - 内容可寻址存储器设备 - Google Patents

Abstract

本文描述的技术一般地涉及将数据存储在内容可寻址存储器(CAM)中以及从内容可寻址存储器(CAM)取回数据。可以接收待存储在CAM中的数据值，其中数据值具有两个或更多个比特。CAM可以包括多个存储器集。对应于数据值的索引可以被确定。该索引可以基于数据值的对应于索引比特集的比特子集来确定。CAM的存储器集可以基于所确定的索引来识别，并且数据值可以存储在所识别的存储器集的存储单元中。

Description

内容可寻址存储器设备

背景技术

本申请要求享有2013年8月31日在印度递交的申请No.3910//CHE/2013的优先权。该母申请的全部公开内容因为所有目的通过引用方式合并于此。

除非在此处进行说明，否则此处所描述的方法不是本申请权利要求的现有技术并且不因包含在该部分中而承认是现有技术。

内容可寻址存储器(CAM)有时在处理器中用于对诸如在转换后援缓存(TLB)中的小的数据结构进行存储和访问。CAM还用于其它环境，诸如互联网路由器、加密以及网络入侵检测，以及其它环境。CAM可用于加速执行数据库搜索或检测模式的应用，诸如在数据库系统、计算机与通信网络、以及高速切换系统中。

在操作期间，CAM的存储阵列的所有行都可以被同时查找以定位特定值，因为该值可能驻存在CAM的任意行中。可能需要大量的功率和持续时间来执行该查找。高功耗还会导致发热，发热会限制CAM的存储密度。本公开探索这些问题以及其它问题。

概述

本文描述的技术一般地涉及将数据存储在功能内容可寻址存储器(CAM)中以及从功能内容可寻址存储器(CAM)中取回数据。该功能CAM可经由RAM的使用来仿真。各种所述的技术可以应用于方法、系统、设备或其组合。

根据本公开的一些示例，描述了与在CAM中存储数据有关的各种方法。一些示例的方法可以包括接收待存储在CAM中的数据值。数据值可以包括两个或更多个比特。CAM可以包括多个存储器集。可以确定对应于数据值的索引。索引可以基于数据值的对应于索引比特集的比特子集来确定。CAM的存储器集可以基于所确定的索引来识别，数据值可以存储在所识别的存储器集的存储单元中。

根据本公开的另外的示例，描述了与从CAM中取回数据有关的各种技术。一些示例的方法可以包括：接收对应于要从内容可寻址存储器(CAM)中取回的数据值的搜索关键字。搜索关键字可以包括两个或更多个比特。CAM可以包括多个存储器集。确定对应于搜索关键字的索引。所确定的索引可被评估以识别对应于所确定的索引的存储器集。可以从所识别的存储器集的存储器集的存储单元取回数据值。

根据本公开另外的示例，描述了内容可寻址存储器(CAM)设备。一些描述的CAM设备可以包括被配置为存储多个数据值的多个存储器集。每个存储器集可以包括多个存储单元。CAM设备可以进一步包括索引选择模块和存储器访问模块。该索引选择模块可被配置为确定对应于数据值或搜索关键字的索引以及识别与数据值或搜索关键字的索引相关联的存储器集。存储器访问模块可被配置为从CAM的识别的存储器集中的存储单元读或者向CAM的识别的存储器集中的存储单元写。

前面的概述仅仅是示例性的，而不意在以任何方式进行限制。通过参考附图以及下面的详细说明，除了上文所描述的示例性的方案、实施例和特征之外，另外的方案、实施例和特征将变得清晰可见。

附图说明

在附图中：

图1是将数据存储在内容可寻址存储器(CAM)设备中的示例过程的图示说明；

图2是从内容可寻址存储器设备取回数据的示例过程的图示说明；

图3示出了存储在CAM的多个存储器集中的示例数据值以及数据中每个比特位置处的值的分布表；

图4示出了具有对应数据值的搜索关键字的示例表以及索引和与索引相关联的存储器集的索引表；

图5是示出示例的内容可寻址存储器设备的功能组件的示意图；

图6是示出图5的内容可寻址存储器设备中的数据值的存储的示意图；

图7是示出从图5的内容可寻址存储器设备中取回数据值的示意图；以及

图8是示出被布置成存储数据在内容可寻址存储器设备中以及从内容可寻址存储器设备中取回数据的示例的计算设备的框图。

以上附图全部都根据本公开的至少一些实施例来布置。

具体实施方式

在下面的详细说明中，将参考附图，附图构成了详细说明的一部分。在附图中，除非上下文指出，否则相似的符号通常表示相似的部件。在详细说明、附图和权利要求中所描述的示例性实施例不意在限制。可以使用其它实施例，并且可以做出其它改变，而不偏离本文呈现的主题的精神或范围。将易于理解的是，如本文大致描述且如图中所图示的，本公开的方案能够以各种不同配置来布置、替代、组合、分离和设计，所有这些都在本文中明确地构思出。

本公开的示例性实施例一般涉及用于内容可寻址存储器(CAM)的存储器管理技术。该技术可实现将数据存储在该内容可寻址存储器中以及从该内容可寻址存储器取回数据，与常规CAM相比其具有降低的功耗和提高的操作速度。

在所描述的实施例中，CAM可以利用索引组织到存储器集中。索引可以基于存储在CAM中的数据值。该技术可允许集相关(set-associative)高速缓存作为CAM运行，并且可实现该CAM中的高效过滤和搜索操作。下面所述的索引和搜索技术可用于网络路由器中并且可以实现该CAM在处理器中的使用用于支持诸如加密、安全、存储器访问过滤和芯片上通信量过滤的应用。

图1是将数据存储在CAM设备中的示例的过程100的图示说明。过程100可以包括由框102-108中的一个或多个所示的一个或多个操作、功能或动作。虽然按顺序的次序示出，这些框还可以并行地执行，和/或按照不同于本文所述的次序来执行。而且，各个框可以组合成较少的框，划分成额外的框，补充代表了其它操作、功能或动作的额外框，和/或基于特定实现方式而去除。过程100开始于框102。

在框102中，“接收待存储在CAM中的具有两个或更多个比特的数据值”，可以通过CAM接口来接收待存储在CAM中的具有两个或更多个比特的数据值。在该示例中，CAM可以包括被配置为存储多个数据值的多个存储器集。在一个示例的实施例中，CAM可以是被配置为用作CAM的集相关SRAM。

处理可以从框102继续到框104，“确定对应于数据值的索引”。在框104中，对应于数据值的索引可以由CAM设备的索引选择模块来确定。该索引可以基于数据值的对应于索引比特集的比特子集来确定。在一些示例中，在数据值存储于CAM设备中的同时，索引比特集可以离线确定。在该示例中，索引比特集可通过评估存储在CAM的多个存储器集中的多个数据值来确定，并且该比特集可以从当前呈现的数据值中被选为索引。评估可以包括确定存储在CAM的多个存储器集中的多个数据值中的每个比特位置处的值的分布。在一些示例中，所确定的索引可以由数据值中的对应于索引比特集的比特值子集构成。

在一些实施例中，在数据值存储于CAM的存储器集中时，专用处理器或处理线程/进程可用于评估数据值中每个比特位置处的离线值的分布。处理器可进一步配置为基于该分布来选定索引。该索引可以通过处理器来动态选定并且可用于将未来数据值存储在CAM的多个存储器集中。

在一些示例中，总体计数器可以由索引选择模块利用数据值来维护和更新以确定存储在CAM中的值的分布。数据值的每个比特位置处的值可被评估，并且可以基于评估结果来更新总体计数器。在各个示例中，可以确定数据值的每个比特位置处的值的加权平均，并且可以基于所确定的加权平均来更新总体计数器。该索引可以利用总体计数器来选定，如下文要描述的。

在一些示例中，数据值的比特位置可被跟踪以确定频繁变化的数据的各个比特，从而确定存储在CAM中的值的分布。这些比特可以由索引选择模块动态地选为索引。在一些实施例中，选择可以利用对数据值的移位和掩码操作来实现。例如，如果数据值的比特位置10、11、12和13被确定为索引比特，则在那些比特位置中具有比特值1且在其它比特位置中具有比特值0的第一掩码可以与数据值一起使用来提取索引比特。随后，该结果可向右移位10个位置，使得比特位置0至9下降，并且索引比特是最低有效的4个比特。这4个比特随后可被选为索引比特。在其它示例中，可从索引比特集中识别一组或多组索引比特，并且可以从所识别的索引比特组中选定索引。

在一些实施例中，可以通过索引选择模块来维护表以确定值分布，并且表可被更新以跟踪每个索引比特集中的索引比特的不同值出现的计数。在一个实施例中，出现的计数可以对应于索引比特的值的确切计数。在其它实施例中，可以利用诸如在CPU分支预测器中使用的迟滞计数器。可构想其它各种技术用于选择索引。基于该分布分析，可以动态地选定索引用于将数据值存储在CAM的存储器集中。

处理可以从框104继续到框106，“基于所确定的索引来识别CAM的存储器集”。在框106处，可以通过CAM设备的存储器访问模块，基于所确定的索引来识别CAM的存储器集。存储器访问模块可以利用对于每个数据值确定的索引将数据值存储在多个存储器集中的任意存储器集中。所识别的存储器集对应于可供用于数据值存储的多个存储器集中的一个存储器集。在一些实施例中，CAM的识别的存储器集可配置为基于每个数据值的索引来存储分配给它的多个数据值。在其它实施例中，如果所识别的存储器集不可用于存储分配给该集的所有数据值，则溢出数据值可以被识别，并且识别的溢出数据值可以利用其它索引方案确定的补充索引而存储在CAM的一个或多个可替代存储器集中，其它索引方案诸如在已知的列相联高速缓存中实现的。例如，如果初始索引比特包含比特位置10、11、12和13，则比特位置8、9、12和14可被选定为补充索引比特。

处理可以从框106继续到框108，“将数据值存储在所识别的存储器集的存储单元中”。在框108中，数据值可以存储在CAM的识别的存储器集的存储单元中。所识别的存储器集对应于多个存储器集中的可供用于存储数据值的一个存储器集。可以识别所识别的存储器集中的可供使用的存储器存储单元，并且数据值可以存储在所识别的存储器存储单元中。下面将对该描述的组织CAM的数据值实现CAM中数据值的高效过滤和搜索的技术进行说明。

图2是从CAM设备取回数据的过程200的图示说明。过程200可以包括由框202-208中的一个或多个所示的一个或多个操作、功能或动作。虽然按顺序的次序示出，这些框还可以并行地执行，和/或按照不同于本文所述的次序来执行。而且，各个框可以组合成较少的框，划分成额外的框，补充代表了其它操作、功能或动作的额外框，和/或基于特定实现方式而去除。过程200开始于框202。

在框202中，“接收用于待从CAM取回的数据值的具有两个或更多个比特的搜索关键字”，可以接收用于待从具有多个存储器集的内容可寻址存储器(CAM)取回的数据值的搜索关键字。在一些示例中，可以通过CAM设备的CAM接口来接收搜索关键字。CAM的多个存储器集可被配置为利用如上文参考图1所描述的动态索引来存储数据值。搜索关键字可以包括两个或更多个比特。在一些实施例中，对应于搜索关键字的数据值可对应于在处理核执行一个或多个线程期间所使用的数据。

处理可以从框202继续到框204，“确定对应于搜索关键字的索引”。在框204中，可以通过CAM设备的索引选择模块来确定对应于搜索关键字的索引。在该示例中，从索引选择模块存储的索引比特集中选定索引。如上所述，处理器可以被配置为基于存储在CAM的多个存储器集中的多个数据值中每个比特位置处的值的分布来确定索引，并且该确定的索引可用于将数据值存储在CAM的多个存储器集中。所确定的对应于搜索关键字的索引可用于识别CAM的具有对应于搜索关键字的数据值的存储器集。

处理可以从框204继续到框206，“评估所确定的索引以识别对应于该索引的存储器集”。在框206中，所确定的搜索关键字的索引被评估以识别CAM的对应于所确定的索引的存储器集。可以通过CAM设备的存储器访问模块来识别存储器集。处理可以从框206继续到框208，“从所识别的存储器集的存储单元取回数据值”。在框208中，可以通过存储器访问模块从CAM的识别的存储器集的存储单元中取回对应于搜索关键字的数据值。在该示例中，可以将搜索关键字的标签与存储的数据值进行比较以识别存储器集的存储单元，并且可以从存储器集的识别的存储单元取回数据值。

在一些实施例中，可以采用另外的技术用于从CAM取回数据值。例如，当使用搜索关键字的确定的索引来对CAM进行查找而导致高速缓存丢失时，Bloom过滤器可用于判定对应于搜索关键字的数据值是否存在于CAM中。如果Bloom过滤器仍指示在CAM中存在数据值，则可以在CAM的其它多个存储器集中的每个存储器集中同时查找该数据值以取回该数据值。在另一示例中，当使用搜索关键字的确定的索引对CAM进行查找而导致高速缓存丢失时，用于多个存储器集中的每一个存储器集的Bloom过滤器可用于识别具有数据值的可能的存储器集。Bloom过滤器一般是由搜索关键字索引的数据结构，其可指示数据值是否没有存储于诸如高速缓存或CAM的存储结构中。

图3示出了存储在CAM的多个存储器集中的示例数据值300以及在数据值中的每个比特位置处的值的分布表302。在该示例中，数据值300中的每个都包括八个比特，可以对输入数据值300中的每个比特位置处的值进行评估以生成分布表302。

在该示例中，分布表302可以包括指示在数据值中的每个比特位置处出现比特值1和/或比特值0的数量的百分比。在图3中，数据值的比特位置由附图标记304来表示，每个比特位置处出现比特值1的百分比由附图标记306表示，并且每个比特位置处出现比特值0的百分比可由附图标记308来表示。在该示例中，对于所有的数据值300，在比特位置1、2和3处的值是1。类似地，对于所有的数据值300，在比特位置4、5和6处的值是0。然而，在图示的示例中比特位置7和8处的值在不同的数据值300之间频繁地变化，因此，这些比特位置可选定为索引比特集。随着新的数据值存储在CAM的存储器集中，可以选择这些值的索引。索引可由数据值中的对应于索引比特集的比特值子集构成。

图3中的表310示出了索引与CAM的存储器集之间的映射。表310中的示例索引基于如附图标记312所代表的比特位置7和8处的值，而相关联的存储器集由附图标记314来表示。

在一些示例中，表310中的索引的总数可以少于或等于配置为CAM的集相关高速缓存中的集合总数。由于CAM接收数据值，被确定为匹配索引标准的值可以存储在CAM的关联集合中。例如，具有索引值“00”的数据值可以存储在CAM的存储器集1中，具有索引值“01”的数据值可以存储在CAM的存储器集2中，具有索引值“11”的数据值可以存储在CAM的存储器集3中，具有索引值“10”的数据值可以存储在CAM的存储器集4中。

图4示出了示例表400以及另一表402，示例表400中的搜索关键字406具有对应数据值404，另一表402能够用于识别与索引相关联的存储器集。在该示例中，搜索关键字406的比特位置3和4可用作索引，并且其它比特位置可用于形成搜索关键字的标签。例如，搜索关键字“0001”的索引可选为“01”。例如，可以选择数据值子集，使得搜索关键字可包括索引比特集。可基于使用表402的索引来识别CAM的存储器集。例如，如果索引是“00”，则识别的存储器集可以是CAM的存储器集1。类似地，如果索引是“01”，则识别的存储器集可以是CAM的存储器集2。在该示例中，搜索关键字的标签可以与存储的数据值进行比较，数据值可以从存储器集的识别的存储单元中取回。

在例如在网络路由器应用的一个示例中，搜索关键字可对应于源IP地址(例如，129.25.64.112)(其它搜索关键字可以是129.25.64.110，129.25.64.95，等等)。数据值可以包括搜索关键字，并且另外地包括对应的目的地IP地址(例如，65.25.78.212)。路由器可被配置为对于给定的源IP地址提供目的地IP地址，其中路由器可以存储与CAM相关联的源-目的地对。源IP地址的部分可用于索引。源IP地址可存储在CAM的关联的存储器集中。一旦利用索引识别出CAM集合，整个搜索关键字可由存储器访问模块匹配以识别关联的目的地地址。

将参考图5来描述示例CAM设备的功能组件。

图5是依照本公开的至少一些实施例布置的示例CAM设备500的组件的示意图。CAM设备500可以包括存储部502。在该示例中，CAM设备500可以包括集相关静态随机存取存储器。存储部502可以包括多个存储器集，诸如存储器集1-N，由附图标记504和506来表示。存储部502可以是处理器508能访问的。处理器508可以包括存储器访问模块510和索引选择模块512。在该示例中，索引选择模块512可以包括索引表514。CAM设备500可进一步包括能够用于将CAM设备500与外部设备(未示出)耦合的CAM接口516。

存储部502的存储器集，诸如存储器集504和506可包括一个或多个存储元件518。每个存储元件518可以被配置为存储数据值。存储器访问模块510可被配置对存储部502写或者从存储部502读。存储器访问模块510可被配置为从索引选择模块512接收集合标识符520。存储器访问模块510可被配置为使用集合标识符520来访问存储部502的特定的存储器集(例如，存储器集504)，并且还被配置为取回存储在存储器集504的存储元件518中的一个或多个数据值。

在一些示例中，存储器访问模块510可进一步配置为从索引选择模块512接收标签522。存储器访问模块510可以使用标签522来从存储器集(例如，存储器集504)的多个存储元件518中选定特定的存储元件518。存储器访问模块510可进一步配置为取回存储在选定的存储元件518中的数据值并且经由CAM接口516将其提供作为取回的数据值。

在一些实施例中，索引选择模块512可被配置为选择对应于数据值的索引。该索引可基于数据值的对应于索引比特集的比特子集来确定。在一些示例中，可通过评估存储在CAM的多个存储器集中的多个数据值来确定索引比特集。

索引可由索引选择模块512动态地选择并且可用于将数据值存储在存储部502的多个存储器集(诸如504和506)中。存储器访问模块510可被配置为基于所确定的索引来识别存储部502的如504的存储器集，并且可以利用用于每个数据值的确定的索引使用存储器访问模块510将数据值存储在多个存储器集中的每个存储器集中。

索引选择模块512还可被配置为识别与对应于数据值的搜索关键字相关联的存储器集。索引选择模块512可使用索引表514来确定集合标识符520，并且存储器访问模块510可以使用集合标识符520来访问存储部502的特定存储器集(例如，存储器集504)并且将存储在存储器集504的存储元件518中的一个或多个数据值取回。下面将参考图6和图7来详细描述数据值在CAM设备500中的存储和从CAM设备500的取回。

图6是示出图5的CAM设备500中的数据值的存储的示意图600。如图所示，待存储在CAM设备500中的数据值602可由设备500经由CAM接口516来接收。在该示例中，数据值602可以由索引选择模块512来接收，索引选择模块512可使用接收到的数据值602来确定与数据值602相关联的索引604。由于索引选择模块512接收到诸如值602的数据值，索引选择模块512可以评估存储在多个存储器集如504和506中的多个数据值以基于评估的分布来从索引比特集606中选定索引404。

索引选择模块512可进一步配置为识别CAM设备500的诸如存储器集608的存储器集，其中存储器集608与数据值602的索引604相关联。选定的索引604连同数据值602一起能够由存储器访问模块510使用来将数据值602存储在识别的存储器集608中。

在一些实施例中，索引选择模块512可以包括总体计数器610，其被配置为计算存储在CAM设备500中的多个数据值的索引比特的分布。在一个示例中，可以确定每个数据值的每个比特位置处的值出现的计数，其中出现的计数能够用于更新总体计数器610。例如，可以利用总体计数器410来跟踪具有值为1的数据值的比特位置。在一些示例中，支持逻辑可被配置为对于数据值的每个比特位置都计算出现计数，使得支持逻辑可以识别出在条目上频繁变化的数据值的各个比特。然后，可以将在条目上频繁变化的比特动态地选为确定的索引604，而不是固定的静态比特集。在一些示例中，动态选择可以利用对数据值的移位和掩码操作来完成。如之前所述，这种利用总体计数器进行索引604的选择可在数据值存储在CAM设备500中的同时来离线地执行。

在其它一些示例中，索引选择模块512可被配置为估计在数据值的每个比特位置处的值的出现计数的加权平均，并且还被配置为基于估计的加权平均来更新总体计数器410。索引选择模块512可被配置为评估出现的计数并且基于比较结果来识别索引604。

存储器访问模块510可被配置为利用选定的索引识别相关联的存储器集608。与选定的索引相关联的数据值602可以存储在识别的存储器集608的存储单元606中。在一些实施例中，如果存储器集不能存储所有的数据值，则可以识别溢出数据值，并且可以利用补充索引(未示出)将识别的溢出数据值存储在CAM的一个或多个存储器集中，补充索引可利用诸如已知的列相联高速缓存中实现的其它索引方案来确定。

图7是示出从图5的CAM设备500中取回数据值的示意图700。如图所示，对应于数据值的搜索关键字702可由CAM设备500接收。搜索关键字702包括两个或更多个比特。索引选择模块512可被配置为确定响应于搜索关键字702的索引704。

索引选择模块512可被配置为识别与对应于数据值的搜索关键字702相关联的存储器集。索引选择模块512可使用索引表514来确定集合标识符520。存储器访问模块510可以使用集合标识符520来访问存储部502的特定存储器集(例如，存储器集504)，以及取回存储在存储器集504的存储元件518中的一个或多个数据值。此外，存储器访问模块510可被配置为将搜索关键字702的标签522与存储的数据值进行比较，以识别所识别的存储器集708的存储单元710以及从存储单元710取回数据值712。

在一些实施例中，CAM设备500的一个或多个存储器集不能利用上述索引技术来存储分配给它们的数据值。例如，当识别的存储器集溢出且不能存储数据值时，数据值可以被输入到替代的存储器集中。在各个实施例中，Bloom过滤器714能够用于判定搜索关键字是否存在于CAM设备500中。可以与初始高速缓存查找并行地或者在初始高速缓存丢失搜索关键字702之后，来评估Bloom过滤器714。如果Bloom过滤器714指示可能存在搜索关键字702，则可以在CAM设备500的多个存储器集中查找搜索关键字702。

在一些实施例中，Bloom过滤器可用于CAM设备500的每个存储器集以识别具有搜索关键字502的存储器集。在一些其它实施例中，单个Bloom过滤器可用于CAM设备来判定在主存储器集中初始丢失之后CAM设备是否应当针对搜索值重新探查。在其它一些实施例中，额外的索引方案可用于将溢出值从一个集合输入至其他集合。该索引方案还可用于在初始高速缓存丢失搜索关键字时在CAM设备500的存储器集中探查所需搜索关键字。

示例的计算设备：图8是示出根据本公开的至少一些实施例的示例的计算设备800的框图。在最基本的配置802中，计算设备800典型地包括一个或多个处理器804以及系统存储器806。存储器总线808可以用于处理器804与系统存储器806之间通信。处理器804可包括多核处理器。

取决于所期望的配置，处理器804可以是任意类型，包括但不限于微处理器(μP)、微控制器(μC)、数字信号处理器(DSP)或其任意组合。处理器804可以包括诸如一级高速缓存810和二级高速缓存812的一级或多级高速缓存、两个或更多个的处理器核814和寄存器816。示例的处理器核814可以包括算术逻辑单元(ALU)、浮点单元(FPU)、数字信号处理核(DSP Core)或其任意组合。示例的存储器控制器818还能够与处理器804一起使用，或者在一些实现方式中，存储器控制器818可以是处理器804的内部部件。一个或多个高速缓存可被配置为用作内容可寻址存储器(CAM)。

根据所需的配置，系统存储器806可以是任意类型，包括但不限于易失性存储器(诸如RAM)、非易失性存储器(诸如ROM、闪速存储器等)或其任意组合。系统存储器806可以包括操作系统820、一个或多个应用822以及程序数据824。在一些实施例中，应用822可以被布置成在操作系统820上操作程序数据824。该所描述的基本配置802通过内虚线框内的那些组件图示于图8中。应用822可以包括被布置成根据基于存储在高速缓存中的数据值选定的索引来将数据值存储在一个或多个高速缓存中以及从一个或多个高速缓存中取回数据值的算法。程序数据822可以包括用于存储在高速缓存中的数据值的索引比特集和索引表。

计算设备800可具有附加的特征或功能以及附加的接口以便于基本配置802与任何所需的设备和接口之间的通信。例如，总线/接口控制器830可用于实现基本配置802与一个或多个数据存储设备832之间经由存储接口总线834的通信。数据存储设备832可以是可移除存储设备836、非可移除存储设备838或者其组合。

可移除存储设备和非可移除存储设备的示例包括诸如软盘驱动器和硬盘驱动器(HDD)的磁盘设备、诸如压缩盘(CD)驱动器或数字多功能盘(DVD)驱动器的光盘驱动器、固态驱动器(SSD)和磁带驱动器，仅列举了几个。示例的计算机存储介质可以包括以用于诸如计算机可读指令、数据结构、程序模块或其它数据的信息的存储的任何方法或技术实现的易失性和非易失性的介质以及可移除和非可移除的介质。

系统存储器806、可移除存储设备836和非可移除存储设备838是计算机存储介质的示例。计算机存储介质包括但不限于RAM、ROM、EEPROM、闪速存储器(flash memory)或其它存储器技术、CD-ROM、数字多功能盘(DVD)或其它光学存储设备、磁盒、磁带、磁盘存储设备或其它磁存储设备、或者可用于存储所需信息并且可由计算设备800访问的任何其它介质。任意这样的计算机存储介质可以是计算设备800的部件。

计算设备800还可以包括接口总线840，该接口总线用于实现从各接口设备(例如，输出设备842、外围设备接口844和通信设备846)经由总线/接口控制器830到基本配置802的通信。示例的输出设备842包括图形处理单元848和音频处理单元850，其可配置为经由一个或多个A/V端口852与诸如显示器或扬声器的各外部设备通信。

示例的外围设备接口844包括串行接口控制器854或并行接口控制器856，其可配置为经由一个或多个I/O端口858与诸如输入设备(例如，键盘、鼠标、笔、语音输入设备、触摸输入设备等)或其它外围设备(例如，打印机、扫描仪等)的外部设备通信。示例的通信设备846包括网络控制器860，其可布置成实现经由一个或多个通信端口864通过网络通信链路与一个或多个计算设备862的通信。

网络通信链路可以是通信介质的一个示例。通信介质通常可通过计算机可读指令、数据结构、程序模块或诸如载波或其它传输机制的调制数据信号中的其它数据来具体化，并且可以包括任何信息输送介质。“调制数据信号”可以是使得其特性中的一个或多个以将信号中的信息编码的方式设定或改变的信号。通过举例而不是限制的方式，通信介质可以包括诸如有线网络或直接线连接的有线介质，以及诸如声波、射频(RF)、微波、红外(IR)和其它无线介质的无线介质。如本文所使用的术语计算机可读介质可以包括存储介质和通信介质两者。

计算设备800可实现为诸如蜂窝电话、个人数据助理(PDA)、个人媒体播放器设备、无线网页监视设备(wireless web-watch device)、个人头戴送受话器设备、专用设备或包括上述功能中的任一种的混合设备的小形状因数的便携式(或移动)电子设备的一部分。计算设备800还可实现为包括膝上型计算机和非膝上型计算机配置两者的个人计算机。

上述的示例性实施例提供了用于存储数据到存储器设备中以及从存储器设备取回数据的技术。该技术实现了以与传统的CAM相比降低的功耗在单一条目集合内的数据值的关联搜索，在传统的CAM中是对于数据值搜索所有的条目集合。本技术允许标准的SRAM充当功率特性和性能特性类似于SRAM的CAM。CAM中的搜索线和匹配线的长度和计数可用于确定功耗。由于这些长度和计数与待搜索的条目的数量成比例，所以与用于传统CAM的搜索时间相比，搜索CAM的小的集合需要相对少量的时间。

本公开不限于本文所描述的特定实施例，这些实施例意在各方案的示例。能够在不偏离其精神和范围的情况下做出多种改进和变型，这对于本领域技术人员而言是显而易见的。通过前面的说明，除了本文所列举的那些之外，在本公开的范围内的功能上等同的方法和装置对于本领域技术人员而言将是显而易见的。旨在使这些改进和变型落在所附权利要求书的范围内。

本公开仅受所附权利要求书以及这些权利要是所给予权利的等同方案的整个范围所限制。应当理解的是，本公开不限于特定的方法、试剂、化合物组成或生物系统，当然这些会变化。还应理解的是，本文所使用的术语是仅仅是为了描述特定实施例的目的，而不意在限制。

关于本文中基本上任何复数和/或单数术语的使用，本领域技术人员能够根据上下文和/或应用适当地从复数变换成单数和/或从单数变换成复数。为了清晰的目的，本文中明确地阐明了各单数/复数的置换。

本领域技术人员将理解，一般地，本文所使用的术语，尤其是随附权利要求(例如，随附权利要求的主体)中所使用的术语，通常意在为“开放式”术语(例如，术语“包括”应当解释为“包括但不限于”，术语“具有”应解释为“至少具有”，术语“包括”应解释为“包括但不限于”，等等)。本领域技术人员还理解，如果意图表达引导性权利要求记述项的具体数量，该意图将明确地记述在权利要求中，并且在不存在这种记述的情况下，不存在这样的意图。

例如，为辅助理解，下面的随附权利要求可能包含了引导性短语“至少一个”和“一个或多个”的使用以引导权利要求记述项。然而，这种短语的使用不应解释为暗指不定冠词“一”或“一个”引导权利要求记述项将包含该所引导的权利要求记述项的任何特定权利要求局限于仅包含一个该记述项的实施例，即使当同一权利要求包括了引导性短语“一个或多个”或“至少一个”以及诸如“一”或“一个”的不定冠词(例如，“一”和/或“一个”应当解释为表示“至少一个”或“一个或多个”)；这同样适用于对于用于引导权利要求记述项的定冠词的使用。

另外，即使明确地记述了被引导的权利要求记述项的具体数量，本领域技术人员将理解到这些记述项应当解释为至少表示所记述的数量(例如，没有其它修饰语的裸记述“两个记述项”表示至少两个记述项或两个以上的记述项)。此外，在使用类似于“A、B和C等中的至少一个”的惯用法的那些实例中，通常这样的构造旨在表达本领域技术人员理解该惯用法的含义(例如，“具有A、B和C中的至少一个的系统”将包括但不限于仅具有A、仅具有B、仅具有C、具有A和B、具有A和C、具有B和C、和/或具有A、B和C等等的系统)。在使用类似于“A、B或C等中的至少一个”的惯用法的那些实例中，通常这样的构造旨在表达本领域技术人员理解该惯用法的含义(例如，“具有A、B或C中的至少一个的系统”将包括但不限于仅具有A、仅具有B、仅具有C、具有A和B、具有A和C、具有B和C、和/或具有A、B和C等等的系统)。

本领域技术人员将进一步理解，呈现两个以上可选项的几乎任何分离词和/或短语，无论是在说明书、权利要求或附图中，都应理解为设想包括一项、任一项或两项的可能性。例如，术语“A或B”将理解为包括“A”或“B”或“A和B”的可能性。

本领域技术人员将理解的是，为了任何以及全部的目的，诸如在提供所撰写的说明书方面，本文所公开的全部范围也涵盖了任何和全部的可能的子范围及其子范围的组合。能够容易地认识到任何所列范围都充分地描述了同一范围并且使同一范围分解成至少均等的一半、三分之一、四分之一、五分之一、十分之一等等。作为非限制示例，本文所论述的每个范围能够容易地分解成下三分之一、中三分之一和上三分之一，等等。

本领域技术人员还将理解的是，诸如“多达”、“至少”、“大于”、“小于”等所有的语言包括所记述的数量并且是指如上文所论述的随后能够分解成子范围的范围。最后，本领域技术人员将理解的是，范围包括每个独立的成员。因此，例如，具有1-3个单元的组是指具有1个、2个或3个单元的组。类似地，具有1-5个单元的组是指具有1个、2个、3个、4个、或5个单元的组，等等。

虽然本文公开了各个方案和实施例，但是其它的方案和实施例对于本领域技术人员而言将是显而易见的。因此，本文所公开的各个方案和实施例是为了示例的目的而不意在限制，真正的范围和精神是通过随附的权利要求表示的。

Claims (22)

1.一种将数据存储在具有多个存储器集的内容可寻址存储器中的方法，所述方法包括：

接收待存储在所述内容可寻址存储器中的数据值，其中所述数据值具有两个或更多个比特；

基于所述数据值的对应于索引比特集的比特子集确定所述数据值的索引，其中确定所述索引包括：评估存储在所述内容可寻址存储器的所述多个存储器集中的多个数据值中的每个比特位置处的值的分布，以及基于所评估的分布来从所述索引比特集中选定所述索引；

基于所确定的索引来从所述内容可寻址存储器的所述多个存储器集中识别存储器集；以及

将所述数据值存储在所识别的存储器集的存储单元中。

2.如权利要求1所述的方法，其中存储所述数据值包括识别所识别的存储器集中的可供用于存储所述数据值的存储器存储位置。

3.如权利要求1所述的方法，进一步包括：

利用所述多个数据值来更新总体计数器；以及

存储所述总体计数器。

4.如权利要求3所述的方法，其中更新所述总体计数器包括：评估所述多个数据值中的每个数据值的每个比特位置处的值，以及基于评估结果来更新所述总体计数器。

5.如权利要求3所述的方法，其中更新所述总体计数器包括：确定所述多个数据值中的每个数据值的每个比特位置处的值的加权平均，以及基于所确定的加权平均来更新所述总体计数器。

6.如权利要求3所述的方法，其中评估所述索引比特的分布包括基于所述总体计数器来识别所述索引。

7.如权利要求1所述的方法，其中将所述数据值存储在所识别的存储器集的存储单元中包括将所述数据值存储在集相关静态随机存取存储器(SRAM)的存储器集的存储单元中。

8.如权利要求1所述的方法，进一步包括：

接收待存储在所述内容可寻址存储器中的额外数据值；

识别来自所述内容可寻址存储器的所识别的存储器集的溢出数据值；以及

利用补充索引将所识别的溢出数据值存储在所述内容可寻址存储器的一个或多个存储器集中。

9.一种从包括多个存储器集的内容可寻址存储器取回数据的方法，所述方法包括：

接收对应于待从所述内容可寻址存储器取回的数据值的搜索关键字，其中所述搜索关键字具有两个或更多个比特；

确定对应于所述搜索关键字的索引，其中确定所述索引包括选择所述搜索关键字的对应于索引比特集的比特子集作为所述索引；

评估所确定的索引以识别来自所述内容可寻址存储器的所述多个存储器集中对应于所确定的索引的存储器集；以及

从所识别的存储器集的存储单元中取回所述数据值。

10.如权利要求9所述的方法，其中从所述存储单元取回所述数据值包括：

将所述搜索关键字的标签与所述内容可寻址存储器中存储的数据值进行比较，以识别所述存储器集的存储单元；以及

从所述存储器集的所识别的存储单元中取回所述数据值。

11.如权利要求9所述的方法，进一步包括：

评估Bloom过滤器，以在没有存储器集对应于所确定的索引时判定所述搜索关键字是否存在于所述内容可寻址存储器中；以及

在所述内容可寻址存储器的所述多个存储器集中的每个存储器集中搜索所述搜索关键字。

12.如权利要求9所述的方法，进一步包括：

对于所述内容可寻址存储器的所述多个存储器集中的每个存储器集评估Bloom过滤器，以当没有存储器集对应于所确定的索引时识别具有搜索关键字的另一存储器集；以及

从所识别的另一存储器集的存储单元中取回所述数据值。

13.一种内容可寻址存储器设备，包括：

多个存储器集，其被配置为存储多个数据值，每个存储器集包括多个存储单元；

索引选择模块，其被配置为确定对应于数据值或搜索关键字的索引以及从所述多个存储器集中识别与所述数据值或所述搜索关键字的所述索引相关联的存储器集，其中确定对应于所述数据值的所述索引是基于所述数据值的对应于索引比特集的比特子集，并且包括：评估存储在所述内容可寻址存储器的所述多个存储器集中的所述多个数据值中的每个比特位置处的值的分布，以及基于所评估的分布来从所述索引比特集中选定所述索引；或者其中确定对应于搜索关键字的索引包括选定所述搜索关键字的对应于索引比特集的比特子集作为所述索引；以及

存储器访问模块，其被配置为从所述内容可寻址存储器的所识别的存储器集中的存储单元读或者向所述内容可寻址存储器的所识别的存储器集中的存储单元写。

14.如权利要求13所述的内容可寻址存储器设备，其中所述索引选择模块被进一步配置为存储所述索引比特集。

15.如权利要求13所述的内容可寻址存储器设备，其中所述内容可寻址存储器设备包括集相关静态随机存取存储器(SRAM)。

16.如权利要求13所述的内容可寻址存储器设备，其中所述索引选择模块被配置为基于存储在所述内容可寻址存储器的所述多个存储器集中的多个数据值中的每个比特位置处值的分布来从所述索引比特集中选定所述索引。

17.如权利要求16所述的内容可寻址存储器设备，其中所述索引选择模块被进一步配置为利用所述多个数据值来更新总体计数器。

18.如权利要求17所述的内容可寻址存储器设备，其中所述索引选择模块被配置为基于所述总体计数器来从所述索引比特集中识别一组或多组索引比特以及从所识别的索引比特组中选定所述索引。

19.如权利要求13所述的内容可寻址存储器设备，其中所述存储器访问模块被配置为利用所确定的索引识别相关联的存储器集以及将所述数据值存储在所识别的存储器集的存储单元中。

20.如权利要求13所述的内容可寻址存储器设备，其中所述存储器访问模块被进一步配置为识别对应于所述搜索关键字的索引的关联的存储器集以及从所识别的存储器集的存储单元中读取对应于所述搜索关键字的数据值。

21.如权利要求13所述的内容可寻址存储器设备，其中所述存储器访问模块进一步包括Bloom过滤器，其被配置为判定所述搜索关键字是否存在于所述内容可寻址存储器设备中。

22.如权利要求21所述的内容可寻址存储器设备，其中所述存储器访问模块进一步包括用于所述多个存储器集中的每个存储器集的Bloom过滤器，以识别具有所述搜索关键字的可能的存储器集。