US6708250B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Circuit and method for performing variable width searches in a content addressable memory
Assignee: Nvidia Corp
•
Filing: 2001-11-30
•
Granted: 2004-03-16
•
Expires: 2021-11-30
Abstract
Abstract A content addressable memory (CAM) for generating intermediate search results in a search on a stored data word sequence. The CAM comprises a plurality of rows of CAM cells each for storing a data word in the data word sequence; a plurality of match lines each coupled to a corresponding row of CAM cells, each for generating a corresponding match line signal. A priority encoder is coupled to the match line for generating a match address in response to a match line signal; and a plurality of logic circuits, each coupled to corresponding match lines for selectively coupling the match line signal to the priority encoder in response to an instruction signal, the instruction signal for instructing the CAM to generate a match address output on a new search or on a continuation of a previous search, such that portions of the data word sequence occurring at any intermediate location within the sequence provides match results in response to input search data which are equivalent to portions of the stored data word sequence.
Inventors
- 👤 Peter Gillingham
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 11:58
CPC Classifications
G; G11; G11C; G11C15/00; G11C15/04
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
201 words
A content addressable memory (CAM) for generating intermediate search results in a search on a stored data word sequence, the CAM comprising: (a) a plurality of rows of CAM cells each for storing a data word in said data ward sequence; (b) a plurality of match lines each coupled to a corresponding row of CAM cells, each match line having a predetermined priority and for generating a corresponding match line signal; (c) a priority encoder coupled to said match lines for generating a match address in response to a match line signal; and (d) a plurality of logic circuits, each coupled between corresponding match lines and said priority encoder for selectively coupling its corresponding match line signal or a match line signal from a lower priority match line to said priority encoder in response to an instruction signal, said instruction signal for instructing the CAM to generate a match address output on a new search or on a continuation of a previous search, such that portions of the data word sequence occurring at any intermediate location within the data word sequence provides match results in response to input search data which are equivalent to portions of the stored data word sequence.
Claim 2
Dependent Claim
201 words
A content addressable memory (CAM) for generating intermediate search results in a search on a stored data word sequence, the CAM comprising: (a) a plurality of rows of CAM cells each for storing a data word in said data ward sequence; (b) a plurality of match lines each coupled to a corresponding row of CAM cells, each match line having a predetermined priority and for generating a corresponding match line signal; (c) a priority encoder coupled to said match lines for generating a match address in response to a match line signal; and (d) a plurality of logic circuits, each coupled between corresponding match lines and said priority encoder for selectively coupling its corresponding match line signal or a match line signal from a lower priority match line to said priority encoder in response to an instruction signal, said instruction signal for instructing the CAM to generate a match address output on a new search or on a continuation of a previous search, such that portions of the data word sequence occurring at any intermediate location within the data word sequence provides match results in response to input search data which are equivalent to portions of the stored data word sequence.
Claim 3
Dependent Claim
30 words
A CAM as defined in claim 1 , including a match latch coupled to each match lines for latching its corresponding match line signal, in response to a clock signal.
Claim 4
Dependent Claim
65 words
A CAM as defined in claim 2 , for each match line said logic circuit logically combining its match line signal from a previous match. line to output a signal to said match latch, such that in a continued search the match latch latches a match only if the current search word matches and the previous match latch latched a match in the previous search.
Claim 5
Independent Claim
217 words
A method for operating a content addressable memory (CAM) having a CAM array comprising a plurality of CAM rows of a first width, each CAM row comprising a plurality of storage cells and at least a match line, the method comprising the steps of: (a) providing a data word of a second width; (b) dividing the data word into a plurality of data word portions of the first width for storing into the plurality of CAM rows; (c) providing a search word of a width wider than the first width; (d) dividing the search word in a plurality of partial search words of the first width; (e) comparing in a first search cycle a partial search word with the data word portions stored in the CAM array and issuing a match signal through the match line to a priority encoder indicating a first address if the search and data words are the same; and (f) comparing in a subsequent search cycle a subsequent partial search word with the data word portions stored in the CAM array and issuing a match signal through the match line to the priority encoder indicating a subsequent address if the search and data words are the same and the result of the previous row in the first search cycle was a match.
Claim 6
Independent Claim
217 words
A method for operating a content addressable memory (CAM) having a CAM array comprising a plurality of CAM rows of a first width, each CAM row comprising a plurality of storage cells and at least a match line, the method comprising the steps of: (a) providing a data word of a second width; (b) dividing the data word into a plurality of data word portions of the first width for storing into the plurality of CAM rows; (c) providing a search word of a width wider than the first width; (d) dividing the search word in a plurality of partial search words of the first width; (e) comparing in a first search cycle a partial search word with the data word portions stored in the CAM array and issuing a match signal through the match line to a priority encoder indicating a first address if the search and data words are the same; and (f) comparing in a subsequent search cycle a subsequent partial search word with the data word portions stored in the CAM array and issuing a match signal through the match line to the priority encoder indicating a subsequent address if the search and data words are the same and the result of the previous row in the first search cycle was a match.
Claim 7
Dependent Claim
14 words
A method according to claim 4 , wherein the first width represent 72 bits.
Claim 8
Dependent Claim
21 words
A method according to claim 4 , including providing an instruction signal indicating if the subsequent search is a continuation search.
Claim 9
Dependent Claim
43 words
A method according to claim 4 ,including storing “don't care” data to the empty CAM cells of the row where the last portion of the data word is stored, if the last portion of the data word is narrower than the first width.
Claim 10
Dependent Claim
29 words
A method according to claim 4 , said priority encoder providing the address of the most subsequent search word and data word portions match as the highest priority match.
Claim 11
Dependent Claim
36 words
A method according to claim 4 , including latching the result of the first search cycle in a latch and combining the latched result with the result of the subsequent search in the subsequent search cycle.
Claim 12
Independent Claim
215 words
A method for operating a content addressable memory (CAM) having a CAM may comprising a plurality of CAM rows of a first width, each CAM row comprising a plurality of storage cells and at least a match line, the method comprising the steps of: (a) providing a data word of a second width; (b) dividing the data word into a plurality of data word portions of the first width for storing into the plurality of CAM rows; (c) providing a search word of a width wider than the first width; (d) dividing the search word in a plurality of partial search words of the first width; (e) comparing in a first search cycle a partial search word with the data word portions stored in the CAM array and issuing a match signal through the match line to a priority encoder indicating a first address if the search and data words are the same; and (f) comparing in a subsequent search cycle a subsequent partial search word with the data word portions stored in the CAM array and issuing a match signal through the match line to the priority encoder indicating a subsequent address if the search and data words are the same and an instruction signal indicates that the subsequent search is a new search.
Claim 13
Independent Claim
215 words
A method for operating a content addressable memory (CAM) having a CAM may comprising a plurality of CAM rows of a first width, each CAM row comprising a plurality of storage cells and at least a match line, the method comprising the steps of: (a) providing a data word of a second width; (b) dividing the data word into a plurality of data word portions of the first width for storing into the plurality of CAM rows; (c) providing a search word of a width wider than the first width; (d) dividing the search word in a plurality of partial search words of the first width; (e) comparing in a first search cycle a partial search word with the data word portions stored in the CAM array and issuing a match signal through the match line to a priority encoder indicating a first address if the search and data words are the same; and (f) comparing in a subsequent search cycle a subsequent partial search word with the data word portions stored in the CAM array and issuing a match signal through the match line to the priority encoder indicating a subsequent address if the search and data words are the same and an instruction signal indicates that the subsequent search is a new search.
References Cited (Backward Citations)
US3984821A
Cited
US4366551A
Cited
US4296475A
Cited
US4254476A
Cited
US4831586A
Cited
US6253280B1
Cited
CA2317387A1
Cited
US6252789B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-03-16 | 2007-09-15 | 2008-03-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-03-16 | 2011-09-15 | 2012-03-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-03-16 | 2015-09-15 | 2016-03-16 | $7700.00 | Window Closed / Lapsed |