Content addressable memory with block-programmable mask write mode, word width and priority

• US 20020129198A1
• Filed: 10/31/2001
• Published: 09/12/2002
• Est. Priority Date: 09/23/1999
• Status: Active Grant

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Nataraj, Bindiganavale S., Khanna, Sandeep, Srinivasan, Varadarajan, Gharia, Nilesh A., Pereira, Jose P., Wong, Hok F., Roy, Rupesh R.
• Granted Patent: US 6,944,709 B2
• Time in Patent Office: Days
• US Class Current: 711/108
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: G11C 15/04 using semiconductor elements
• CPC Class Codes: H03K 23/56 Reversible counters H03K23/52 and H03K23/548 take precedence
• CPC Class Codes: H03K 3/356139 with synchronous operation

Abstract

A content addressable memory (CAM) device comprising a plurality of CAM blocks and a block control circuit. The plurality of CAM blocks each includes an array of CAM cells to store data words and an array of priority number storage circuits to store priority numbers. Each priority number indicates a priority of a respective one of the data words relative to others of the data words. The block control circuit has an input to receive a class code and circuitry to output a plurality of select signals to the plurality of CAM blocks. Each select signal selectively disables a respective one of the plurality of CAM blocks from participating in a compare operation according to the class code.

Claims

1. A content addressable memory (CAM) device comprising:

a plurality of CAM blocks, each CAM block having an array of CAM cells to store data words and an array of priority number storage circuits to store priority numbers, each priority number indicating a priority of a respective one of the data words relative to others of the data words; and

a block control circuit having an input to receive a class code and circuitry to output a plurality of select signals to the plurality of CAM blocks, each select signal to selectively disable a respective one of the plurality of CAM blocks from participating in a compare operation according to the class code.

2. The CAM device of claim 1 wherein the circuitry to output a plurality of select signals to the plurality of CAM blocks includes a plurality of compare circuits, each compare circuit being adapted to compare the class code to a respective stored code that corresponds to one of the plurality of CAM blocks and to output a respective one of the plurality of select signals in either a first state or a second state according to whether the class code matches the stored code.

3. The CAM device of claim 1 wherein the block control circuit comprises a plurality of block configuration registers to store respective block configuration values, each block configuration value corresponding to a respective one of the CAM blocks and indicating the number of constituent bits of the data words stored within the corresponding CAM block.

4. The CAM device of claim 3 wherein each block configuration value further indicates the number of constituent bits of the priority numbers stored within the corresponding CAM block.

5. The CAM device of claim 4 wherein each block configuration value includes a mode value, and wherein each CAM block includes a circuit to generate, during a priority number write operation, a mask value for storage in the array of CAM cells of the CAM block if the mode value indicates a first mode.

6. The CAM device of claim 5 wherein the circuit to generate the mask value is a decoder circuit to decode a priority number into the mask value, the mask value having more constituent bits than the priority number.

7. The CAM device of claim 4 wherein each block configuration register includes a storage circuit to store a mode value, and wherein each CAM block includes a write circuit to generate, during a mask word write operation, a priority number for storage in the array of priority number storage circuits of the CAM block if the mode value indicates a first mode.

8. The CAM device of claim 7 wherein the write circuit to generate the priority number is an encoder circuit to encode a mask value to generate the priority number, the priority number having fewer constituent bits than the mask value.

9. The CAM device of claim 4 wherein each block configuration value includes a mode value that is indicative of a class of data to be stored within the corresponding CAM block.

10. The CAM device of claim 4 wherein each block configuration value includes a mode value that indicates whether internet protocol (IP) prefixes or policy statements are to be stored within the corresponding CAM block.

11. The CAM device of claim 1 wherein the array of CAM cells within at least one of the CAM blocks comprises ternary CAM cells.

12. The CAM device of claim 1 wherein the block control circuit is adapted to selectively disable the one of the plurality of CAM blocks from participating in the compare operation by preventing a comparand value from being input to the one of the plurality of CAM blocks.

13. The CAM device of claim 1 wherein each CAM block further includes a block match circuit to generate a block match flag signal if the CAM block is not disabled from participating in the compare operation and if at least one data word stored within the array of CAM cells of the CAM block is determined to match a comparand value.

14. The CAM device of claim 13 wherein the block control circuit comprises a plurality of block configuration registers to store respective block configuration values, each block configuration value corresponding to a respective one of the CAM blocks and indicating the number of constituent bits of the data words stored within the corresponding CAM block, and wherein within each of the CAM blocks, the array of CAM cells is coupled to the array of priority number storage circuits via a first plurality of match lines, and the array of priority number storage circuits is coupled to the block match circuit via a second plurality of match lines, the block match circuit including circuitry to generate a plurality of configuration-dependent match flag signals according to match signals asserted on the second plurality of match lines, the block match circuit further including circuitry to select, in accordance with the block configuration value for the corresponding CAM block, one the plurality of configuration-dependent match flag signals to be output from the CAM block as the block match flag signal.

15. The CAM device of claim 1 wherein each CAM block further includes a block multiple match circuit to generate a block match signal if the CAM block is not disabled from participating in the compare operation and if at least two data words stored within the array of CAM cells of the CAM block are determined to match a comparand value.

16. The CAM device of claim 1 further comprising a priority encoder circuit to generate an index indicative of a storage location within one of the plurality of CAM blocks not disabled from participating in the compare operation.

