Content addressable memory with configurable class-based storage partition

• US 20050063241A1
• Filed: 10/12/2004
• Published: 03/24/2005
• Est. Priority Date: 06/08/2000
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Jose P. Pereira, Varadarajan Srinivasan
• Inventors: Srinivasan, Varadarajan, Pereira, Jose P.
• Granted Patent: US 7,230,840 B2
• Time in Patent Office: Days
• US Class Current: 365/222
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• 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

Abstract

A content addressable memory (CAM) device having a plurality of CAM blocks and a block selection circuit. Each of the CAM blocks includes an array of CAM cells to store data words having a width determined according to a configuration value. The block selection circuit includes an input to receive a class code and circuitry to output a plurality of select signals to the plurality of CAM blocks. Each of the select signals selectively disables a respective one of the plurality of CAM blocks from participating in a compare operation according to whether the class code matches a class assignment of the CAM block.

Claims

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

a plurality of CAM blocks each having an array of CAM cells to store data words having a width determined according to a configuration value; and

a block select 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 2 wherein each of the plurality of CAM blocks for which the corresponding select signal is in a first state is disabled from participating in the compare operation.

4. The CAM device of claim 2 wherein the stored code is indicative of the configuration value.

5. The CAM device of claim 2 wherein each respective stored code is indicative of a class of data.

6. The CAM device of claim 2 wherein the stored code is stored in a memory within the block select circuit.

7. The CAM device of claim 6 wherein the memory is a block configuration register.

8. The CAM device of claim 2 further comprising a device configuration register to store the stored code.

9. The CAM device of claim 1 wherein the plurality of CAM blocks comprise binary CAM cells.

10. The CAM device of claim 1 wherein the plurality of CAM blocks comprise ternary CAM cells.

11. The CAM device of claim 1 further comprising a plurality of block match circuits, each block match circuit being coupled to a respective CAM block of the plurality of CAM blocks via a plurality of match signal lines and being adapted to generate a block match signal if the CAM block is not disabled from participating in the compare operation and if a match signal is asserted on at least one of the match signal lines during the compare operation.

12. The CAM device of claim 1 further comprising a plurality of block multiple match circuits, each block multiple match circuit being coupled to a respective CAM block of the plurality of CAM blocks via a plurality of match signal lines and being adapted to generate a block match signal if the CAM block is not disabled from participating in the compare operation and if a match signal is asserted on at least two of the match signal lines during the compare operation.

13. The CAM device of claim 1 wherein the block select 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.

14. The CAM device of claim 13 wherein the block select circuit includes circuitry to prevent the comparand value from being input to the one of the plurality of CAM blocks by setting a plurality of bits within the comparand value to a reset state.

15. The CAM device of claim 1 further comprising a plurality of block flag circuits, each block flag circuit being coupled to a corresponding one of the plurality of CAM blocks and being adapted to assert a match flag signal if any of a plurality of data words stored within the corresponding CAM block matches a comparand value, and wherein the block select circuit is adapted to selectively disable the one of the plurality of CAM blocks from participating in the compare operation by preventing the corresponding block flag circuit from asserting the match flag signal.

16. The CAM device of claim 1 wherein the circuitry to output a plurality of select signals to the plurality of CAM blocks comprises a plurality of sets of CAM cells, each set of CAM cells including memory elements to store a class value that corresponds to one of the plurality of CAM blocks and compare circuitry to compare the stored class value to the class code 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 class value.

17. The CAM device of claim 16 wherein each CAM cell in the plurality of sets of CAM cells is a ternary CAM cell capable of storing a mask state to enable the stored class value to match more than one class code.

18. 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.

19. A method of operation within a content addressable memory (CAM) device:

receiving a class code;

comparing the class code to each of a plurality of block configuration values, each block configuration value indicating a width and depth configuration of a corresponding one of a plurality of storage blocks within the CAM device; and

disabling each of the plurality of storage blocks for which the corresponding configuration value does not match the class code from participating in a compare operation.

20. The method of claim 19 further comprising storing the plurality of block configuration values within the CAM device.

