Integrated Silicon Solution Incorporated

Nelson L Chow

Paul Cheng

Fangli Chien

David L Amey

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.

Search engine for large database search using CAM and hash

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.

Dynamic linking of banks in configurable content addressable memory systems

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&#x2212;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&#x2212;1) of its disable connections programmed as inputs for disable-in signals received from higher-priority CAM devices, and its remaining (M&#x2212;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.

Cascading content addressable memory devices with programmable input/output connections

A search scheme () in which a controller () provides a search key () to a search engine (). In one variation, the search engine () provides a match address () based on prefix matching to an associate content (AC) memory () and the AC memory provides a search result () back to the controller. In an other variation the search engine () effectively may include the AC and itself provide the search result (). Within the search engine () 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) () associatively mapping to the search result, or by directly addressing the search result ().

Prefix match search scheme

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.

Associated content storage system

A search engine () having a controller (), a memory (), and a hash pointer unit (). The memory () includes a database of search data and associate content, and the controller () uses individual search values to access the memory () to obtain individual search results. The controller () includes a hash function () 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 () converts the hash value into a hash address which is communicated to the hash pointer unit (), 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 () is not a function of the degree of multi-way set-associativity used.

Search engine for large database search using hash pointers

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.

Large database search using content addressable memory and hash

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

Fast aging scheme for search engine databases using a linear feedback shift register

A content addressable memory (CAM)( ) and method having a data-in sub-circuit ( ), memory cells ( ), a match-high line ( ), a match-low line ( ), and pre-charge devices ( ). Input lines ( ) from the data-in sub-circuit ( ) are not necessarily discharged to ground in every cycle of a clock signal ( ) used by the memory cells ( ). Further, the pre-charge devices ( ) may be operated at one half of the rate of the clock signal ( ). Yet further, the CAM ( ) may be selectively configured to operate in either binary or ternary mode.

Growing community of inventors

Mountain View, CA, United States of America

Nelson L Chow