Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2003-03-11
2004-08-10
Le, Vu A. (Department: 2824)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S189070
Reexamination Certificate
active
06775167
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to memory circuits, and more specifically to low power search techniques in content addressable memory circuits using sample words to save power in compare lines.
2. Description of the Related Art
A content addressable memory (CAM) semiconductor device is a device that allows the entire contents of the memory to be searched and matched instead of having to specify one or more particular memory locations in order to retrieve data from the memory. Thus, a CAM may be used to accelerate any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks.
CAMs provide performance advantages over conventional memory devices having conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired search term, or comparand, against the entire list of entries simultaneously, giving an order-of-magnitude reduction in the search time. For example, a binary search through a non-CAM based database of 1000 entries may take ten separate search operations whereas a CAM device with 1000 entries may be searched in a single operation, resulting in significant time and processing savings. Internet routers often include a CAM for searching the address of specified data, allowing the routers to perform fast address searches to facilitate more efficient communication between computer systems over computer networks.
Conventional CAMs typically include a two-dimensional row and column content addressable memory core array of cells. In such an array, each row typically contains an address, pointer, or bit pattern entry. In this configuration, a CAM may perform “read” and “write” operations at specific addresses as is done in conventional random access memories (RAMs). However, unlike RAMs, data “search” operations that simultaneously compare a bit pattern of data against an entire list (i.e., column) of pre-stored entries (i.e., rows) can be performed.
FIG. 1A
shows a simplified block diagram of a conventional CAM
100
. The CAM
100
includes a data bus
102
for communicating data, an instruction bus
104
for transmitting instructions associated with an operation to be performed, and an output bus
106
for outputting a result of the operation. For example, in a search operation, the CAM
100
may output a result in the form of an address, pointer, or bit pattern corresponding to an entry that matches the input data.
As mentioned above, to perform a search operation a CAM includes a plurality of bit pattern entries, each comprising a series of CAM cells coupled to a local match line.
FIG. 1B
is a schematic diagram showing a prior art bit pattern entry
120
in a conventional CAM. The bit pattern entry
120
includes a plurality of CAM cells
122
coupled to a local match line
124
. In addition, the bit pattern entry
120
includes a current generator
126
and precharge circuitry
128
coupled to the local match line
124
. The local match line
124
is further coupled to an inverter
130
, which is coupled to an inverter latch
132
. Each CAM cell
122
is also coupled to a pair of compare lines K
0
and K
1
. Although, for clarity, only one CAM cell
122
is shown coupled to compare lines in
FIG. 1B
, it should be noted that all the CAM cells
122
are actually coupled to compare lines.
During a search operation, the precharge circuitry
128
precharges the match line
124
to a predictable state, which is generally low, to prepare for the search. The compare data, known as the comparand, is then compared to the bit pattern entry
120
. Specifically, compare lines, such as compare lines K
0
and K
1
, are used to compare the comparand to the data stored in the CAM cells
122
. The current generator
126
begins to supply current to the match line
124
. As the compare data is compared to the data stored in each CAM cell
122
, the CAM cell will ground the match line
124
if the data stored in the CAM cell
122
does not match the compare data. Thus, if any CAM cell
122
does not match the compare data, the match line
124
will be pulled low. Conversely, if all the CAM cells
122
in the bit pattern entry
120
match the comparand, the match line
124
will remain high. The signal from the match line
124
is then sent through an inverter
130
, and then to the inverter latch
132
, which provides a high or low output, as described in greater detail below.
FIG. 1C
is a diagram showing exemplary search signals
150
for a conventional CAM. The search signals
150
include an external clock
152
, a first compare line K
0
154
, a second compare line K
1
156
, an internal clock
158
, a match line
160
, and a search output
162
. As previously mentioned, during a search the compare lines
154
and
156
are used to provide search data to a particular CAM cell. Each compare line
154
and
156
will be set to either high or low, depending on the search data. Typically the compare lines K
0
154
and K
1
156
are set to the inverse of each other, however, when using a ternary CAM cell both compare lines
154
and
156
may be set to the same value. In the example of
FIG. 1C
, a first set of search data is placed on the compare lines for the first and second external clock cycle
150
a
and
150
b
. Then the search data is inverted in the third and fourth external clock cycle
150
c
and
150
d
. In addition, the data stored in the CAM cell matches the first set of search data, during the first and second external clock cycle
150
a
and
150
b
, and does not match during the third and fourth external clock cycle
150
c
and
150
d.
To set the compare lines
154
and
156
to their appropriate values in a conventional CAM, each compare line
154
/
156
is first set to a predictable state of zero, or low. Then, one of the compare lines is asserted high. As shown in
FIG. 1C
, at the rising edge of the first external clock cycle
150
a
, both compare lines
154
and
156
are set low. Shortly thereafter, one of the compare lines is asserted high, in this case compare line K
0
154
, thus in the first external clock cycle
150
a
, K
0
154
is asserted high and K
1
remains low.
Next, at the rising edge of the second external clock cycle
150
b
, compare line K
0
154
is again set to a predictable state of zero. In this case, the search data for this particular CAM cell remains the same in the second external clock cycle
150
b
, thus compare line K
0
154
is again asserted high shortly after the rising edge of the second external clock cycle
150
b
. In a similar manner, both compare lines K
0
154
and K
1
156
are set to a state of zero at the beginning of the third external clock cycle
150
c
. This time the comparand changes, thus switching compare lines K
0
154
and K
1
156
such that K
1
156
is asserted high shortly after the rising edge of the third external clock cycle
150
c
, while K
0
154
remains low. At the rising edge of the fourth clock cycle
150
d
, both compare lines
154
and
156
are set to zero. The search data remains the same for the fourth external clock cycle
150
d
, thus compare line K
1
156
is again asserted high shortly after the rising edge of the fourth clock cycle
150
d.
Thus, in a conventional CAM the compare lines are pulsed to compare the search data to the data stored in the CAM cell. This results in two transitions for every clock cycle of the external clock
152
, regardless of the actual data being placed on the compare lines. As will be explained in greater detail subsequently, each transition requires increased power in the CAM to overcome the capacitance of the compare line.
Continuing with the above example, an internal clock
158
is used to control the search results in the conventional CAM. The internal clock
158
is an inverted clock, which is pulsed slightly after the compare lines
154
and
156
are set to the appropriate search value. As mentioned above, in the example of
FIG. 1C
the search data matches the data store
Avramescu Radu
Podaima Jason Edward
Le Vu A.
Martine & Penilla LLP
Nguyen Tuan T.
SiberCore Technologies, Inc.
LandOfFree
System and method for low power searching in 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 System and method for low power searching in content..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for low power searching in content... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3276620