21. The method of claim 20 further comprising storing the plurality of block configuration values within a configuration register of the CAM device.

22. The method of claim 20 further comprising storing the same block configuration value within the CAM device for more than one of the plurality of storage blocks.

23. The method of claim 19 wherein disabling each of the plurality of storage blocks for which the corresponding configuration value does not match the class code from participating in a compare operation comprises generating a plurality of select signals, each select signal being coupled to a respective one of the plurality of storage blocks, and each select signal being set to a first state to disable the respective one of the plurality of storage blocks from participating in the compare operation if the corresponding configuration value does not match the class code.

24. A method of controlling a content addressable memory (CAM) device, the method comprising:

assigning respective classification values to a plurality of storage blocks within the CAM device; and

outputting a compare instruction to the CAM device, the compare instruction including a class code to be compared with the classification values to select a subset of the plurality of storage blocks to participate in a compare operation.

25. The method of claim 24 wherein assigning respective classification values to the plurality of storage blocks comprises outputting an instruction to the CAM device to store the classification values within at least one storage register within the CAM device.

26. The method of claim 24 wherein assigning respective classification values to the plurality of storage blocks comprises storing, for each of the storage blocks, a value indicative of the size of a data word to be stored in the storage block.

27. The method of claim 24 wherein assigning respective classification values to the plurality of storage blocks comprises storing, for each of the storage blocks, a value indicative of a width and depth configuration of the storage block.

28. The method of claim 27 wherein the class code included with the compare instruction specifies a particular width and depth configuration.

29. The method of claim 24 wherein the class code is included within an operation code of the compare instruction.

30. The method of claim 24 wherein the class code forms at least a portion of an operand associated with the compare instruction.

31. A method of controlling a content addressable memory (CAM) device, the method comprising:

assigning respective classification values to a plurality of storage blocks within the CAM device;

outputting a class code to the CAM device; and

outputting a compare instruction to the CAM device, the compare instruction indicating that a comparand is to be compared with data words stored within each of the plurality of storage blocks for which the assigned classification value matches the class code.

32. The method of claim 31 wherein assigning respective classification values to the plurality of storage blocks comprises storing, for each of the storage blocks, a value indicative of a width and depth configuration of the storage block.

33. The method of claim 32 wherein outputting a class code comprises outputting a class code that specifies a particular width and depth configuration.

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

a plurality of CAM blocks each having an array of CAM cells; and

an address circuit coupled to the plurality of CAM blocks and including a plurality of storage elements to store respective addresses, each of the plurality of storage elements corresponding to a respective one of a plurality of class-based storage partitions within the CAM device, each class-based storage partition including at least one of the plurality of CAM blocks, the address circuit including selection circuitry to select, according to a class code value, one of the plurality of storage elements to supply an address to access the corresponding class-based storage partition.

35. The CAM device of claim 34 wherein the CAM device includes circuitry to store a plurality of configuration values, each configuration value corresponding to a respective CAM block of the plurality of CAM blocks and indicating one of the class-based storage partitions that includes the CAM block.

36. The CAM device of claim 35 wherein each configuration value is indicative of a width and depth configuration of the corresponding CAM block, and wherein each set of one or more CAM blocks that have the same width and depth configuration form a respective one of the class-based storage partitions.

37. The CAM device of claim 34 wherein each of the plurality of storage elements is adapted to indicate a storage location within the corresponding class-based storage partition that contains a data word which, at least in part, matched a comparand in a compare operation.

38. The CAM device of claim 34 further comprising:

a select circuit to select, according to a class code, one of the class-based storage partitions to participate in a compare operation;

a priority encoder to generate an index indicative of a storage location within the selected one of the class-based storage partitions that contains a data word which is determined, in the compare-operation, to match a comparand; and

a load control circuit to load the index into one storage element of the plurality of storage elements that corresponds to the selected one of the class-based storage partitions.

39. The CAM device of claim 38 further comprising a flag circuit to assert a flag signal if the comparand is determined to match a data word stored within the selected one of the class-based storage partitions, the load control circuit being adapted to load the index into the one storage element if the flag signal is asserted by the flag circuit.

