公开(公告)号：US06925524B2

公开(公告)日：2005-08-02

申请号：US10249189

申请日：2003-03-20

申请人： Nelson L. Chow ,  David L. Amey ,  Paul Cheng

发明人： Nelson L. Chow ,  David L. Amey ,  Paul Cheng

IPC分类号： G06F12/00 ,  G06F12/08 ,  G06F17/30

CPC分类号： G06F17/30952

摘要： A relocation system to associatively search a database lookup table with a search key to addressably retrieve a corresponding associate content table record as a search result. The relocation system is implemented in search engine devices having associative memory (e.g., CAM) having one or more sections. The search engine devices employ relocation values when calculating addresses, one per section per device, with the relocation values optionally pre-calculated and stored in relocation registers. The search engine devices may be cascaded to construct a larger search engine. The search engine is typically used with a processor and addressable memory (e.g., RAM or ROM). In particular, the relocation system permits multiple databases to be concurrently stored and worked with in the associative and addressable memory.

摘要翻译： 一种重定位系统，用于将搜索关键字搜索数据库查找表以可寻址地检索相应的关联内容表格记录作为搜索结果。 重定位系统在具有具有一个或多个部分的关联存储器（例如，CAM）的搜索引擎设备中实现。 搜索引擎设备在计算地址时使用重定位值，每个设备每个部分一个，重定位值可选地预先计算并存储在重定位寄存器中。 搜索引擎设备可以被级联以构造较大的搜索引擎。 搜索引擎通常与处理器和可寻址存储器（例如，RAM或ROM）一起使用。 特别地，重定位系统允许在关联和可寻址存储器中同时存储和处理多个数据库。

公开(公告)号：US07054995B2

公开(公告)日：2006-05-30

申请号：US10249598

申请日：2003-04-23

申请人： Nelson L. Chow ,  Paul Cheng

发明人： Nelson L. Chow ,  Paul Cheng

IPC分类号： G06F12/00

CPC分类号： G11C15/00

摘要： A content addressable memory (CAM) system includes CAM banks that can be linked together in a series to form a CAM module. Each CAM bank includes a CAM array with rows. In a lookup operation, each row asserts a field-match signal when a field from a key matches the field of a CAM entry held in the row. Each CAM bank receives a link-control signal, each received from the preceding CAM bank match-in signals for the rows, and each generates match-out signals for the rows. Some embodiments dynamically configure the CAM system into one or more independent CAM modules of various widths, according to data held in a configuration register or to the current value of the key or other search information. Some embodiments include multiple priority encoders that can be coupled to the match-out signals of dynamically selected CAM banks, thus advantageously allowing parallel lookup operations in the CAM modules.

摘要翻译： 内容可寻址存储器（CAM）系统包括可以串联连接在一起以形成CAM模块的CAM库。 每个CAM库包括一个带有行的CAM阵列。 在查找操作中，当来自键的字段与保持在该行中的CAM条目的字段匹配时，每行将断言字段匹配信号。 每个CAM存储体接收一个链接控制信号，每个链接控制信号从前一个CAM存储体的行匹配输入信号中接收，并且各自产生行的匹配信号。 一些实施例根据保存在配置寄存器中的数据或密钥或其他搜索信息的当前值，将CAM系统动态地配置成各种宽度的一个或多个独立CAM模块。 一些实施例包括可以耦合到动态选择的CAM组的匹配输出信号的多个优先级编码器，因此有利于允许CAM模块中的并行查找操作。

公开(公告)号：US06928430B1

公开(公告)日：2005-08-09

申请号：US10128844

申请日：2002-04-23

申请人： Fangli Chien ,  Nelson L. Chow ,  Paul Cheng

发明人： Fangli Chien ,  Nelson L. Chow ,  Paul Cheng

IPC分类号： G06F17/30

CPC分类号： G06F17/30985 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99935

摘要： A search scheme (10) in which a controller (14) provides a search key (16) to a search engine (18, 36). In one variation, the search engine (18) provides a match address (20) based on prefix matching to an associate content (AC) memory (22) and the AC memory provides a search result (24) back to the controller. In an other variation the search engine (36) effectively may include the AC and itself provide the search result (24). Within the search engine (18, 36) every possible prefix for possible respective prefix lengths in the search key may be represented, either by a bit which addressable maps to the search result, by content addressable memory (CAM) (32) associatively mapping to the search result, or by directly addressing the search result (24).

