Method and data processing system for data lookups

Details Method and data processing system for data lookups Method and data processing system for data lookups

2000-12-22

2002-03-05

Phan, Trong (Department: 2818)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S189070, C365S195000

Reexamination Certificate

active

06353548

ABSTRACT:

PRIOR FOREIGN APPLICATION
This application claims priority from European patent application number 99126171.0, filed Dec. 30, 1999, which is hereby incorporated herein by reference in its entirety.
TECHNICAL FIELD
The present invention is generally related to a method and a data processing system for data lookups using high-speed memories. More particularly, the present invention relates to a content addressable memory (CAM) or associative content addressable memory, in such a system.
BACKGROUND ART
An associative memory or content addressable memory (CAM) is a memory comprising a plurality of CAM circuits, each comprising a memory circuit and a compare circuit. The CAM is accessed by data content, rather than by the address or location of data.
FIG. 1
shows a block diagram of a CAM according to the prior art comprising a plurality of CAM circuits.
FIG. 2
shows a single CAM circuit of
FIG. 1
in more detail.
A known CAM
100
comprises a plurality of identical CAM circuits
109
,
110
to
124
, such as 16 CAM circuits
0
to
15
, and an OR-gate
143
, as shown in FIG.
1
.
As depicted in
FIG. 2
, each known CAM circuit
109
,
110
to
124
comprises a memory circuit
102
and a compare circuit
106
. The memory circuit
102
consists of a memory cell array and the compare circuit
106
comprises a comparator array
126
and a NAND- gate
125
. The output of each memory cell (CELL D
0
to CELL D
31
) of the memory circuit
102
is connected with a first input of a corresponding comparator CO
0
to CO
31
in comparator array
126
via output means
104
of the memory circuit
102
and data input means
105
of the compare circuit
106
. Compare data C
0
to C
31
, representing the bits of a 32-bit-word, are applied to second inputs of the comparators CO
0
to CO
31
in comparator array
126
via compare data input means
107
of compare circuit
106
. The comparators are XOR-gates, i.e. exclusive OR-gates. Via input means
103
of memory circuit
102
input data D
0
to D
31
, also representing the bits of a 32-bit-word, and to be stored in the memory circuit
102
, are applied to input means
103
of the memory circuit
102
. Each bit of the input data D
0
to D
31
is stored in a corresponding memory cell of the memory circuit
102
, if a write signal is applied to a write line
0
(WL
0
) of the CAM circuit
0
(
109
). The write signal enables writing into the memory cells.
In the following, the operation of known CAM circuit
0
(
109
) will be described in more detail. It shall be assumed that input data have already been stored in the memory cells of memory circuit
102
in a first step or cycle. Accordingly, each memory cell stores one bit of the input data.
In a second step or cycle, input data D
0
to D
31
are applied to the input means
103
of memory circuit
102
and a write signal is applied to word line
0
(WL
0
) enabling storage of the second input data D
0
to D
31
in the memory cells (CELL D
0
to CELL D
31
) of the memory circuit
102
.
Since it takes a certain time until the first input data stored in said memory circuit
102
are substituted by the applied second input data D
0
to D
31
in the memory cells, the data status of each memory cell and accordingly of the memory circuit
102
is not defined in the step of storing the second input data D
0
to D
31
. Accordingly, it is necessary to wait a certain time, until the outputs of all memory cells comprise a defined status, i.e. the outputs represent the second input data D
0
to D
31
. Although the waiting period depends on the characteristics of the memory cells, a typical period lasts at least about to the same time it takes to perform a compare operation. This time has to pass before the compare operation can be started and a comparison result may be used for further processing.
Otherwise, it cannot be made sure that a comparison of the data present in memory circuit
102
with the compare data C
0
to C
31
by the comparator array
126
is a comparison of the second input data D
0
to D
31
with the compare data C
0
to C
31
.
Each comparator of comparator array
126
generates an output signal indicating whether its applied input bit (0-bit or 1-bit, i.e. a low-level signal or a high-level signal) is identical to its applied compare bit (also a 0-bit or a 1-bit, i.e. a low-level signal or a high-level signal). The output signal or comparison result of each comparator of comparator array
126
is applied to a corresponding input of the NAND-gate
125
, which performs a logical AND-operation with the output signals of all comparators and inverts the output signal on the single output line
127
of the NAND-gate
125
.
As shown in
FIG. 1
, each line
127
,
128
to
142
of the CAM circuits
0
to
15
is applied to a corresponding input of the OR- gate
143
, which comprises a single output line
144
forwarding a match signal generated by at least one of the CAM circuits
0
,
1
, . . . ,
15
(
109
,
110
, . . . ,
124
) to a data processing system (not shown) comprising the known CAM
100
for further processing.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a more efficient method and data processing system for data lookups.
It is another object of the present invention to provide a method and a data processing system using a content addressable memory, which is more efficient.
It is yet another object of the present invention to provide a method and a data processing system comprising a content addressable memory that performs a comparison of input data and compare data within a lower amount of clock cycles or steps, or within a shorter cycle.


REFERENCES:
patent: 5930359 (1999-07-01), Kempke et al.
patent: 5946704 (1999-08-01), Yoneda et al.
patent: 6175514 (2001-01-01), Henderson et al.

Affiliated with

Also associated with

Rating

Method and data processing system for data lookups 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 data processing system for data lookups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and data processing system for data lookups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2863124