Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2001-06-11
2003-01-28
Elms, Richard (Department: 2824)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S189070
Reexamination Certificate
active
06512684
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to content addressable memory (CAM) devices, and more specifically, to the design and use of a CAM circuit having a plurality of cascaded sub-entries, each sub-entry having a Match-enabled output adapted to enable the CAM search operation of the next sub-entry.
RELATED ART
A Content Addressable Memory (CAM) is a device adapted to perform fast searches of list-based data stored in a plurality of locations called CAM entries. Each CAM entry stores a word (i.e., a plurality of binary or ternary bits) of data in a plurality of CAM cells, and includes circuits to perform comparisons with an externally asserted comparand word typically stored in a comparand buffer.
In many CAM circuits of the related art, all of the CAM cells of a given CAM entry are tied directly to the same Match Line (ML) and share a single distributed Match Line Pass-Gate (i.e., the sum of all XNOR circuitry of all the CAM cells in that Match Line's CAM entry) which performs the logical comparison function and which is connected between the Match Line and a Low voltage level.
The Match Line of a CAM entry functions as a single capacitor having capacitance (C
ML
) that is pre-charged (e.g., through pre-charge transistor) to a logic High voltage (e.g., Vdd) prior to each search, and the observable event on each Match Line will be a MISS (the logical opposite of a MATCH which may be called a HIT), which will cause the Match Line voltage to drop (discharge towards ground voltage) from the pre-charged High voltage to a Low voltage through the Match Line Pass-Gate.
In the CAM arrays of the related art, as the size (i.e., width X) of the binary word storable in each CAM entry is increased, the capacitance (C
ML
) of each CAM entry's Match Line generally increases proportionately. Thus, in the related art, the Match-sensing hardware designer is faced with the problem of reliably detecting the much smaller and slower voltage change on a Match Line having a potentially large and entry-width-dependent capacitance. Accurate Match-detection requires a circuit to distinguish between the characteristics of a MATCH-ing entry from the characteristics of a MISS-ing entry having as few as only one mismatched data bit (i.e., providing only one conducting leg in the Match Line Pass Gate through which to discharge the Match Line capacitor to the Low voltage). The larger the Match Line's capacitance (C
ML
), the longer it will take to discharge in the case of a MISS-ing entry, in turn requiring a longer detection period. This generally requires customized sensing circuitry tailored for a specific CAM entry width, and therefore limits the scalability of the CAM circuits of the related art. And, the larger the CAM entry, the greater is the challenge to the designer to define reliable strobing protocols and sensing margins necessary to activate a reliable MATCH or HIT output signal, while maximizing the search frequency. Because only one search at a time can be performed on a CAM entry having one Match Line, the maximum frequency of CAM search operations generally decreases as the width of the CAM entry is increased.
Since the energy consumed (E
CAP
) by the complete discharge of a capacitor (e.g., a Match Line) is equal to ½ CV
cap
2
, where C is the capacitance and V
cap
is the Voltage across the capacitor, the energy consumed per search by each MISS (e.g., E
MISS
=E
CAP
) with single Match Line systems can increase approximately proportionally with the increased size (bits) of the word storable in the CAM entry. Match Lines in wider CAM entries have larger capacitance associated with them and will therefore consume more power during a search operation and have lower search frequency.
The explosive growth and increasing speed of Intranets and the Internet is fueling the demand for larger, faster, and more energy-efficient CAM circuits. The large CAM memory arrays of the related art can consume multiple watts of power during performance of search operations. It is desirable that the entry-width of CAM arrays may be increased without additional power consumption and/or without reducing the CAM search frequency significantly. A growable CAM architecture (e.g., a data word-width scalable CAM circuit architecture) is desirable for reducing the burdens on circuit designers when implementing wider CAM circuits.
SUMMARY OF THE INVENTION
The present invention overcomes the problems and limitations of the related art by providing a cascadable CAM sub-entry architecture based on CAM blocks, and a plurality of exemplary circuits for gating match line segments within CAM blocks, and methods of selecting and combining these blocks to obtain power-savings and/or high performance.
It is desirable that a wide CAM array will consume only minimal energy during operation, and operate at a high speed and/or at a high CAM search frequency, and that each CAM search will reliably generate a Match/HIT output for only CAM entries storing a MATCH-ing word. Accordingly, a first aspect of the invention provides a content addressable memory (CAM) device comprising: a first CAM block having a binary first block input and a binary first block output and including a first sub-entry. The first sub-entry includes one or more CAM cells, each CAM cell in the first sub-entry being coupled to a first match line segment and to a first search-enabling line segment. The device further comprises a first combinatorial logic gate having a binary first gate output and a first gate input, the first gate input being the first match line segment, the first gate output being the first block output. A CAM comparison is performed on the first sub-entry only if a predetermined binary logic voltage level is being asserted at the binary first block input. The first block output will assert the predetermined binary logic voltage level if the first sub-entry is a match-ing sub-entry.
A second aspect of the invention provides a content addressable memory array comprising a plurality of CAM entries, each CAM entry being segmented into first, second and third sub-entries, the first, second and third sub-entries including a first, second and third match-line segment respectively. The first match-line segment is operatively coupled to the second match-line segment through a first combinatorial logic gate, the second match-line segment is operatively coupled to the third match-line segment through a second combinatorial logic gate.
A third aspect of the invention provides a digital system, such as for example, a computer, or a network router, comprising a digital processor operatively coupled to a CAM array, the CAM array having cascaded CAM blocks, as in the forgoing aspects of the invention.
A fourth aspect of the invention provides an ASIC library comprising an ASIC library element having electrical rules that describe devices within and describe interconnections between the devices within a CAM block in accordance with embodiments of the invention.
A fifth aspect of the invention provides a method of performing a CAM comparison on a CAM entry, the method comprising: providing a first CAM block including a binary first block input, a binary first block output, a first CAM cell, the first CAM cell being operatively coupled to the first block input and to the first block output; and performing a CAM comparison on the first CAM cell only if a predetermined binary logic voltage level is asserted at the binary first block input; and asserting the predetermined binary logic voltage level at the first block output.
A sixth aspect of the invention provide a method of performing a CAM comparison on a CAM entry having a first sub-entry and a second sub-entry, the method comprising: providing a first CAM block having a binary first block input and a binary first block output and including the first sub-entry, the first sub-entry having one or more CAM cells; performing a CAM comparison on the first sub-entry only if a predetermined binary logic voltage level is being asserted at the binary first block input; asserting the prede
Gordon Tarl S.
Nadkarni Rahul K.
Elms Richard
International Business Machines - Corporation
Phung Anh
Schmeiser Olsen & Watts
Walsh Robert A.
LandOfFree
Content addressable memory having cascaded sub-entry... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Content addressable memory having cascaded sub-entry..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory having cascaded sub-entry... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3065640