Dual match-line, twin-cell, binary-ternary CAM

Details Dual match-line, twin-cell, binary-ternary CAM Dual match-line, twin-cell, binary-ternary CAM

2002-08-15

2004-03-09

Nguyen, Viet Q. (Department: 2818)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S203000, C365S204000, C365S202000, C365S189070, C365S051000

Reexamination Certificate

active

06704216

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to static information storage and retrieval systems, and more particularly to associative memories, which are also referred to as content or tag memories.
2. Background Art
In a content addressable memory (CAM), an input word (the data-in word) consists of an ordered group of K bits which is compared bit-by-bit with a plurality of stored words in the CAM. If all of the bits of one of the stored words match those of the data-in word, the address of that stored word is output to the user. Sometimes more than one stored word matches the data-in word. In this case, usually only one address is output, based on a pre-specified priority criterion.
On the other hand, in many cases not all bits need to match when such comparisons are performed. Some bits in a stored word may then be masked out, and not compared with the corresponding bits in the data-in word. It is considered a legitimate match here if the stored word matches the data-in word for all but the masked bits. Technically, a masked bit always returns a match condition so that it does not affect the overall result.
A CAM wherein stored words must be compared bit-by-bit without exception is called a binary CAM, and its memory cells have two logic states: a “0” state and a “1” state. In contrast, a CAM that allows stored words to have masked bits is called a ternary CAM. The memory cell of a ternary CAM has three logic states: a “0” state, a “1” state, and a “DON'T CARE” state that returns an unconditional match.
FIG. 1
shows a typical stored word in a binary CAM. It consists of a row of SRAM cells having differential outputs DSk and DSkB (DSk bar) which are compared with corresponding differential data-in lines Dlk and DlkB through a comparator. The set of connections for the comparator logic, also commonly termed a logic comparison function, is equivalent to (DSk*DlkB)+(DSkB*Dlk)=DSk(+)Dlk, which is effectively an EXCLUSIVE OR function. At the beginning of each compare cycle a match line (ML) is pulled high by connection to a voltage source V
DD
) via a pre-charge gate (MP
0
; typically a PMOS device), and all of the data lines Dlk and DlkB, where k=1 . . . K, are held low. The pre-charge gate is then turned off, leaving the match line floating. At the same time the Dlk data lines are driven by the input data. If DSk=Dlk then DSk (+)Dlk=0 and the cell k leaves the match line alone. This is a match condition.
On the other hand, if DSk≠Dlk then DSK(+)Dlk=1 and one of the series pairs of pass-gates (typically NMOS devices) will conduct and discharge the match line to ground. This is a non-match condition. Since it takes only one non-matched cell to discharge the match line to ground, a word is said to match with the data-in word if DSk=Dlk for all k=1 . . . K. That is if the match line stays high. Since all cells are counted in the compare here this is a binary CAM. The two states of the cell are: a “1” state with DSK=1 (high) and DSkB=0 (low); and a “0” state with DSK=0 and DSkB=1.
FIG. 2
shows a typical stored word in a ternary CAM. Since the memory cell of a ternary CAM needs three states, two SRAM cells sharing a comparator form a ternary cell. There are now three usable states: a “1” state, with DS
1
=1 and DS
2
=0; a “0” state with DS
1
=0 and DS
2
=1; and a “DON'T CARE” state with DS
1
=DS
2
=0. The data-in lines Dl and DlB are connected in the same fashion as in
FIG. 1
, forming an EXCLUSIVE OR logic function. The pre-charged match line (ML) stays high if Dl
1
=1and the cell is in the “1” state or Dl
1
=0 and the cell is in the “0” state. When the cell is in the “DON'T CARE” state, with both series pairs of pass-gates cut off and preventing the match line discharging to ground, a match condition is guaranteed and the cell has no effect on the overall result. Notice that the DSk and DSkB outputs of all odd numbered SRAM are the mirror images of the associated even numbered SRAM for easy layout.
As can be seen by comparing FIG.
1
and
FIG. 2
, the only difference between a binary CAM cell and a ternary CAM cell is that in a ternary cell a single comparator is shared by two SRAM cells. Most ternary CAM on the market today uses this configuration to save die area and to simplify component connection. Such CAM can still be used as a binary cell, but then the die area is not used efficiently, because two SRAM cells are being used to hold only one bit of data.
Another major concern regarding the efficient use of CAM is power consumption. As those skilled in the electronic arts well know, reducing power consumption is generally desirable in a circuit. However, in CAM it is an increasingly concern because CAM is often used in portable, battery operated devices and the consumption of power relates directly to how long such devices can be operated. Any reduction in CAM power consumption is therefore a highly desirable benefit.
FIG. 3
depicts a logical approach, based on industry trends, to achieving a binary-ternary CAM. It should be noted, however, that the present inventors do not know of any products actually using this approach.
FIG. 3
is included here as a useful comparison to the present invention. Yet another manner of achieving binary-ternary CAM, and one which takes a much different approach, is described in U.S. Pat. No. 6,362,992.
As can also be seen by comparing
FIGS. 1-3
, a common feature of CAM (and many other parallel comparison circuits, for that matter) is the use of a match line (ML). Only a few memory cells are shown in the examples, with all in a single row connected to only a single match line. In actual practice, there typically will be thousands of cells in each row and hundreds or thousands of such rows, each having a respective match line. Each such match line is pre-charged with a voltage and when a match condition occurs the match line discharges, nominally to ground. Conceptually similar circuits can be constructed, but are not common, where the match line is pre-grounded and a match condition causes charging to some voltage level which is detected. Unfortunately, these approaches to match detection have a number of problems.
One can consider just one row. In view of the large number of cells present, it should be clear that the match line for such a row will have an appreciable capacitance. The pre-charge sub-circuit (e.g., MP
0
in
FIG. 1
) has to handle this, and will typically take up a relatively large amount of die space or “real estate.” The row also necessarily operates at a particular clock rate, performing pre-charging, comparison, and match detection in each cycle. In this approach, the match line necessarily also runs at that clock frequency. However, as those skilled in the electronic arts also accept as a maxim, it is generally desirable to reduce sub-circuit frequency wherever possible, while maintaining overall system frequency. Lower operating frequency typically correlates with reduced power consumption, component life, etc. Additionally, switching high power and reactive loads at high frequency is undesirable because of possible collateral effects due to electro-magnetic radiation.
In summary, it is desirable to have a more flexible CAM, which can be efficiently applied as either binary or ternary CAM. It is also desirable to have CAM, in the form of binary CAM, ternary CAM, or configurable binary-ternary CAM, which consumes less power. And it is further desirable to have CAM which operates sub-circuits at low effective frequency, particularly including the match line sub-circuit.
DISCLOSURE OF INVENTION
Accordingly, it is an object of the present invention to provide a CAM which is configurable to operate in either binary mode or ternary mode, yet which is efficiently able to utilize all memory cells in either mode.
Another object of the invention is to provide a CAM which provides substantial power savings.
Briefly, on

Affiliated with

Also associated with

Rating

Dual match-line, twin-cell, binary-ternary CAM does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dual match-line, twin-cell, binary-ternary CAM, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dual match-line, twin-cell, binary-ternary CAM will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3230097