US 8,914,574 B2 · Content addressable memory and method of searching data thereof

Abstract

The present invention discloses a content addressable memory and a method of searching data thereof. The method includes generating a hash index data item from a received input data item; searching the cache for presence of a row tag of the RAM data row corresponding to the data item of hash index; in response to presence, searching the RAM for a RAM data item corresponding to the input data item according to the corresponding row tag of the RAM data row; in response to absence, searching the RAM for a RAM data item corresponding to the input data item by using the data item of hash index; and in response to finding a RAM data item corresponding to the input data item in the RAM, outputting data corresponding to the RAM data item. The method can accelerate data search in the CAM.

Claims13

Dependent claims

A method of searching data in a content addressable memory-that includes a cache and a random access memory (RAM) that stores a plurality of RAM data items by using an array of RAM data rows having a row tag, the method comprising:

generating a first data item of hash index from a first input data item;
searching the cache for correspondence between a first row tag of a first RAM data row and the first data item of hash index;
in response to a cache hit for the first data item of hash index, searching the first RAM data row for a first RAM data item corresponding to the first input data item;
generating a second data item of hash index from a second input data item;
searching the cache for correspondence between a second row tag and the second data item of hash index;
in response to a cache miss for the second data item of hash index, searching the RAM for a second RAM data item corresponding to the second input data item by using the second data item of hash index;
and
in response to finding correspondence between the second RAM data item and the second input data item in the RAM, outputting data corresponding to the second RAM data item.

5 more elements

A content addressable memory, comprising:

a random access memory (RAM) configured to store a plurality of RAM data items by using an array of RAM data rows, each RAM data row in the array including a row tag;
a cache configured to store a previously searched correspondence relation between a data item of hash index and a row tag of a corresponding RAM data row;
a hash index generator configured to generate a data item of hash index from a received input data item;
a controller configured to:
control searching of the cache for a correspondence between a row tag and the data item of hash index;
in response to finding the correspondence between a row tag of the RAM data row in the cache and the data item of hash index, search the RAM for a RAM data item corresponding to the received input data item according to the corresponding row tag of the RAM data row;
in response to not finding the correspondence between a row tag and the data item of hash index in the cache, search the RAM for a RAM data item corresponding to the received input data item by using the data item of hash index;
and
in response to finding the RAM data item corresponding to the received input data item in the RAM, output data corresponding to the RAM data item.

6 more elements

Dependencies are inferred from the claim text.

Content addressable memory and method of searching data thereof

Life of this patent

Content addressable memory and method of searching data thereof

Life of this patent

Abstract

Claims13