Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2001-05-07
2002-11-05
Phan, Trong (Department: 2818)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S189070
Reexamination Certificate
active
06477071
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to content addressable memory (CAM) circuitry with a partitioned match line.
BACKGROUND OF THE INVENTION
When one needs to do a fast search among large amounts of data one usually uses associative memories or content addressable memories (CAM). By using a fully parallel CAM, i.e., all cells in all rows of the CAM are searched simultaneously, one can search through the whole memory with only one instruction and this is very fast.
A drawback with a common parallel CAM is the large power consumption. The most common way to implement the match operation in a fully parallel CAM is to use a wired-OR gate for the match operation. This wired-OR gate is implemented with a wire, a match line, which is common to all CAM cells in a row. All cells can discharge the normally precharged line if there is a mismatch, or leave it alone if there is a match, for the searched and the stored bit of each CAM cell. The match line has a high capacitance due to the many CAM cells. The precharge and the very common discharges make the activity of the line almost equal to one under normal usage of the CAM. Hence, the power consumption of the match line is high.
Another known way to implement a CAM is to do it serially. In a serial implementation, a CAM row is searched bit by bit. However, the serial implementations have high latency.
It is also previously known to divide a CAM into parts. U.S. Pat. No. 5,517,441 to Dietz, et al. discloses CAM circuitry in which logic states of a first and second part of a match line are selectively modified in response to comparisons between information, and the logic state of a second match line is selectively modified in response to the logic state of the first match line. This design results in faster comparisons when the search data input is partitioned.
U.S. Pat. No. 5,592,407 to Konishi, et al. discloses an associative memory divided into blocks. The power consumption is reduced by making active only the necessary areas. The prior art does not effectively address the issue of high power consumption in a CAM circuit.
SUMMARY OF THE INVENTION
In a content addressable memory comprising at least one row of memory cells, each memory cell in said row for storing data and including a comparator for comparing the data in said memory cell with search data selectively coupled to the memory cell and a match line connected to the memory cell to indicate whether the search data matched the data stored in the memory cell. In one embodiment, the present invention is a row compare circuit for generating a result output that indicates when the data in each memory cell in said row matches the search data coupled thereto, comprising a plurality of comparison control units for partitioning the memory cells in said row into at least two segments of memory cells, each said comparison control unit for controlling the comparing of the data in the memory cells grouped in its associated segment of memory cells with search data coupled to the memory cells in said segment, each said memory cell in a given segment connected in common to a match line, said match line being caused to indicate whether the search data does not match the data stored in any of the memory cells in that segment, each said comparison control unit except the first comparison control unit operative to determine the result of a previous segment's compare operation, each said comparison control unit being prevented from executing a compare operation with respect to its segment of memory cells when a mismatch has been detected by a previous segment's compare operation in said row, and wherein the first comparison control unit in said row presents the match line connected to the memory cells in the first segment of memory cells to cause the memory cells in said first segment to be compared with search data coupled to the memory cells in said segment whenever a row comparison operation is initiated, said first segment match line being caused to indicate whether the search data does not match the data stored in any of the memory cells in said first segment, said subsequent match lines in said row being present only if combined result of the segment compare operations of the respective preceding segments is a match; and a match determination unit is coupled to the match line of the last segment of memory cells in said row for generating said result output, which may be preset by being precharged.
In another embodiment, each said comparsion control unit has a clock input coupled to a clock signal line from a single clock for triggering its compare operation to begin, wherein the compare operation of said first comparison control unit is triggered by a clock signal without a delay from said clock, and the compare operation of each subsequent comparison control unit is triggered by a clock signal from said clock having a delay.
In another embodiment of the present invention, the row compare circuit further comprises a forward line coupled to each said comparison control unit for transmitting a mismatch signal from one segment to a next segment for preventing the comparison control unit in said next segment from executing a compare operation with respect to its segment of memory cells, said forward line further coupled to said match determination unit for transmitting said mismatch signal to said match determination unit.
In yet another embodiment of the present invention, the content addressable memory row compare circuit further comprises a plurality of group comparison control units, each said group comparison control unit coupled to each segment match line in a column of segments in said group of rows for detecting a mismatch result from any segment match line in said column; a group match determination unit for gating each said match determination unit in said group of rows; and a forward line coupled to each said group comparison control unit for transmitting a mismatch signal from one column of segments to a next column of segments for preventing all comparison control units in said next column of segments from executing a compare operation with respect to its segment of memory cells, said forward line further coupled to said group match determination unit for transmitting said mismatch signal to said group match determination unit.
In still another embodiment of the present invention, the content addressable memory match determination unit is further operative such that if a series of search data to be compared is stored in a plurality of rows such that a row-compare operation for at least two rows is required, the row compare operation of a first row is always executed, and the row compare operation of each subsequent row is executed only if the match determination for the preceding row indicates a match.
The object of the present invention is to provide a novel implementation of a content addressable memory circuit having reduced power consumption. This is achieved by partitioning the match wire and designing the CAM such that the precharge and/or evaluation of the segments of the match line are made conditional. A key advantage of the present invention is that the power consumption of the device from precharging and discharging the match line is reduced since only a part of the comparison circuitry will be activated during most searches. Another advantage is that the present invention provides for a faster operating memory device.
REFERENCES:
patent: 5396449 (1995-03-01), Atalla et al.
patent: 5463751 (1995-10-01), Yonezawa et al.
patent: 5517441 (1996-05-01), Dietz et al.
patent: 5592407 (1997-01-01), Konishi et al.
patent: 5828593 (1998-10-01), Schultz et al.
patent: 5978246 (1999-11-01), Shindo
patent: 5999435 (1999-12-01), Henderson et al.
patent: 6212106 (2001-04-01), Kurotsu
patent: 6295576 (2001-09-01), Ogura et al.
patent: 6310880 (2001-10-01), Waller
Edman Anders
Johansson Henrik
Coudert Brothers LLP
Phan Trong
Switchcore AB
LandOfFree
Method and apparatus for content addressable memory with a... 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 content addressable memory with a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for content addressable memory with a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2980471