Content addressable memory with programmable priority...

Details Content addressable memory with programmable priority... Content addressable memory with programmable priority...

2002-10-21

2003-06-10

Elms, Richard (Department: 2824)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S189070

Reexamination Certificate

active

06577520

ABSTRACT:

FIELD OF THE INVENTION
The present invention generally relates to content addressable memory and in particular, to a content addressable memory with programmable priority weighting and low cost match detection.
BACKGROUND OF THE INVENTION
Content addressable memory (CAM) is useful in various applications such as address translation in network routers.
FIG. 1
illustrates, as an example, a block diagram of a first prior art CAM arrangement including a CAM array
100
and a priority encoder
106
. The CAM array
100
in this example has 2
N
−1 CAM cells, such as CAM cells
101
~
105
. Each CAM cell includes a comparator and a register.
An input data word is provided to each CAM cell, and the CAM cell's comparator compares the input data word against the entry in its register. If they match, a match indication, such as a binary “1”, is placed on the CAM cell's output line, such as output line M
0
of CAM cell
101
. On the other hand, if they do not match, a no-match indication, such as a binary “0”, is placed on the output line.
The priority encoder
106
receives the match and no-match indications from the CAM array
100
, and provides an N-bit binary output and a “match detect” output. If only one match indication is received, the N-bit binary output indicates an address location of the CAM cell register containing the matching entry. If multiple match indications are received, the priority encoder
106
first determines a winning match by selecting, for example, the match indication that is provided on a CAM cell output line corresponding to a highest physical position connection. The N-bit binary output then indicates the address location of a CAM cell register containing the winning matching entry.
The “match detect” output of the priority encoder
106
indicates whether or not the CAM array
100
has detected a match (i.e., whether at least one match indication has been received from the CAM array
100
). If no match has been detected, then the N-bit binary output should be ignored. The “match detect” output may be generated at the output of OR logic by coupling all output lines M
0
~M
2
N
−1 (wherein the symbol “~” indicates the sequence of output lines from M
0
to M
2
N
−1) of the CAM array
100
to inputs of the OR logic.
There are at least two perceived problems with the first prior art CAM arrangement. One problem is the fixed nature of its priority encoder
106
when determining a winning match among multiple match indications from the CAM array
100
. In particular, it is advantageous in some applications to provide a capability to change the order of priority among the output lines of the CAM array
100
. Otherwise, each time an entry is added or deleted from the CAM array
100
, all of the entries would have to be rearranged again in proper priority order in the CAM array
100
. Another problem is that generation of the “match detect” output may be circuit intensive when the number of match output lines is large. For example, a CAM array with 64K match output lines may require OR logic with 64K inputs to generate the “match detect” output.
FIG. 2
illustrates, as an example, a block diagram of a second prior art CAM arrangement including a CAM array
100
, a weight array
200
and an encoder
206
. This approach provides some level of flexibility in prioritizing match indications provided by the CAM array
100
on its output lines M
0
~M
2
N
−1. The CAM array
100
is identical in construction and operation as that described in reference to
FIG. 1
, therefore, it is given the same reference number and its description is not repeated here.
The weight array
200
determines a winner among match indications received from the CAM array
100
according to their respectively assigned weights, such as
201
~
205
, that are stored in the weight array
200
. The winner is indicated, for example, by a binary “1” placed on one of the output lines W
0
~W
2
N
−1 of the weight array
200
, while non-winners are indicated by binary “0's” placed on all other of the output lines W
0
~W
2
N
−1.
The encoder
206
receives the winning and non-winning match information from the weight array
200
, and provides an N-bit binary output and a “match detect” output. As in the first prior art CAM arrangement, the N-bit binary output indicates an address location of the CAM cell register containing the winning matching entry, and the “match detect” output indicates whether or not the CAM array
100
has detected a match. If no match has been detected, then the N-bit binary output should be ignored. The “match detect” output in this case may be generated at the output of OR logic by coupling all output lines W
0
~W
2
N
−1 of the weight array
200
to inputs of the OR logic (i.e., if no winner is detected, then it is assumed that no match indications were received from the CAM array
100
).
Although it provides some capability to change the order of priority among the output lines M
0
~M
2
N
−1 of the CAM array
100
, the second prior art CAM arrangement still generates the “match detect” output in much the same circuit intensive way as the first prior art CAM arrangement.
OBJECTS AND SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to provide a content addressable memory with programmable priority weighting and low cost match detection.
Another object is to provide such a content addressable memory using minimal circuitry so as to minimize die size and therefore, cost of an integrated circuit device including such a content addressable memory.
These and additional objects are accomplished by the various aspects of the present invention, wherein briefly stated, one aspect is a content addressable memory comprising: a CAM array having a first plurality of addressable storage elements for storing a plurality of entries, comparison logic for comparing an input data word with individual of the plurality of entries, and a plurality of outputs providing match and no-match indications of the input data word with the plurality of entries; and a weight array coupled to the plurality of outputs of the CAM array for receiving the match and no-match indications, the weight array having a second plurality of addressable storage elements for storing weights respectively assigned to corresponding ones of the plurality of outputs of the CAM array and at least one storage element for storing a weight lower than the weights and assigned to a forced match indication, weight logic for determining a winner among the match indications and the forced match indication, and a plurality of outputs indicating the winner.
Another aspect is a method for determining whether a match has been detected by a content addressable memory, comprising: receiving match information from a content addressable memory for a plurality of lines assigned with weights; generating a forced match on a line assigned with a lowest weight; determining a winning match among the forced match and any matches indicated in the match information according to their respective weights; and determining whether a match has been detected by the content addressable memory from the success of the forced match being determined to be the winning match.
Another aspect is a weight array circuit employed to determine a winning match among indicated matches of a content addressable memory. A plurality of lines is individually coupled through a current limiting circuit to a high reference voltage at one end and open-ended at another end. A plurality of weight cells are organized in rows and columns, each column coupled to a corresponding one of the plurality of lines, and each row receiving a corresponding output of the content addressable memory to determine whether the corresponding output is a winning match. Individual of the plurality of weight cells include an addressable storage element for storing a weight value; a first NMOS transistor having a drain coupled to the corresponding one of the plurality of lines, and a gate coupled to the corresponding output of the

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3134961