Content addressable memory with longest match detect

Details Content addressable memory with longest match detect Content addressable memory with longest match detect

1999-07-27

2002-04-09

Elmore, Reba I. (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S103000, C711S100000

Reexamination Certificate

active

06370613

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to content addressable memory (CAM) systems. More specifically, the present invention relates to methods and structures for performing a longest match operation in a CAM system.
2. Discussion of Related Art
CAM cells are defined as memory cells that are referenced in response to their content, rather than by a physical address in an array.
FIG. 1
shows a block diagram of a conventional CAM array
100
including twelve CAM cells, three match lines ML
0
-ML
2
, four data lines DL
0
-DL
3
, four complementary data lines DL
0
#-DL
3
#, and a splitter
110
. A CAM array is specified by a depth, equal to its number of rows, and a width, equal to its number of columns that define the number and length, respectively, of words that can be stored in the array. For example, CAM array
100
has a depth of three bits (three rows) and a width of four bits (four columns) and is therefore a 3×4 array capable of storing three words of four bits each.
The individual CAM cells in CAM array
100
are labeled C
x,y
, where X is the row of the array and Y is the column of the array. Thus, CAM array
100
includes CAM cells C
0,0
to C
2,3
. Each row of CAM cells is coupled to a common match line, and each column of CAM cells is coupled to a common data line and a common complementary data line. For example, CAM cells C
0,0
, C
0,1
, C
0,2
, and C
0,3
are all coupled to match line ML
0
. Similarly, CAM cells C
0,0
, C
1,0
, and C
2,0
are all coupled to data line DL
0
and complementary data line DL
0
#. 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 C
0,0
, C
0,1
, C
0,2
, and C
0,3
store data bit values of 0, 1, 0, and 0, respectively.
The CAM array
100
is addressed by providing a data bit value to each column of stored bit values, or bit slice, in the array. Splitter
110
receives an input word as a four-bit input data value ID[
3
:
0
], and applies the individual data bit values ID[
0
], ID[
1
], ID[
2
]and ID[
3
] to data lines DL
0
, DL
1
, DL
2
, and DL
3
, respectively. Splitter
110
also provides complementary data bit values ID#[
0
], ID#[
1
], ID#[
2
] and ID#[
3
] to columns
0
,
1
,
2
, and
3
, respectively, by complementary data lines DL
0
#, DL
1
#, DL
2
#, and DL
3
#, respectively. Each row of CAM memory cells includes match logic (not shown) to indicate when a match condition occurs, i.e., when the data bit values stored in the CAM memory cells of that row match the applied data bit values ID[
3
:
0
]. For example, if the data bit values ID[
0
], ID[
1
], ID[
2
], and ID[
3
] are 0, 1, 0, and 0, respectively, the data bit values stored in the CAM cells along row
0
match the applied data bit values. Under these conditions, a match signal MS
0
on match line ML
0
is asserted TRUE. Because the applied data bit values do not match the data bit values stored in the CAM memory cells of rows
1
and
2
, match signals MS
1
and MS
2
on match lines ML
1
and ML
2
, respectively, are deasserted. Match signals MS
0
-MS
2
can be used to determine any or all row addresses within CAM array
100
which have their match line asserted.
A CAM array does not always contain a match for a given input data value. However, some of the bits of a row may match the input data value, while other bits of the row do not match the input data value. In such cases, it is often desirable to locate the stored word that provides the “longest match” with the input word. This “longest match” determination involves selecting the row of CAM cells containing the longest string of data bit values providing a match with the data bit values of the input word, starting from either its least significant bit (LSB) or most significant bit (MSB).
FIG. 2
shows a block diagram of a conventional CAM system
200
providing longest match capability. CAM system
200
includes a bit-wise mask logic
210
, a M×N CAM array
220
, a no-match decoder
230
, a priority encoder
240
and software
250
for controlling the recursive mask generation process. Bit-wise mask logic
210
specifies a set of bits, or “subfield”, from input data value ID[N-
1
:
0
] in response to a MASK signal received from software
250
. The MASK signal is initially selected to cause only the shortest subfield of bits ID[N-
1
:
0
] to be transmitted through mask logic
210
. This subfield of bits is transmitted to CAM array
220
as a key K, K#. CAM array
220
simultaneously compares key K, K# with all the stored words in its M rows of CAM cells, generating a match signal MS[M-
1
:
0
] made up of individual match signals MS
M-1
-MS
0
. If the applied data bit values specified by key K, K# match the corresponding stored data bit values in any row of CAM cells in CAM array
220
, the corresponding match signal is asserted TRUE.
If at least one of the match signals MS[M-
1
:
0
] is asserted TRUE, no-match decoder
230
provides a logic FALSE NO_MATCH signal to software
250
. In response, software
250
generates another MASK data word, which is selected to cause a wider subfield of bits ID[M-
1
:
0
] to be transmitted through mask logic
210
. Note that software
250
must wait for no match decoder
230
to generate the NO_MATCH signal before generating the next MASK data word. Consequently, mask logic
210
,
220
,
230
and
240
is very much under-utilized, and the resultant throughput is low.
To perform a longest match operation, bit-wise mask logic
210
provides wider and wider subfields of input data value ID[N-
1
:
0
] until no match is detected with any row of CAM array
220
. The subfields are widened by software
250
, which progressively increases the number of enabling bits in the MASK data word. When no match is detected, no-match decoder
230
asserts a logic TRUE NO_MATCH signal, which causes priority encoder
240
to provide an address M_ADDR of the last match indicated by CAM array
220
. If more than one match was indicated during the last pass, priority encoder
240
provides an address having the highest priority (e.g., the lowest address).
Although CAM system
200
is able to determine the longest match for a given input data value, the recursive comparison loops significantly increase the time required to perform the operation. In addition, the time required to obtain a result is non-deterministic (i.e., the result can be obtained after one recursive loop, two recursive loops, etc.). This can often have undesirable effects at the system level.
FIG. 3
shows a block diagram of another conventional CAM system
300
providing longest match capability. CAM system
300
includes mask logic blocks
310
a
,
310
b
,
310
c
, and
310
d
, an M×N
3
CAM array
320
, no-match decoders
330
a
,
330
b
,
330
c
, and
330
d
, first-level priority encoders
340
a
,
340
b
,
340
c
, and
340
d
, and second-level priority encoder
350
. Mask logic blocks
310
a
-
310
d
receive an N-bit input data value ID[N-
1
:
0
] and specify keys Ka-Kd, respectively.
Keys Ka-Kd represent successively wider subsections of input data value ID[N-
1
:
0
], starting from either its LSB or MSB. Keys Ka, Kb, Kc, and Kd have widths A, B, C, and D, respectively, where
0
<A<B<C<D≦N. Each key is compared to all of the words stored in CAM array
320
. In response, CAM array
320
generates a set of match signals for each key. For example, CAM array
320
generates a first set of match signals MSa[M-
1
:
0
] in response to key Ka, and a second set of match signals MSb[M-
1
:
0
] in response to key Kb. Each set of match signals is provided to a corresponding first-level priority encoder and a corresponding no-match detector. For example, the first set of match signa

Affiliated with

Also associated with

Rating

Content addressable memory with longest match detect 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 with longest match detect, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory with longest match detect will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2887539