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

2001-06-26

Dinh, Son T. (Department: 2824)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S189070

Reexamination Certificate

active

06252789

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.
It would be desirable to have an improved technique of width expanding data words in a CAM array.
SUMMARY OF THE INVENTION
A CAM system for storing a data word chain having a sequence of one or more data words stored in one or more rows of CAM cells is disclosed. For one embodiment, the CAM system includes a plurality of rows of CAM cells each for storing a data word in a data word chain, a plurality of match lines each coupled to a corresponding row of CAM cells, and a plurality of width expansion logic circuits each having a match line input coupled to a match line of a corresponding row of CAM cells, a match line output, a match carry output, a match carry input, and a plurality of control inputs for receiving a plurality of control signals. The match carry output of one of the width expansion logic circuits is coupled to the match carry input of another one of the width expansion logic circuits. The control signals are for determining the operation of the width expansion logic circuits and for indicating when a first data word and a last data word of the data word chain are provided for comparison with the data word of each of the rows of CAM cells. The control signals may also indicate when a continuing data word is provided for comparison with the rows of CAM cells. The continuing data word is a data word between the first and last data word in the data word chain. For one embodiment, the control signals are generated by an instruction decoder in response to decoding separate instructions for comparing the first data word, a continuing data word, and the last data word of a data word chain. The width expansion logic circuits control how and when the match results are provided to a priority encoder, and how and when match results are communicated to each other.
For one embodiment, each row of CAM cells may also include CAM cells for storing classification information that uniquely identifies each data word chain, or that identifies the number of data words in each data word chain. For another embodiment, each row of CAM cells may also include CAM cells for storing control bits that indicate when the data stored in the row of CAM cells is the first, last, or a continuing data word in the data word chain. The control bits may be one or more of a start bit that indicates the first data word, an end bit that indicates the last data word, a continuing bit that indicates a continuing data word, or a default bit that indicates that the row of CAM cells stores a data word that belongs to a data word chain that is only one entry wide. For other embodiments, only one of these four bits may be used in conjunction with the width expansion logic circuits, or the four bits may be encoded to only two bits to represent the four possible types of data words. For one embodiment, the CAM system can store and operate on data word chains of different lengths.
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: 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: 5394353 (1995-02-01), Nusinov et al.
patent: 5440715 (1995-08-01), Wyland
patent: 5483480 (1996-01-01), Yoneda
patent: 5787458 (1998-07-01), Miwa
patent: 5818786 (1998-10-01), Yoneda
patent: 5930790 (1999-07-01), Law et al.
patent: 5943252 (1999-08-01), Schultz et al.
patent: 6081441 (2000-06-01), Ikeda
patent: 6081442 (2000-06-01), Igarashi et al.
patent: 6147890 (2000-11-01), Kawana et al.
Ken Schultz and Andrew Sorowka, “High Performance CAMs for 10GB/s and Beyond”, Gigabit Ethernet Conference (GEC2000), Mar. 27, 2000, pp. 147-154.

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-2478612