Inter-row configurability of content addressable memory

Details Inter-row configurability of content addressable memory Inter-row configurability of content addressable memory

2000-06-14

2003-05-06

Elmore, Reba I. (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S214000, C711S216000, C365S230030

Reexamination Certificate

active

06560670

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to content addressable memories (CAMs), and more particularly to inter-row configurability of a CAM array.
BACKGROUND
A content addressable memory (CAM) system is a storage system that can be instructed to compare a specific pattern of comparand data with data stored in its associative CAM array. The entire CAM array, or segments thereof, is searched in parallel for a match with the comparand data. The CAM device typically includes a priority encoder to translate the highest priority matching location into a match address or CAM index.
The CAM array has rows of CAM cells that each stores a number of bits of a data word. U.S. Pat. No. 5,440,715 describes a technique for expanding the width of the data words beyond that of a single row of CAM cells. Multiple data words can be width expanded together to form a data line. It appears, however, that the CAM system of the '715 patent will not always output the correct match address. For example, assume a first data line of two data words ZY is stored in data words
0
and
1
, respectively, and a second data line of two data words WZ is stored in data words
2
and
3
, respectively. When a comparand data line of WZ is provided for comparison, the first cycle compare with W will indicate a match with data word
2
only. The second cycle compare with Z will indicate a match with data words
0
and
3
and match lines ML
0
and ML
3
will be activated. When the priority encoder is enabled, it will output a match address of 0 instead of 3 since ML
0
is the highest priority match line.
Additionally, it appears that the CAM system of the '715 patent will not always function correctly when each data line has different numbers of data words. For example, assume that a data line of 5 words VWXYZ is loaded into data word locations
0
-
4
, and a data line of 4 words VWXY is loaded into data word locations
5
-
8
. When a comparand data line of VWXY is provided to the CAM array, ML
3
and ML
8
will both be activated and the priority encoder will incorrectly output an address of three that stores the last word of a five word data line and not the last word of a four word entry.
Additionally, it appears that the CAM system of the '715 patent is unable to store data words of a data line in non-consecutive rows and still be able to accurately search for the data line.
It would be desirable to have an improved technique of width expanding data words in a CAM array.
SUMMARY OF THE INVENTION
An inter-row configurable content addressable memory (CAM) system is disclosed. For one embodiment, the CAM system includes an array of CAM cells having a plurality of rows of CAM cells for storing a data word chain, wherein the data word chain comprises a sequence of at least two data words each stored in a different row of CAM cells, and wherein each row of CAM cells includes a first group of CAM cells for storing a pointer and a second group of CAM cells for storing one of the data words. The pointer of the first data word of the data word chain may be a predetermined number greater than the number of rows in the CAM array. The pointers associated with the other data words of the data word chain each store an address of the previous data word in the data word chain. The CAM system further includes a write circuit for writing the data words into the rows of CAM cells, an address decoder coupled to the CAM array, and a priority encoder coupled to the CAM array.
A method of using a CAM array to store and maintain a data word chain spanning more than one row of the CAM array is also disclosed. For one embodiment, the data word chain is written into the CAM array by determining the address of a first row in the CAM array that does not store valid data; writing a first data word of the data word chain to the first row in the CAM array; and writing a second data word of the data word chain and the address of the first row to a second row in the CAM array. The method may further include writing a null pointer with the first data word to indicate to the first row to indicate the first data word in the data word chain. For another embodiment, the data word chain is written into the CAM array by determining that a first data word in the data word chain matches data stored in a first row of the CAM array; determining the address of the first row; appending the address of the first row to a second data word in the data word chain; determining that no row in the CAM array stores data that matches the second data word and the address of the first row; and writing the second data word and the address of the first row to a second row in the CAM array.
A method of searching for a matching data word chain in the CAM array is also disclosed. For one embodiment, the method includes determining the address of a first row in the CAM array that stores data matching a first data word in the data word chain, and determining that a second row in the CAM array stores data that matches a second data word in the data word chain and the address of the first row. The method may further include appending a null pointer to the first data word, and comparing the first data word and the null pointer with the data stored in the CAM array. The method may also include appending the address of the first row to the second data word, and comparing the second data word and the address of the first row with the data stored in the CAM array.
A method of invalidating or deleting one or more data words of a data word chain stored in a content addressable memory (CAM) array is also disclosed. The data word chain comprises a sequence of n data words each stored in a unique row of CAM cells of the CAM array, where n is an integer greater than one, and wherein each data word has an associated pointer stored in the same row as the corresponding data word. For one embodiment, the method includes determining that the CAM array stores the data word chain, and invalidating the nth data word of the data word chain when the address of the row in the CAM array that stores the nth data word does not match any of the pointers of the data words. The method may further include invalidating the rest of the data words in the data word chain.
Another embodiment of invalidating one or more valid data words of a data word chain stored in a content addressable memory (CAM) array is also disclosed. The data word chain comprises a sequence of n data words each stored in a unique row of CAM cells of the CAM array, where n is an integer greater than one, and wherein each data word has an associated pointer stored in the same row as the corresponding data word. The method includes (a) determining that the CAM array stores the data word chain; (b) comparing the address of the row in the CAM array that stores the nth data word with the pointers of each of the data words; (c) setting x equal to the pointer of the nth data word; (d) setting y equal to the address of the row in the CAM array that stores the nth data word; (e) invalidating the data word at address y; (f) comparing x with the pointers of the remaining valid data words; (g) setting y equal to x; (h) setting x equal to the pointer at the address of x in the CAM array; and (i) repeating (e)-(h), inclusive, until x is equal to a null pointer associated with the first data word of the data word chain. The method may further include invalidating the first data word of the data word chain.
Other objects, features, and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.


REFERENCES:
patent: 3257646 (1966-06-01), Roth
patent: 3353159 (1967-11-01), Lee, III
patent: 4159538 (1979-06-01), Motsch
patent: 4575818 (1986-03-01), Almy et al.
patent: 4622653 (1986-11-01), McElroy
patent: 5053991 (1991-10-01), Burrows
patent: 5072422 (1991-12-01), Rachels
patent: 5325501 (1994-06-01), Carlstedt
patent: 5394353 (1995-02-01), Nusinov et al.
patent: 5440715 (1995-08-01), Wyland
patent: 5444649 (1995-08-01), Nemirovsky
patent: 548

Affiliated with

Also associated with

Rating

Inter-row configurability of content addressable memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Inter-row configurability of content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inter-row configurability of content addressable memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3027123