摘要翻译： 一种搜索方案（10），其中控制器（14）向搜索引擎（18,36）提供搜索关键字（16）。 在一个变型中，搜索引擎（18）基于与关联内容（AC）存储器（22）的前缀匹配提供匹配地址（20），并且AC存储器将搜索结果（24）提供回控制器。 在另一变型中，搜索引擎（36）有效地可以包括AC，并且本身提供搜索结果（24）。 在搜索引擎（18,36）内，搜索关键字中可能的相应前缀长度的每个可能的前缀可以由内容可寻址存储器（CAM）（32）映射到搜索结果的可寻址映射的位来表示，其相关地映射到 搜索结果，或通过直接寻址搜索结果（24）。

公开(公告)号：US07107258B2

公开(公告)日：2006-09-12

申请号：US10065267

申请日：2002-09-30

申请人： Paul Cheng ,  Nelson L. Chow ,  Fangli Chien

发明人： Paul Cheng ,  Nelson L. Chow ,  Fangli Chien

IPC分类号： G06F17/30

CPC分类号： G06F17/30982 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99935

摘要： A search engine having a controller, a memory, and at least one hash-CAM (H-CAM). The memory includes a database of search values and associate content or just associate content. The controller uses search values to access the memory to obtain the search results. The H-CAM includes at least one set of paired hash units and CAM units and at least one logic unit. The CAM units hold values known to cause hash collisions in the paired hash units, and the logic unit prioritizes the hash and CAM unit outputs to address values usable to access the memory and obtain a search result at the controller that is not the result of a hash collision. The H-CAM may optionally include a search data storage to store the search values, so that they need not be stored in the memory, and a comparator to determine and handle new search data based hash collisions. The H-CAM may optionally also be cascaded.

公开(公告)号：US06917934B2

公开(公告)日：2005-07-12

申请号：US10065261

申请日：2002-09-30

申请人： Paul Cheng ,  Nelson L. Chow ,  Fangli Chien

发明人： Paul Cheng ,  Nelson L. Chow ,  Fangli Chien

IPC分类号： G06F17/30

CPC分类号： G06F17/30982 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99935

摘要： A search engine (100) having a controller (112), a memory (114), and a hash pointer unit (110). The memory (114) includes a database of search data and associate content, and the controller (112) uses individual search values to access the memory (114) to obtain individual search results. The controller (112) includes a hash function (116) that generates a hash value from a, typically large, search value into a, typically smaller, hash value that may be a hash collision. The controller (112) converts the hash value into a hash address which is communicated to the hash pointer unit (110), which receives the hash address and provides a hash pointer that is communicated to and used by the memory to look up respective search results. In this manner hash collisions are avoided and the size of the memory (114) is not a function of the degree of multi-way set-associativity used.

摘要翻译： 具有控制器（112），存储器（114）和散列指针单元（110）的搜索引擎（100）。 存储器（114）包括搜索数据和关联内容的数据库，并且控制器（112）使用各个搜索值访问存储器（114）以获得单独的搜索结果。 控制器（112）包括散列函数（116），该散列函数（116）从通常较大的搜索值生成散列值到通常较小的可能是散列冲突的哈希值。 控制器（112）将哈希值转换成散列地址，该哈希地址被传送到散列指针单元（110），该哈希指令单元接收散列地址并提供传送给存储器并由存储器使用以查找相应搜索结果的散列指针 。 以这种方式避免了哈希冲突，并且存储器（114）的大小不是所使用的多路组合关联度的函数。

公开(公告)号：US06889225B2

公开(公告)日：2005-05-03

申请号：US09927599

申请日：2001-08-09

申请人： Paul Cheng ,  Nelson L. Chow ,  Fangli Chien

发明人： Paul Cheng ,  Nelson L. Chow ,  Fangli Chien

IPC分类号： G06F17/30 ,  G06F7/00

CPC分类号： G06F17/30982 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99935

摘要： A hash-CAM (H-CAM) which may work with a controller and a memory containing a database of either search values and associate content or associate content by itself The H-CAM includes at least one set of paired hash units and CAM units and at least one logic unit. The CAM units hold values known to cause hash collisions in the respectively paired hash units, and the logic unit prioritizes the hash and CAM unit outputs to a single address value usable to access the memory and obtain a search result at the controller that is not the result of a hash collision. The H-CAM may optionally include a search data storage to store the search values, so that they need not be stored in the memory, and a comparator to determine and handle newly determined hash collisions.

摘要翻译： 可以与控制器和包含搜索值和关联内容或关联内容的数据库的存储器一起工作的散列CAM（H-CAM）.H-CAM包括至少一组配对散列单元和CAM单元， 至少一个逻辑单元。 CAM单元保持已知的在分别对应的哈希单元中引起哈希冲突的值，并且逻辑单元将散列和CAM单元输出优先级到可用于访问存储器的单个地址值，并且在控制器处获得不是 哈希冲突的结果。 H-CAM可以可选地包括搜索数据存储以存储搜索值，使得它们不需要存储在存储器中，以及比较器来确定和处理新确定的哈希冲突。

