Pre-computation based ternary content addressable memory
AssigneeBroadcom Corporation
InventorVinay Iyengar
Life of this patent
Estimating the term…
Abstract
A pre-computation based TCAM configured to reduce the number of match lines being pre-charged during a search operation to save power is disclosed. The pre-computation based TCAM stores additional information in a secondary TCAM that can be used to determine which match lines in a primary TCAM storing data words to be searched need not be pre-charged because they are associated with data words guaranteed to not match. The additional information stored in secondary TCAM can include a pre-computation word that represents a range inclusive of a lower and upper bound of a number of ones or zeroes possible in a corresponding data word stored in the primary TCAM.
Claims20
A pre-computation based ternary content addressable memory (TCAM), comprising:
- a primary TCAM comprising a match line associated with a data word in the primary TCAM;
- and
- a secondary TCAM comprising a match line associated with a pre-computation word in the secondary TCAM,
- wherein the pre-computation word represents a range inclusive of a lower bound of a number of ones or zeros possible in the data word and an upper bound of the number of ones or zeros possible in the data word, and
- wherein the match line associated with the pre-computation word in the secondary TCAM is configured to disable pre-charging of the match line associated with the data word in the primary TCAM.
A pre-computation based ternary content addressable memory (TCAM), comprising:
- a primary TCAM comprising a match line associated with a data word in the primary TCAM;
- and
- a secondary TCAM comprising a match line associated with a pre-computation word in the secondary TCAM,
- wherein the matchline associated with the pre-computation word in the secondary TCAM is configured to disable pre-charging of the match line associated with the data word in the primary TCAM based on a count of a number of ones or zeroes in only a portion of a search word used to search the primary TCAM.
A method for performing pre-computation in a ternary content addressable memory (TCAM), the method comprising:
- storing a data word in a primary TCAM;
- storing a pre-computation word in a secondary TCAM;
- and
- disabling pre-charging of a match line associated with the data word if a count of a number of ones or zeroes in at least a portion of a search word does not fall within a range represented by the pre-computation word.
Dependencies are inferred from the claim text.