18. The method of claim 17 further comprising receiving an instruction that includes the class code.

19. The method of claim 17 wherein selecting a subset of the CAM blocks according to the class code comprises:

comparing the class code to a plurality of configuration values, each configuration value corresponding to a respective one of the plurality of CAM blocks; and

selecting each of the plurality of CAM blocks for which the corresponding configuration value matches the class code.

20. The method of claim 19 wherein selecting each of the plurality of CAM blocks for which the corresponding configuration value matches the class code comprises outputting a respective block select signal to each of the plurality of CAM blocks for which the corresponding configuration value matches the class code.

21. The method of claim 19 further comprising storing the plurality of configuration values within respective configuration storage circuits within the CAM device.

22. The method of claim 21 wherein each of the plurality of configuration values indicates a width, in bits, of data words stored in the corresponding CAM block.

23. The method of claim 19 further comprising:

receiving an instruction to store a priority number within one of the plurality of CAM blocks;

decoding the priority number to generate a mask word if a mode value within the configuration value that corresponds to the one of the plurality of CAM blocks indicates a first operating mode;

storing the priority number in an array of priority number storage circuits within the one of the CAM blocks; and

storing the mask word in an array of CAM cells within the one of the CAM blocks.

24. The method of claim 19 further comprising:

receiving an instruction to store a mask word within one of the plurality of CAM blocks;

encoding the mask word to generate a priority number if a mode value within the configuration value that corresponds to the one of the plurality of CAM blocks indicates a first operating mode;

storing the priority number in an array of priority number storage circuits within the one of the CAM blocks; and

storing the mask word in an array of CAM cells within the one of the CAM blocks.

25. The method of claim 17 wherein comparing a comparand value to data words stored in the selected subset of CAM blocks to identify matching data words comprises generating a plurality of match signals to identify the matching data words.

26. The method of claim 17 wherein generating an index according to priority values associated with the matching data words comprises:

comparing the priority values to one another to determine a highest priority value of the priority values; and

generating an index that corresponds to a storage location of the highest priority value.

27. The method of claim 26 wherein comparing the priority values to one another comprises:

comparing a first subset of the priority values with one another within a first one of the selected CAM blocks to determine a first block priority value;

comparing a second subset of the priority values with one another within a second one of the selected CAM blocks to determine a second block priority value; and

comparing the first block priority value and the second block priority value to determine the highest priority value.

29. The CAM device of claim 28 further comprising means for receiving an instruction that includes the class code.

30. The CAM device of claim 28 wherein the means for selecting the subset of CAM blocks comprises:

means for comparing the class code to a plurality of configuration values, each configuration value corresponding to a respective one of the plurality of CAM blocks; and

means for selecting each of the plurality of CAM blocks for which the corresponding configuration value matches the class code.

31. The CAM device of claim 30 wherein the means for selecting each of the plurality of CAM blocks for which the corresponding configuration value matches the class code comprises means for outputting a respective block select signal to each of the plurality of CAM blocks for which the corresponding configuration value matches the class code.

32. The CAM device of claim 30 further comprising means for storing the plurality of configuration values within respective configuration storage circuits within the CAM device.

33. The CAM device of claim 28 wherein the means for generating an index according to priority values associated with the matching data words comprises:

means for comparing the priority values to one another to determine a highest priority value of the priority values; and

means for generating an index that corresponds to a storage location of the highest priority value.

34. The CAM device of claim 33 wherein the means for comparing the priority values to one another comprises:

means for comparing a first subset of the priority values with one another within a first one of the selected CAM blocks to determine a first block priority value;

means for comparing a second subset of the priority values with one another within a second one of the selected CAM blocks to determine a second block priority value; and

means for comparing the first block priority value and the second block priority value to determine the highest priority value.

36. The system of claim 35 wherein the processor is programmed to output the class code to the CAM device.

37. The system of claim 35 wherein the processor is programmed to output a compare instruction to the CAM device, the compare instruction including the class code.

38. The system of claim 37 wherein the class code is included in an operand portion of the instruction.

39. The system of claim 37 wherein the class code is included in an operation code portion of the instruction.

17. A method of operation within a content addressable memory (CAM) device that includes a plurality of CAM blocks, the method comprising:

selecting a subset of the CAM blocks according to a class code;

comparing a comparand value to data words stored in the selected subset of CAM blocks to identify matching data words; and

generating an index according to priority values stored in the selected subset of CAM blocks and associated with the matching data words.

28. A content addressable memory (CAM) device comprising:

a plurality of CAM blocks; and

means for selecting a subset of the CAM blocks according to a class code, wherein each CAM block includes means for comparing a comparand value to data words stored in the CAM block to identify matching data words and means for generating an index according to priority values stored in the CAM block and associated with the matching data words.

35. A system comprising:

a processor; and

a CAM device coupled to the processor, the CAM device including;

a plurality of CAM blocks, each CAM block having an array of CAM cells to store data words and an array of priority number storage circuits to store priority numbers, each priority number indicating a priority of a respective one of the data words relative to others of the data words; and

a block control circuit having an input to receive a class code and circuitry to output a plurality of select signals to the plurality of CAM blocks, each select signal to selectively disable a respective one of the plurality of CAM blocks from participating in a compare operation according to the class code.