Power savings in a content addressable memory device using masked pre-compare operations
AssigneeNetLogic Microsystems, Inc.
InventorDimitri Argyres
Life of this patent
Estimating the term…
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.
Claims32
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 (DMIN) and a maximum data population count (DMAX) for a corresponding ternary word stored in the array, wherein DMIN indicates how many bits of the ternary word are of a same predetermined logic value, and DMAX 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.
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 (DMIN) and a maximum data population count (DMAX) 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 DMIN and DMAX values from a corresponding row of the pre-compare memory, a second input to receive a minimum key population count (KMIN) and a maximum key population count (KMAX) associated with the search key, and a plurality of outputs each coupled to a corresponding row of the array.
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 (DMIN) and a maximum data population count (DMAX) for each ternary word;
- generating a key set including a minimum key population count (KMIN) and a maximum key population count (KMAX) for the search key;
- comparing values of DMIN and KMAX to generate a first result indicating whether KMAX≧DMIN;
- comparing values of DMAX and KMIN to generate a second result indicating whether DMAX≧KMIN, and
- selectively enabling rows of the CAM array in response to the first and second results.
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 (DMIN) and a maximum data population count (DMAX) for each ternary word;
- means for generating a key set including a minimum key population count (KMIN) and a maximum key population count (KMAX) for a search key;
- means for comparing values of DMIN and KMAX to generate a first result indicating whether KMAX≧DMIN;
- means for comparing values of DMAX and KMIN to generate a second result indicating whether DMAX≧KMIN;
- and
- means for selectively enabling rows of the CAM array in response to the first and second results.
Dependencies are inferred from the claim text.