40. The CAM device of claim 34 wherein each of the plurality of storage elements is adapted to store an address of a storage location within the corresponding class-based storage partition that is available to be loaded with a data word in a write access to the class-based storage partition.

41. The CAM device of claim 40 further comprising an instruction decoder to select one of the plurality of storage elements within the address circuit to output the address stored therein to access the corresponding class-based storage partition in a write operation.

42. The CAM device of claim 41 wherein the instruction decoder is adapted to select the one of the plurality of storage elements within the address circuit according to a class code received from a host device.

43. The CAM device of claim 41 further comprising:

a priority encoder to generate an index indicative of a storage location within the class-based storage partition that is determined not contain a valid data word; and

a load control circuit to load the index into the selected one o f the plurality of storage elements.

44. The CAM device of claim 43 further comprising a flag circuit to assert a flag signal if a storage location within the class-based storage partition is determined not to contain a valid data word, the load control circuit being adapted to load the index into the selected one of the plurality of storage elements if the flag signal is asserted by the flag circuit.

45. A method of operation within a content addressable memory (CAM) device, the method comprising:

receiving an instruction to store a data word in the CAM device, the instruction including a class code that identifies one of a plurality of storage partitions within the CAM device;

selecting, according to the class code, one of a plurality of address storage elements to output an address; and

storing the data word within the CAM device at the address output by the one of the plurality of address storage elements.

46. The method of claim 45 wherein receiving the instruction to store a data word comprises receiving an operation code that includes the class code.

47. The method of claim 45 wherein receiving the instruction to store a data word comprises receiving an operand that includes the class code.

48. The method of claim 45 wherein storing the data word within the CAM device at the address output by the one of the plurality of address storage elements comprises storing the data word within the one of the plurality of storage partitions.

49. The method of claim 48 further comprising:

identifying a storage location within the one of the plurality of storage partitions that does not contain a valid data value; and

loading an address of the storage location into the one of the plurality of address storage elements.

50. The method of claim 45 further comprising loading a new address into the one of the plurality of address storage elements.

51. The method of claim 50 wherein loading a new address into the one of the plurality of address storage elements comprises loading the one of the plurality of address storage elements with a next free address indicative of a storage location within the one of the plurality of storage partitions.

52. A method of operation within a content addressable memory (CAM) device, the method comprising:

receiving an instruction to perform a comparison operation within the CAM device, the instruction including a class code that identifies one of a plurality of storage partitions within the CAM device;

performing the comparison operation, including generating an address of a storage location within the one of the plurality of storage partitions that contains a data word that matches a comparand;

selecting one of a plurality of match address storage elements according to the class code; and

loading the address into the one of a plurality of match address storage elements.

53. The method of claim 52 wherein receiving the instruction to perform a comparison operation comprises receiving an operation code that includes the class code.

54. The method of claim 52 wherein receiving the instruction to perform a comparison operation comprises receiving an operand that includes the class code.

55. The method of claim 52 wherein receiving an instruction to perform a comparison operation comprises receiving an operation code at a first time and receiving the class code at a second time, the operation code indicating a comparison operation.

56. The method of claim 52 wherein generating an address of a storage location comprises generating a highest priority match address.

57. The method of claim 52 further comprising:

receiving an instruction to read a data word stored within the CAM device, the instruction including a class code that identifies the one of a plurality of storage partitions; and

selecting, according to the class code, the one of a plurality of match address storage elements to output an address;

reading the data word from a storage location within the one of the plurality of storage partitions at the address output by the one of the plurality of match address storage elements.

58. A method of operation within a CAM device, the method comprising:

receiving an instruction to read a data word stored within the CAM device, the instruction including a class code that uniquely identifies one of a plurality of storage partitions;

selecting, according to the class code, one of a plurality of address storage elements to output an address; and

reading the data word from a storage location within the one of the plurality of storage partitions at the address output by the one of the plurality of address storage elements.

59. The method of claim 58 wherein receiving the instruction to read a data word comprises receiving an operation code that includes the class code.

60. The method of claim 58 wherein receiving the instruction to read a data word comprises receiving an operand that includes the class code.

