Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-12-08
2002-12-03
Ellis, Kevin L. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
Reexamination Certificate
active
06490650
ABSTRACT:
BACKGROUND
1. Field of Invention
This invention relates generally to content addressable memories and specifically to generating a device index in a content addressable memory.
2. Description of Related Art
A content addressable memory (CAM) is a storage device that can be instructed to retrieve information based upon a comparison of a comparand word with data words stored in the CAM.
FIG. 1
shows a CAM device
100
having an array of memory cells
102
and an associated priority logic circuit
104
. The CAM array
102
includes k rows of memory cells. Each row of memory cells stores a CAM word, and is connected to the logic
104
via a corresponding match line ML. The priority logic circuit
104
includes well-known match logic, multiple match logic, and a priority encoder. During compare operations, the comparand word is received at appropriate input terminals of the CAM device
100
and then compared with the CAM words stored in the CAM array
102
. For each CAM word that matches the comparand word, its corresponding match line ML is asserted to indicate the match condition.
In response to the asserted match line ML, the priority logic circuit
104
asserts a match flag MF, and outputs the index of the matching CAM word. If there are multiple matches, the priority logic circuit
104
asserts a multiple match flag MMF, and selects one of the matching CAM words to be output from the CAM device
100
. When there are multiple matches, priority logic circuit
104
selects the highest priority match, which is typically defined as the matching CAM word that has the lowest CAM index, although other priority schemes may be used. The index of the highest priority match, the contents of the matched location, and other status information (e.g., skip bit, empty bit, and full flag, as well as the match and multiple match flags) may be output from the CAM device
100
to an output bus (not shown in FIG.
1
).
FIG. 2
shows a conventional architecture
200
of the priority logic circuit
104
. The priority logic circuit
200
includes n well-known match and priority encoding logic (MPL) circuits
202
(
1
)-
202
(n), a control circuit
204
, a multiplexer (MUX)
206
, and a concatenation node
208
. Each MPL circuit
202
(
1
)-
202
(n) receives a corresponding set of match lines ML_
1
to ML_n, respectively, where each match line set ML_
1
to ML_n includes x match lines from the CAM array
102
(see also FIG.
1
). In response to its corresponding set of match lines ML, each MPL circuit
202
(l)-
202
(n) provides a respective match flag MF_
1
to MF_n to the control circuit
204
via corresponding signal lines
208
(
1
)-
208
(n). Also, although not shown in
FIG. 2
for simplicity, each MPL circuit
202
(
1
)-
202
(n) may provide a multiple match flag MMF to the control circuit
204
.
If there is a match condition within its corresponding match line set ML, each MPL circuit
202
(
1
)-
202
(n) provides the highest priority matching index I_
1
to I_n, respectively, to the MUX
206
via corresponding index buses
210
(
1
)-
210
(n). Each index I_
1
to I_n, and thus each index bus
210
(
1
)-
210
(n), is y=log
2
x bits wide. Using the match flags MF_
1
to MF_n, the control circuit
204
identifies the highest priority MPL circuit
202
(
1
)-
202
(n) that detects a match condition and, in response thereto, provides a select signal to the MUX
206
to select the index I from that MPL circuit
202
to provide as an input signal to the concatenation node
208
. The control circuit
204
also generates an m-bit set ID that identifies the index of the highest priority match line set that has a match condition. The set ID is provided to the concatenation node
208
, and concatenated therein as the most significant bits (MSB's) to the index I received from the MUX
206
to form a z-bit device index I_dev, where z=y+m. The device index is the index or address of the highest priority match in the entire CAM array.
The priority logic circuit
200
of
FIG. 2
requires a significant number of signal lines to carry each of the indexes I_
1
to I_n from respective MPL circuits
202
(
1
)-
202
(n) to the MUX
206
. Because of the
2
dimensional spacial relationship between the MPL circuits
202
and the MUX
206
, the index buses
210
from the MPL circuits
202
located farthest from the MUX
206
(e.g., MPL circuit
202
(
1
), then MPL circuit
202
(
2
), and so on), are quite long and occupy significant silicon area. For example, as illustrated in
FIG. 2
, the index buses
210
(
1
)-
210
(n) each run in both the horizontal and vertical directions, where each index bus
210
(
1
)-
210
(n) is routed past all subsequent MPL circuits
202
to reach the MUX
206
. As the size of CAM devices increases, the number and length of the index buses
210
increases, thereby consuming even greater silicon area. Accordingly, it would be desirable to reduce the amount of silicon area occupied by the index buses
210
.
SUMMARY
A method and apparatus are disclosed that generate a device index in a CAM device. In accordance with the present invention, the match lines of a CAM array are grouped into a plurality of sets. The match lines within each set are provided to a corresponding match and priority encoding logic (MPL) circuit. Each MPL circuit includes an input index terminal connected to an index output terminal of a previous MPL circuit, and includes an index output terminal connected to the index input terminal of a next MPL circuit. In response to match signals provided by its corresponding match line set, each MPL circuit generates a match flag, a multiple match flag, and the index of the highest priority match for the set. The match flags and multiple match flags from each MPL circuit are provided to a control circuit. The last MPL circuit has an index output terminal connected to an index input terminal of the control circuit.
In response to the match flags, the control circuit generates a plurality of select signals, each of which is provided to a corresponding MPL circuit. In response to its corresponding select signal, each MPL circuit selectively provides either the set index generated therein or a input set index received from the previous MPL circuit to the next MPL circuit. The control circuit asserts the select signals in a manner such that the index from the highest priority match line set ripples through one or more of the MPL circuits to the control circuit. The control circuit also generates a set ID that identifies the highest priority matching set. The set ID is concatenated as the most significant bit(s) to the selected set index to form the device index.
By rippling the highest priority set index through the MPL circuits to the control circuit, present embodiments may significantly reduce the length of the index buses. Thus, rather than routing an index bus from each MPL circuit to the control circuit, present embodiments route index buses between adjacent MPL circuits. The reduction in index signal lines and signal line lengths achieved by present embodiments may advantageously reduce the silicon area occupied thereby.
In some embodiments, a hierarchical scheme may be used.
REFERENCES:
patent: 5852569 (1998-12-01), Srinivasan et al.
patent: 5930359 (1999-07-01), Kempke et al.
patent: 6000008 (1999-12-01), Simcoe
patent: 6253280 (2001-06-01), Voelkel
patent: 6381673 (2002-04-01), Srinivasan et al.
Ellis Kevin L.
NetLogic Microsystems, Inc.
Paradice III William L.
LandOfFree
Method and apparatus for generating a device index in a... 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 apparatus for generating a device index in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating a device index in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2964247