Pipelining a content addressable memory cell array for...

Details Pipelining a content addressable memory cell array for... Pipelining a content addressable memory cell array for...

1999-01-15

2002-10-22

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S168000, C365S049130

Reexamination Certificate

active

06470418

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to content addressable memory (CAM) cells. More specifically, the present invention relates to methods and structures for pipelining an array of CAM cells.
2. Discussion of Related Art
CAM cells are defined as memory cells that are addressed in response to their content, rather than by a physical address within an array.
FIG. 1
is a block diagram of a conventional memory array formed using twelve CAM cells. The CAM cells are labeled M
X,Y
, where X is the row of the array, and Y is the column of the array. Thus, the array includes CAM cells M
0,0
, to M
2,3
. Each of the CAM cells is programmed to store a data bit value. In the described example, the data bit value stored in each CAM cell is indicated by either a “0” or a “1” in brackets. For example, CAM cells M
0,0
, M
0,2
and M
0,3
store data bit values of 0, 1, 0 and 0, respectively. Each row of CAM cells is coupled to a common match line. For example, CAM cells M
0,0
, M
0,1
, M
0,2
and M
0,3
are coupled to match line MATCH
0
.
The array of CAM cells is addressed by providing a data bit value to each column of CAM cells. Thus data bit values D
0
, D
1
, D
2
and D
3
are provided to columns 0, 1, 2 and 3, respectively. Note that complementary data bit values D
0
#, D
1
#, D
2
# and D
3
# are also provided to columns 0, 1, 2 and 3, respectively. If the data bit values stored in a row of the CAM cells match the applied data bit values D
0
-D
3
, then a match condition occurs. For example, if the data bit values D
0
, D
1
, D
2
and D
3
are 0, 1, 0 and 0, respectively, then the data bit values stored in the CAM cells of row
0
match the applied data bit values. Under these conditions, the MATCH
0
signal is asserted true (e.g., high). Because the applied data bit values D
0
, D
1
, D
2
and D
3
do not match the data bit values store in the CAM cells of rows
1
or
2
, the MATCH
1
and MATCH
2
signals are de-asserted false (e.g., low). The match signals MATCH
0
-MATCH
2
can be used for various purposes, such as implementing virtual addressing, in a manner known to those skilled in the art.
FIG. 2
is a block diagram of a conventional CAM system
1
that includes a 64 Kbit CAM array
10
and an associated priority encoder
11
. CAM array
10
includes 1024 rows and 64 columns of CAM cells. A 64-bit data input signal D[
63
:
0
] is provided from an input/output (I/O) circuit (not shown) to CAM array
10
. Each row of CAM cells in CAM array
10
simultaneously compares its contents with the input data signal D[
63
:
0
] in the manner described above in connection with FIG.
1
. If a match is detected in any of the rows, CAM array
10
asserts a corresponding match control signal. More specifically, if a match is detected in row N of CAM array
10
, then match control signal MATCH_N is asserted, where N is an integer between 0 and 1023.
More than one of the match control signals can be asserted during a comparison operation. For example, match control signals MATCH_
1
, MATCH_
125
and MATCH_
1000
may be asserted during the same comparison operation. All of the match control signals are provided to priority encoder
11
. Priority encoder
11
determines which one of the asserted match control signals has priority. In response, priority encoder
11
provides a 10-bit output address A[
9
:
0
] that corresponds with the asserted match control signal determined to have priority. The output address A[
9
:
0
] is provided to the I/O circuitry (not shown).
FIG. 3
is a block diagram of a 1 Mbit CAM system
100
that includes sixteen CAM arrays
101
-
116
identical to CAM array
10
(FIG.
2
). Each of the sixteen CAM arrays
101
-
116
receives the input data signal D[
63
:
0
] and simultaneously generates the appropriate match control signals. Priority encoder
120
receives the match control signals from all of the CAM arrays
101
-
116
. In response, priority encoder
120
generates a 14-bit output address A[
13
:
0
].
CAM system
100
consumes a significant amount of power. In general, CAM arrays
101
-
116
consume about 2.5 Watts. Priority encoder
120
also typically consumes about 2.5 Watts. The I/O circuitry associated with CAM system
100
consumes about 1 Watt. This is a significant amount of power to be consumed by a memory system. Consequently, CAM arrays are typically limited to smaller capacities than 1 Mbit (e.g., 1 Kbit).
It would therefore be desirable to have a CAM system having a relatively large capacity, but which consumes less power than a conventional CAM system having the same capacity.
Accordingly, the present invention provides a CAM system that includes a first CAM array and a second CAM array. The first CAM array is coupled to a first match detector and a first priority encoder. The second CAM array is coupled to a second match detector and a second priority encoder. The first CAM array generates a first set of match control signals, and the second CAM array generates a second set of match control signals. The match control signals in the first set have priority over the match control signals in the second set.
During a first memory cycle, the first CAM array is enabled and the second CAM array is disabled. At this time, the first CAM array generates the first set of match control signals in response to an input data value. The first match detector receives the first set of match control signals, and in response, determines whether a match exists in the first CAM array. If a match exists in the first CAM array, the first priority encoder is enabled to process the first set of match control signals. Under these conditions, power savings are realized because it is not necessary to enable either the second CAM array or the second priority encoder.
If a match does not exist in the first CAM array, the first priority encoder is not enabled, and a second memory cycle is initiated. During the second memory cycle, the second CAM array is enabled and the first CAM array is disabled. At this time, the second CAM array generates the second set of match control signals in response to the input data value. The second match detector receives the second set of match control signals, and in response, determines whether a match exists in the second CAM array. If a match exists in the second CAM array, the second priority encoder is enabled to process the second set of match control signals. Under these conditions, power savings are realized because it is not necessary to enable the first priority encoder.
If a match does not exist in the second CAM array, then the second priority encoder is not enabled. Under these conditions, power savings are realized because it is not necessary to enable the first priority encoder or the second priority encoder.
In a variation of the above-described embodiment of the present invention, the first match detector can be divided into a plurality of smaller match detectors, and the first priority encoder can be divided into a corresponding plurality of smaller priority encoders. In this variation, additional power savings are realized within the first priority encoder, because only one of the smaller priority encoders is enabled when there is a match in the first CAM array.
In a second embodiment of the present invention, the first priority encoder can be divided into a first-level priority encoder and a second-level priority encoder. The first-level priority encoder is coupled to receive the first set of match control signals, and reduce these match control signals down to a second set of match control signals. The first match detector is coupled to receive the second set of match control signals, and in response, determine whether a match exists in the first CAM array. If the first match detector determines that a match exists in the first CAM array, then the second-level priority encoder is enabled to process the second set of match control signals. If the first match detector determines that no match exists in the fir

Affiliated with

Also associated with

Rating

Pipelining a content addressable memory cell array for... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pipelining a content addressable memory cell array for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelining a content addressable memory cell array for... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2995064