61. The method of claim 58 wherein receiving an instruction to read a data word comprises receiving an operation code at a first time and receiving the class code at a second time, the operation code indicating a data read operation.

62. A method of operation within a CAM device, the method comprising:

selecting a first storage partition within the CAM device according to a first class code; and

identifying a free storage location within the first storage partition.

63. The method of claim 62 further comprising:

selecting a second storage partition within the CAM device according to a second class code; and

identifying a free storage location within the second storage partition.

64. The method of claim 63 wherein identifying a free storage location within the first storage partition comprises identifying the free storage location according to a plurality of validity signals, each validity signal indicating whether a corresponding storage location within the first storage partition has a valid data value stored therein.

65. The method of claim 62 further comprising generating an index indicative of an address of the free storage location.

66. The method of claim 62 wherein identifying a free storage location comprises identifying the free storage location within the first storage partition if the first storage partition is not full, the method further comprising asserting a full flag signal to indicate that the first storage partition is full if the first storage partition is full.

67. A method of operation within a CAM device, the method comprising:

selecting a first storage partition within the CAM device according to a class code; and

identifying, within the first storage partition, a storage location having a data value stored therein that, at least in part, matches a first comparand value.

68. The method of claim 67 further comprising:

selecting a second storage partition within the CAM device according to a second class code; and

identifying, within the second storage partition, a second storage location having a data value stored therein that, at least in part, matches a second comparand value.

69. The method of claim 67 wherein identifying the first storage location comprises identifying the first storage location according to a plurality of match signals, each match signal indicating whether a corresponding storage location within the first storage partition contains a data value that, at least in part, matches the first comparand value.

70. The method of claim 67 further comprising generating an index indicative of an address of the first storage location.

71. The method of claim 67 wherein identifying a first storage location within the first storage partition comprises asserting a match flag signal to indicate that a storage location containing a data value that, at least in part, matches the first comparand value has been identified within the first storage partition.

72. The method of claim 67 further comprising:

identifying, within the first storage partition, a second storage location having a data value stored therein that, at least in part, matches the first comparand value; and

asserting a multiple match flag signal to indicate that more than one storage location containing a data value that, at least in part, matches the first comparand value has been identified within the first storage partition.

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

a first CAM block configurable into a first width and depth configuration; and

a second CAM block configurable into a second width and depth configuration.

74. The CAM device of claim 73 further comprising a block select circuit having an input to receive a class code and circuitry to output first and second select signals, each of the first and second select signals to selectively disable the first and second CAM blocks from participating in a compare operation according to the width and depth configurations of the first and second CAM blocks.

75. The CAM device of claim 74 wherein each of the first and second select signals is adapted to disable the one of the first and second CAM blocks from participating in the compare operation by preventing a comparand value from being input to the one of the first and second CAM blocks if the class code does not match a stored configuration value.

76. The CAM device of claim 74 wherein each of the first and second select signals is adapted to disable the one of the first and second CAM blocks from participating in the compare operation by preventing assertion of a match signal that corresponds to the one of the first and second CAM blocks if the class code does not match a stored configuration value.

77. The CAM device of claim 73 wherein the plurality of CAM blocks comprise ternary CAM cells.

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

a plurality of storage means for storing data words, each storage means having a storage width determined according to a configuration value; and

select means for enabling, according to a class code, selected ones of the plurality of the storage means to participate in a compare operation.

79. The CAM device of claim 78 wherein the select means comprises:

compare means for comparing the class code to a plurality of stored class values that correspond, respectively, to the plurality of storage means; and

enable means for enabling each storage means for which the corresponding stored class value matches the class code to participate in the compare operation.

80. The CAM device of claim 79 wherein the enable means comprises comparand disable means for setting a comparand value to a predetermined state to prevent a storage means for which the corresponding stored class value does not match the class code from participating in the compare operation.

81. The CAM device of claim 79 wherein the enable means comprises match disable means to prevent assertion of a match signal that corresponds to a storage means for which the corresponding stored class value does not match the class code.

82. The CAM device of claim 78 wherein each of the plurality of storage means comprises a plurality of ternary CAM cells.