公开(公告)号：US06772301B2

公开(公告)日：2004-08-03

申请号：US10177895

申请日：2002-06-20

申请人： Paul Cheng ,  Nelson L. Chow

发明人： Paul Cheng ,  Nelson L. Chow

IPC分类号： G06F1200

CPC分类号： G06F17/30982

摘要： A fast aging system (10) which may work with a memory (12) in which data words (16) having aging words (18) are stored. An aging address counter (20) selects an aging word (18) for updating based on a state change in a linear feedback shift register (LFSR) (24). Optionally, in the aging word (18) a zero value (52) may represent a permanent data words (16), a predefined non-zero value (56) may represent data words (16) which are available for replacement, and other zero values may represent data words (16) which are in various stages of valid lifetimes and which should not be replaced yet.

摘要翻译： 一种快速老化系统（10），其可以与其中存储有具有老化字（18）的数据字（16）的存储器（12）一起工作。 老化地址计数器（20）基于线性反馈移位寄存器（LFSR）（24）中的状态变化来选择用于更新的老化字（18）。 可选地，在老化字（18）中，零值（52）可以表示永久数据字（16），预定义的非零值（56）可以表示可用于替换的数据字（16），而其他零 值可以表示处于有效寿命的不同阶段并且不应被替换的数据字（16）。

公开(公告)号：US06704216B1

公开(公告)日：2004-03-09

申请号：US10064770

申请日：2002-08-15

申请人： Paul Cheng ,  Nelson L. Chow

发明人： Paul Cheng ,  Nelson L. Chow

IPC分类号： G11C700

CPC分类号： G11C15/04 ,  G11C15/00

摘要： A content addressable memory (CAM)(10, 102) and method having a data-in sub-circuit (44), memory cells (16, 18), a match-high line (36), a match-low line (38), and pre-charge devices (40, 42). Input lines (30, 32, 48, 50) from the data-in sub-circuit (44) are not necessarily discharged to ground in every cycle of a clock signal (62) used by the memory cells (16, 18). Further, the pre-charge devices (40, 42) may be operated at one half of the rate of the clock signal (62). Yet further, the CAM (10, 102) may be selectively configured to operate in either binary or ternary mode.

摘要翻译： 一种内容可寻址存储器（CAM）（10,102）和方法，具有数据输入子电路（44），存储单元（16,18），匹配高线（36），匹配低线（38） ）和预充电装置（40,42）。 来自数据输入子电路（44）的输入线（30,32,48,50）不一定在由存储器单元（16,18）使用的时钟信号（62）的每个周期中释放到地。 此外，预充电设备（40,42）可以以时钟信号（62）的速率的一半操作。 此外，CAM（10,102）可以被选择性地配置为以二进制或三进制模式操作。

公开(公告)号：US07043600B2

公开(公告)日：2006-05-09

申请号：US10249842

申请日：2003-05-12

申请人： Nelson L. Chow ,  Paul C. Cheng

发明人： Nelson L. Chow ,  Paul C. Cheng

IPC分类号： G06F12/00

CPC分类号： G11C15/00

摘要： CAM devices that can be cascaded together to form CAM systems of different sizes are disclosed. The system has one or more clusters of M CAM devices, each device including (M−1) disable connections. Disable signals are used to avoid contention so that one CAM device generates the system output on a shared bus. To reduce pin count, the CAM device of priority N within each cluster has (N−1) of its disable connections programmed as inputs for disable-in signals received from higher-priority CAM devices, and its remaining (M−N) disable connections programmed as outputs for disable-out signals provided to lower-priority CAM devices. Some embodiments include two or more clusters of CAM devices and a controller. In some embodiments, the CAM system works as fast as a single CAM device. Some embodiments impose no architectural limits on the number of CAM devices that can be cascaded together.

摘要翻译： 公开了可以级联在一起以形成不同尺寸的CAM系统的CAM装置。 该系统具有一个或多个M CAM设备群集，每个设备包括（M-1）禁用连接。 禁用信号用于避免竞争，以便一个CAM设备在共享总线上生成系统输出。 为了减少引脚数量，每个簇内优先级为N的CAM器件将其禁用连接的（N-1）编程为从较高优先级CAM器件接收的禁止输入信号的输入，其剩余（MN）禁止连接编程为 输出用于禁止输出信号提供给较低优先级的CAM设备。 一些实施例包括两个或更多个CAM设备群集和控制器。 在一些实施例中，CAM系统与单个CAM设备一样快。 一些实施例对可以级联在一起的CAM设备的数量没有施加架构限制。