Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2000-06-14
2001-06-12
Phan, Trong (Department: 2824)
Static information storage and retrieval
Associative memories
Ferroelectric cell
Reexamination Certificate
active
06246601
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 ML0 and ML3 will be activated. When the priority encoder is enabled, it will output a match address of 0 instead of 3 since ML0 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, ML3 and ML8 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 method is disclosed for writing a data word chain into more than one row of content addressable memory (CAM) cells of a CAM array, and for searching for the data word chain. For one embodiment, the method includes initially writing a first data word of the data word chain into a first row of CAM cells; subsequently writing a last data word of the data word chain into a second row of CAM cells; subsequently comparing the last data word of the data word chain with the data words stored in the first and second row of CAM cells; subsequently comparing the first data word of the data word chain with the data words stored in the first and second row of CAM cells; and determining the address of the first row of CAM cells.
For another embodiment, the method includes initially writing a last data word of the data word chain into a first row of CAM cells; subsequently writing a first data word of the data word chain into a second row of CAM cells; subsequently comparing the first data word of the data word chain with the data words stored in the first and second row of CAM cells; subsequently comparing the last data word of the data word chain with the data words stored in the first and second row of CAM cells; and determining the address of the first row of CAM cells.
For another embodiment, the method includes initially writing a first data word of the data word chain into a first row of CAM cells; subsequently writing a last data word of a data word chain into a second row of CAM cells; subsequently comparing the first data word of the data word chain with the data words stored in the first and second row of CAM cells; subsequently comparing the last data word of the data word chain with the data words stored in the first and second row of CAM cells; and determining the address of the first row of CAM cells.
For yet another embodiment, the method includes initially writing a last data word of a data word chain into a first row of CAM cells; subsequently writing a first data word of a data word chain into a second row of CAM cells; subsequently comparing the last data word of the data word chain with the data words stored in the first and second row of CAM cells; subsequently comparing the first data word of the data word chain with the data words stored in the first and second row of CAM cells; and determining the address of the first row of CAM cells.
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: 5325501 (1994-06-01), Carlstedt
patent: 5394353 (1995-02-01), Nusinov et al.
patent: 5440715 (1995-08-01), Wyland
patent: 5483480 (1996-01-01), Yoneda
patent: 5576985 (1996-11-01), Holtz
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.
patent: 6166938 (2000-12-01), Wong
Ken Schultz and Andrew Sorowka, “High Performance CAMs for 10GB/s and Beyond”, Gigabit Ethernet Conference (GEC2000), Mar. 27, 2000, pp. 147-154.
Blakely & Sokoloff, Taylor & Zafman
NetLogic Microsystems, Inc.
Phan Trong
LandOfFree
Method and apparatus for using an inter-row configurable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for using an inter-row configurable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for using an inter-row configurable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2499140