Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2002-01-31
2004-07-27
Yoha, Connie C. (Department: 2818)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S203000, C711S108000
Reexamination Certificate
active
06768659
ABSTRACT:
The present invention relates generally to the field of content addressable memories (CAMs) and more particularly to a circuit and method for reducing power usage during search operations in a CAM.
BACKGROUND OF THE INVENTION
A CAM is a memory device in which data is accessed and modified based on the content of the stored data, rather than the location where the data is stored. In general, a typical CAM search operation involves receiving a search data word and comparing the search data word with all entries in the CAM to determine whether there exists a single match, a multiple match or a mismatch between the search data word and entries in the CAM. Each storage location in a row of a CAM is connected to a matchline that indicates a match or mismatch result of the comparison between the stored data word and the search word. All match lines indicating a match condition are typically processed by a priority encoder (PE) to determine a highest priority match address which is provided as an output of the CAM.
Each data word and match line combination has a unique N-bit address within the CAM. Accordingly, for any search cycle there may be up to 2
N
match lines activated. The priority encoder is coupled to the match lines and generates an N-bit address corresponding to the highest priority active match line. This N-bit address may then be used, for example, as a pointer in an Internet Protocol (IP) routing table lookup, compression and decompression or fully associative cache memory implementations in microprocessor systems. Ternary CAMs are widely used in networking applications due to their ability to store logic “1”, logic “0” as well as “don't care” states. There is an ever increasing demand for wider data width CAMSs. CAMs are commonly available in data widths (denoted by M) that are 72-bits and 144-bits and more recently 288-bits wide.
With increasing data widths, power or current consumption during search operations in the CAM becomes increasingly important. The reason for this may be explained as follows.
In a search operation, data is provided to the CAM for comparing to stored data. The CAM cells are normally designed such that a match between search data and stored data provides a non-conductive path, whereas a mis-match provides a conductive path. A row of CAM consists of cells coupled in parallel between common nodes called a match line (ML) and a tail line (TL). Each individual ML connects to M cells (where M is the number of bits or usually the data width). Typically, in a search operation, M-bit search data is provided to a search data path which consists of M search lines coupled to corresponding columns of CAM cells. All N-rows of the CAM simultaneously then compare the search data with the stored data in each cell-typically implemented as an exclusive-OR comparison block-and provide a result of his comparison to each match line associated with each row of the CAM. The result on the match line is then sensed, amplified and typically latched in order to provide a logic level result of the search operation.
There are two main sources of substantial power consumption during search operations in CAM's: power consumed by match lines and power consumed by search lines. Conventionally, all match lines are precharged to a logic ‘H’ state (a match condition), and then the comparison with search data is allowed to pull match lines to a logic ‘L’ state (a miss condition).
In most CAM applications “misses” occur more frequently than “hits”. Precharging match lines to a logic ‘H’ and discharging match lines to logic ‘L’ for misses tends to generate high power consumption due to the high current associated with charging and discharging all match lines for each search operation. In additions with an increased number of cells connected to each match line for wider-word CAM applications, the capacitance of match lines increases accordingly, which in turn increases the current required to charge and discharge the match lines.
Various solutions have been proposed for reducing the power consumed during search operations, such as segmenting match lines into multiple segments and activating segments sequentially based on match or miss results of previous segments,
For example, a segmented match line architecture is described in U.S. Pat. No. 6,243,280 (Wong et al.)., wherein rows of the CAM are partitioned into a plurality of segments. For each match line, the first of the plurality of match line segments is precharged and a search operation is performed on the first segment. In case of a match in the first segment, the second match line segment is selectively precharged and searching proceeds to the second segment. If there is a match in the second segment, a third segment is precharged and searching proceeds in a similar manner until all segments of a match line have been searched. Precharging of a subsequent segment therefore only occurs in case of a match result in a previous segment. In the case of a match in all segments, selective precharging each segment to a logic ‘H’ however still requires a large current. Furthermore, a significant delay is introduced in the search time by having to wait for the selective precharge to occur in a segment before proceeding with the actual comparison in that segment.
U.S. Pat. No. 6,191,970 (Pereira) a match line is divided into multiple segments all of which are simultaneously precharged to a logic ‘H’ state prior to beginning a search operation. In addition, each CAM cell has an associated discharge circuit for selectively discharging its corresponding match line segment in response to a disable signal from a previous match line segment. A segment therefore is only discharged if the immediately preceding segment results in a miss while all subsequent segments remain precharged to a logic ‘H’. As a result, the miss condition of one segment is propagated along the remainder of the row without discharging all other segments along the row. While this approach alleviates the problem of delays introduced by selectively precharging segments, the potential for high current consumption still remains, since all match lines must first be precharged to a logic ‘H’ state. In addition, the match detect of each segment must be synchronized to a clock signal, clocked since the match line precharges to a hit. As a result, either a number of internal clocks must be generated, or the system clock must be used which increases system latency. Finally, in order to prevent discharge before the segment is enabled a series coupled device is added to each CAM cell, thereby increasing chip area and slowing down the entire operation.
In an article entitled “Use of Selective Precharge for Low Power on the Match Lines of Content Addressable Memories” by Zukowski et al. IEEE 1997 there is described a method whereby a small segment of an overall match line is precharged and used to perform a partial comparison first and only if a match occurs in that first small segment is the remaining segment of the match line precharged and eventually searched. The article also suggests that theoretically the selective precharge technique could be extended to cover more than one stage, but the additional overhead, extra clock phases and additional buffering would not provide any large additional gains over the single stage selective precharge proposed therein. This approach does not consider the possibility of having multiple match line segments working sequentially but independently of clock cycles, providing a sufficiently fast process technology is available to implement the necessary circuitry. Furthermore, the approach discussed by Zukowski et al. still relies on a precharge to a logic ‘H’ state which can draw large amounts of current as previously explained.
Thus there is still a need for a CAM which is capable of consuming less power during search operations than conventional search techniques.
SUMMARY OF THE INVENTION
In accordance with the present invention there is provided a method for selectively enabling, during a search operation, at least one of a plurality o
Gillingham Peter
Roth Alan
Mosaid Technologies Incorporated
Yoha Connie C.
LandOfFree
Circuit and method for reducing power usage in a content... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit and method for reducing power usage in a content..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit and method for reducing power usage in a content... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3241047