Power savings in a content addressable memory device using masked pre-compare operations

Abstract

A CAM device for comparing a search key with a plurality of ternary words stored in a CAM array includes one or more population counters, a pre-compare memory, and a pre-compare circuit. The present embodiments reduce the power consumption of CAM devices during compare operations between a search key and ternary words stored in a CAM array by selectively enabling the match lines in the CAM array in response to pre-compare operations between a set of population counts corresponding to the masked search key and a set of population counts corresponding to the ternary words stored in the CAM array.

What is claimed is: 
     
       1. A content addressable memory (CAM) device for comparing a search key with a plurality of ternary words, comprising:
 an array having a plurality of rows of CAM cells and a respective row to store an associated ternary word, wherein each respective row is coupled to a corresponding match line, and wherein the associated ternary word embodies a binary data word masked by a local mask word; and 
 a pre-compare memory having a plurality of rows of memory cells and a respective row to store a minimum data population count (D MIN ) and a maximum data population count (D MAX ) for a corresponding ternary word stored in the array, wherein D MIN  indicates how many bits of the ternary word are of a same predetermined logic value, and D MAX  indicates how many bits of the ternary word are of the same predetermined logic value plus how many bits of the ternary word have a don't-care value. 
 
     
     
       2. The CAM device of  claim 1 , further comprising:
 a first population counter to generate corresponding sets of D MIN  and D MAX . 
 
     
     
       3. The CAM device of  claim 2 , wherein the first population counter is configured to generate D MIN  by counting how many logic ones are in the ternary word, and to generate D MAX  by counting how many logic ones are in the ternary word plus how many logic ones are in the local mask word. 
     
     
       4. The CAM device of  claim 2 , wherein the first population counter is configured to generate D MIN  by counting how many logic zeros are in the ternary word, and to generate D MAX  by counting how many logic zeros are in the ternary word plus how many logic ones are in the local mask word. 
     
     
       5. The CAM device of  claim 2 , further comprising:
 a block mask register coupled to the array and configured to store a block mask; and 
 a second population counter to generate a minimum key population count (K MIN ) and a maximum key population count (K MAX ) for a masked search key formed by the search key and the block mask. 
 
     
     
       6. The CAM device of  claim 5 , wherein the first population counter and the second population counter share the same circuit. 
     
     
       7. The CAM device of  claim 5 , wherein K MIN  indicates how many bits of the masked search key are of the same predetermined logic value, and K MAX  indicates how many bits of the masked search key are of the same predetermined logic value plus how many bits of the masked search key have a don't-care value. 
     
     
       8. The CAM device of  claim 7 , wherein the second population counter is configured to generate K MIN  by counting how many logic ones are in the masked search key, and to generate K MAX  by counting how many logic ones are in the masked search key plus how many logic ones are in the block mask. 
     
     
       9. The CAM device of  claim 7 , wherein the second population counter is configured to generate K MIN  by counting how many logic zeros are in the masked search key, and to generate K MAX  by counting how many logic zeros are in the masked search key plus how many logic ones are in the block mask. 
     
     
       10. The CAM device of  claim 5 , further comprising:
 a pre-compare circuit having a plurality of first inputs each for receiving a pair of D MIN  and D MAX  values from a corresponding row of the pre-compare memory, a second input to receive K MIN  and K MAX , and a plurality of outputs each coupled to a corresponding row of the array. 
 
     
     
       11. The CAM device of  claim 10 , wherein the pre-compare circuit is configured to selectively enable a respective row of the array for a compare operation with the search key in response to a comparison between D MIN  and K MAX  and a comparison between D MAX  and K MIN . 
     
     
       12. The CAM device of  claim 11 , wherein the pre-compare circuit is configured to assert an enable signal to enable the respective row if K MAX ≧D MIN  and D MAX ≧K MIN . 
     
     
       13. The CAM device of  claim 12 , further comprising match-line control circuitry to pre-charge the match line of the respective row in response to the asserted state of the enable signal. 
     
     
       14. The CAM device of  claim 11 , wherein the pre-compare circuit is configured to de-assert an enable signal to disable the respective row if either K MAX <D MIN  or D MAX <K MIN . 
     
     
       15. The CAM device of  claim 10 , where the pre-compare circuit includes a plurality of segments, each comprising:
 a first comparator having inputs to receive K MAX  and D MIN , and having an output; 
 a second comparator having inputs to receive D MAX  and K MIN , and having an output; and 
 a logic gate having inputs coupled to the outputs of the first and second comparators, and having an output to generate an enable signal that selectively pre-charges the match line of a corresponding row of the array. 
 
     
     
       16. A content addressable memory (CAM) device for comparing a search key with a plurality of ternary words, comprising:
 an array having a plurality of rows of CAM cells, a respective row to store an associated ternary word and being coupled to a corresponding match line, wherein the associated ternary word embodies a binary data word and a local mask word; 
 a pre-compare memory having a plurality of rows of memory cells, a respective row to store a minimum data population count (D MIN ) and a maximum data population count (D MAX ) for a corresponding ternary word stored in the array; and 
 a pre-compare circuit having a plurality of first inputs each for receiving a pair of D MIN  and D MAX  values from a corresponding row of the pre-compare memory, a second input to receive a minimum key population count (K MIN ) and a maximum key population count (K MAX ) associated with the search key, and a plurality of outputs each coupled to a corresponding row of the array. 
 
     
     
       17. The CAM device of  claim 16 , wherein D MIN  indicates how many bits of the ternary word are of a same predetermined logic value, and D MAX  indicates how many bits of the ternary word are of the same predetermined logic value plus how many bits of the ternary word have a don't-care value. 
     
     
       18. The CAM device of  claim 17 , further comprising:
 a first population counter to generate corresponding sets of D MIN  and D MAX . 
 
     
     
       19. The CAM device of  claim 18 , wherein the first population counter is configured to generate D MIN  by counting how many logic ones are in the ternary word, and to generate D MAX  by counting how many logic ones are in the ternary word plus how many logic ones are in the local mask word. 
     
     
       20. The CAM device of  claim 16 , wherein K MIN  indicates how many bits of a masked search key are of the same predetermined logic value, and K MAX  indicates how many bits of the masked search key are of the same predetermined logic value plus how many bits of the masked search key have a don't-care value. 
     
     
       21. The CAM device of  claim 18 , further comprising:
 a block mask register coupled to the array and configured to store a block mask; and 
 a second population counter to generate K MIN  and K MAX . 
 
     
     
       22. The CAM device of  claim 21 , wherein the second population counter is configured to generate K MIN  by counting how many logic ones are in the masked search key, and to generate K MAX  by counting how many logic ones are in the masked search key plus how many logic ones are in the block mask. 
     
     
       23. The CAM device of  claim 16 , wherein the pre-compare circuit is configured to selectively enable a respective row of the TCAM array for a compare operation with the search key in response to a comparison between D MIN  and K MAX  and a comparison between D MAX  and K MIN . 
     
     
       24. The CAM device of  claim 23 , wherein the pre-compare circuit is configured to assert an enable signal if K MAX ≧D MIN  and D MAX ≧K MIN . 
     
     
       25. The CAM device of  claim 23 , wherein the pre-compare circuit is configured to de-assert an enable signal if either K MAX <D MIN  or D MAX <K MIN . 
     
     
       26. A method of comparing a search key with a plurality of ternary words stored in corresponding rows of a content addressable memory (CAM) array, wherein each ternary word embodies a data word and a local mask word, the method comprising:
 generating a data set including a minimum data population count (D MIN ) and a maximum data population count (D MAX ) for each ternary word; 
 generating a key set including a minimum key population count (K MIN ) and a maximum key population count (K MAX ) for the search key; 
 comparing values of D MIN  and K MAX  to generate a first result indicating whether K MAX ≧D MIN ; 
 comparing values of D MAX  and K MIN  to generate a second result indicating whether D MAX ≧K MIN , and 
 selectively enabling rows of the CAM array in response to the first and second results. 
 
     
     
       27. The method of  claim 26 , wherein D MIN  indicates how many bits of the ternary word are of a same predetermined logic value, and D MAX  indicates how many bits of the ternary word are of the same predetermined logic value plus how many bits of the ternary word have a don't-care value. 
     
     
       28. The method of  claim 27 , wherein a first population counter generates D MIN  by counting how many logic ones are in the ternary word, and generates D MAX  by counting how many logic ones are in the ternary word plus how many logic ones are in the local mask word. 
     
     
       29. The method of  claim 26 , wherein K MIN  indicates how many bits of a masked search key corresponding to the search key and an associated block mask are of the same predetermined logic value, and K MAX  indicates how many bits of the masked search key are of the same predetermined logic value plus how many bits of the masked search key have a don't-care value. 
     
     
       30. The method of  claim 29 , wherein the second population counter generates K MIN  by counting how many logic ones are in the masked search key, and generates K MAX  by counting how many logic ones are in the masked search key plus how many logic ones are in the block mask. 
     
     
       31. The method of  claim 26 , wherein the selectively enabling comprises:
 pre-charging a match line for a corresponding row only if K MAX ≧D MIN  and if D MAX ≧K MIN . 
 
     
     
       32. A content addressable memory (CAM) array having a plurality of rows of CAM cells, wherein each row stores a ternary word embodied by a data word and a local mask word, comprising:
 means for generating a data set including a minimum data population count (D MIN ) and a maximum data population count (D MAX ) for each ternary word; 
 means for generating a key set including a minimum key population count (K MIN ) and a maximum key population count (K MAX ) for a search key; 
 means for comparing values of D MIN  and K MAX  to generate a first result indicating whether K MAX ≧D MIN ; 
 means for comparing values of D MAX  and K MIN  to generate a second result indicating whether D MAX ≧K MIN ; and 
 means for selectively enabling rows of the CAM array in response to the first and second results.