Content addressable memory with hashing function

• US 6,934,796 B1
• Filed: 02/01/2002
• Issued: 08/23/2005
• Est. Priority Date: 02/01/2002
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Jankov, Ronald S., Rathnavelu, Sunder R., Beraha, Rodolfo G., Pereira, Jose P., Carroll, Lewis M.
• Primary Examiner(s): Verbrugge, Kevin
• Application Number:
  US10/061,941
• Time in Patent Office: 1,299 Days
• Field of Search: 711/108, 711/164, 365/49, 365/189.07
• 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

Abstract

A content addressable memory (CAM) device having a memory, a hash index generator to associate a search value with a unique location within a memory, and a compare circuit. The index generator generates an index based on the search value. The memory receives the index from the index generator and outputs a stored data value from a location indicated by the index. A compare circuit receives the data value from the memory and compares the data value and the search value to generate a match signal indicative of whether the data value and search value match. The match signal and index are output from the CAM device.

Claims

1. A method of operation within an integrated circuit device, the method comprising:

generating an index based on a search value;

determining whether constituent bits of the search value, including bits thereof used to generate the index, match corresponding bits of a data value stored at a memory location indicated by the index; and

outputting, from the integrated circuit device, the indent and an indication of whether the constituent bits of the search value match the corresponding bits of the data value.

2. The method of claim 1 wherein generating the index based on the search value comprises selecting a portion of the search value, and generating the index based on the selected portion of the search value.

3. The method of claim 2 wherein selecting the portion of the search value comprises selecting the portion of the search value in accordance with a configuration value stored within the integrated circuit device.

4. The method of claim 1 wherein accenting an index based on the search value comprises:

assembling dispersed fields of bits within the march value to form a search key; and

generating the index based on the search key.

5. The method of claim 4 further comprising masking selected bits within the search key prior to generating the index.

6. The method of claim 5 wherein masking selected bits within the search key comprises masking bits within the search key in accordance with a configuration value within the integrated circuit device.

7. The method of claim 4 wherein assembling dispersed fields of bits within the search value to form the search key comprises assembling the dispersed fields of bits into a contiguous set of bits in accordance with a configuration value within the integrated circuit device.

8. The method of claim 7 wherein the configuration value specifies a data format of the search value.

9. The method of claim 1 wherein generating the index based on the search value comprises generating a hash index based on the search value, the hash index having fewer constituent bits then the search value.

10. The method of claim 9 wherein generating the hash index comprises generating a cyclic redundancy check (CRC) value.

11. The method of claim 1 wherein determining whether the search value matches the data, value comprises comparing the search value with the data value to generate a match signal that indicates whether the search value matches the data value.

12. The method of claim 11 wherein outputting the indication of whether the search value matches the data value comprises outputting the match signal.

13. The method of claim 11 wherein comparing the search value with the data value comprises comparing a selected potion of the search value with a selected portion of the data value, the selected portions of the search value and data value being indicated by a mask value.

14. The method of claim 13 further comprising retrieving the mask value from the memory, location indicated by the index.

15. The method of claim 13 further comprising decoding an encoded value to generate the mask value.

16. The method of claim 15 fuller comprising retrieving the encoded value from the memory location indicated by the index.

17. The method of claim 11 wherein comparing the search value with the data value comprises determining whether the search value is greater than the data value and wherein generating the match signal that indicates whether the search value matches the data value comprises generating a match signal to indicate that the search value matches the data value if the search value is not greater then the data value.

18. The method of claim 11 wherein comparing the search value with the data value comprises determining whether the search value is less then the data value and wherein generating the match signal then indicates whether the search value matches the data value comprises generating a match signal to indicate that the search value matches the data value if the search value is not less then the data value.

19. The method of claim 11 wherein comparing the search value with the data value comprises performing either a range comparison or a match comparison according to a configuration value within she integrated circuit device, and wherein performing a range comparison comprises determining whether the search value is greater than the date value.

20. The method of claim 1 wherein generating an index based on a search value comprises:

generating a plurality of hash values based on the search value, each hub value having fewer constituent bits than the search value; and

selecting one of the hash values to be the index.

21. The method of claim 20 wherein selecting one of the hash values to be the index comprises selecting the one of the hash values in accordance with a configuration value within the integrated circuit device.

22. The method of claim 1 further comprising:

retrieving a priority value from the memory location indicated by the index; and

outputting the priority value from the integrated circuit device.

23. A method of operation within an integrated circuit device, the method comprising:

receiving a search value;

generating an index based on a selected bits of the search value;

determining whether constituent bits of the search value, including the selected bits match corresponding bits of a data value stated at a memory location indicated by the index; and

selecting the selected bits of the search value in accordance with a configuration value stored within the integrated circuit device.

28. The method of claim 23 wherein generating the index based on selected bits of the search value comprises generating a hash index based on the selected bits of the search value, the hash index having fewer constituent bits than the search value.

29. The method of claim 28 wherein generating the hash index comprise generating a cyclic redundancy check (CRC) value.

24. A method of operation within an integrated circuit device, the method comprising:

receiving a search value;

generating an index based on a selected bits of the search value;

determining whether constituent bits of the search value, including the selected bits match corresponding bits of a data value stored at a memory location indicated by the index; and

wherein generating an index based on selected bits of the search value comprises;

assembling dispersed fields of bits within the search value to form a search key; and

generating the index based on the search key.

25. The method of claim 24 further comprising masking bits within the search key prior to generating the index.

26. The method of claim 25 wherein masking bits within the search key comprises masking bits within the search key in accordance with a configuration value within the integrated circuit device.

27. The method of claim 24 wherein assembling dispersed fields of bits within the search value to form the search key comprises assembling the dispersed fields of bits into a contiguous set of bite in accordance with a configuration value within the integrated circuit device.

30. A method of operation within an integrated circuit device, the method comprising:

generating an index based on a search value;

generating an indication of whether a first portion of the search value, including constituent bits of the search value used to generate the index, matches a selected portion of a data value stored at a memory location indicated by the index; and

wherein generating the index based on the match value comprises selecting portion of the first portion of the search value, and generating the index based on the selected portion of the first portion of the search value, and

wherein selecting the portion of the first portion of the search value comprises selecting the portion of the first portion of the search value in accordance with a configuration value stored within the integrated circuit device.

33. The method of claim 30 wherein generating an indication of whether a first portion of the search value matches a selected portion of a data value stored at a memory location indicated by the index comprises:

retrieving the data value from the memory location indicated by the index; and

comparing the first portion of the search value with the selected portion of the data value to generate a match signal that indicates whether the search value matches the data value.

31. A method of operation within an integrated circuit device, the method comprising:

generating an index based on a search value;

generating an indication of whether a first portion of the starch value, including constituent bits of the search value used to generate the index, matches a selected portion of a data value stored at a memory location indicated by the index; and

wherein generating an index based on the search value comprises;

assembling dispersed fields of bits within the search value to form a search key; and

generating the index based on the search key.

32. The method of claim 31 further comprising masking selected bits within the search key prior to generating the index, the selected bits being selected in accordance with a configuration value within the integrated circuit device.

34. A method of operation within an integrated circuit device, the method of comprising:

generating an index based on a search value;

generating an indication of whether a first portion of the search value, including constituent bits of the search value used to generate the index, matches a selected portion of a data value stored at a memory location indicated by the index;

retrieving mask information from the memory location indicated by the index, the mask information indicating the selected portion of the data valve; and

wherein generating the indication of whether the first portion of the search value matches the selected portion of the data value stored at the memory location indicated by the index comprises;

retrieving the data value from the memory location indicated by the index; and

comparing the first portion of the search value with the selected portion of the data value to generate the match signal that indicates whether the search value matches the data value.

35. The method of claim 34 further comprising decoding an encoded value included within the mask information to generate a decoded mask value, the mask value indicating the selected portion of the data value.

36. A method of operation within an integrated circuit device the method comprising:

generating a search index based on a search value; and

identifying, within a content addressable memory (CAM), one of a plurality of stored indices that matches the search index; and

determining whether the search value matches a data value stored at a first location within a data memory, the first location corresponding to a location of the one of the plurality of indices.

37. The method of claim 36 wherein generating the search index based on the search value comprises selecting a portion of the search value, and generating the search index based on the selected portion of the search value.

38. The method of claim 37 wherein selecting the portion of the search value comprises selecting the portion of the search value in accordance with a configuration value within the integrated circuit device.

39. The method of claim 36 wherein generating the search index based on the search value comprises generating a search index having fewer constituent bits than the search value.

40. The method of claim 36 wherein generating the search index comprise generating a cyclic redundancy check (CRC) value.

41. The method of claim 36 wherein identifying, within the CAM, one of a plurality of stored indices that matches the search index comprises comparing the search index with each of the plurality of stored indices.

42. The method of claim 41 wherein comparing the search index with each of the plurality of stored indices comprises simultaneously comparing the search index with each of the plurality of stored indices.

43. The method of claim 41 wherein identifying one of a plurality of stored indices that matches the search index further comprises generating a plurality of match signals, each match signal indicating whether a respective one of the stored indices matches the search index.

44. The method of claim 36 wherein determining whether the search value matches a data value stored at a first location within a data memory comprises:

retrieving the data value from the first location within the memory; and

comparing the search value with the data value.

45. The method of claim 44 wherein retrieving the data value from the first location within the memory comprises:

generating a row address indication that corresponds to the one of the plurality of stored indices that matches the search index; and

retrieving the data value from a location within the memory indicated by the row address indication.

46. The method of claim 45 wherein generating the row address indication comprises generating a plurality of match signals that each indicate whether a respective one of the stored indices matches the search index.

47. The method of claim 46 wherein generating the row address indication further comprises encoding the plurality of match signals into a row address.

48. The method of claim 47 wherein encoding the plurality of match signals into a row address comprises retrieving the row address from a lookup table storage location indicated by the plurality of match signals.

49. A method of operation within an integrated circuit device, the method comprising:

converting a search value into a search index having fewer constituent bits than the search valve;

identifying, within a content addressable memory (CAM), one of a plurality of stored indices that matches the search index; and

outputting a data value from a first location within a data memory, the first location corresponding to a location within the CAM of the one of the plurality of indices.

50. The method of claim 49 further comparing determining whether the search value matches the data value.

51. The method of claim 50 further comprising generating a match signal that indicates whether the search value matches the data value.

52. The method of claim 49 wherein converting a match value into a search index comprises converting a selected portion of the search value into a search index.

53. The method of claim 49 wherein converting a search value into a search index comprises generating a hash index based on the search value.

54. The method of claim 53 wherein generating a hash index comprises generating a cyclic redundancy check (CRC) value.

55. The method of claim 49 wherein identifying within the CAM, one of a plurality of stored indices that matches the search index comprises comparing the search index with each of the plurality of stored indices.

56. The method of claim 55 wherein comparing the search index with each of the plurality of stored indices comprises simultaneously comparing the search index with each of the plurality of stored indices.

57. The method of claim 55 wherein identifying, within a content addressable memory (CAM), one of a plurality of stored indices that matches the search index further comprises generating a plurality of match signals, each match signal indicating whether a respective one of the stored indices matches the search index.

58. The method of claim 49 wherein outputting the data value from the first location within the data memory comprises:

generating a new address indication that corresponds to the one of the plurality of stored indices that matches the search index; and

retrieving the data value from a location within the data memory indicated by the row address indication.

59. The method of claim 58 wherein generating the row address indication comprises generating a plurality of match signals that each indicate whether a respective one of the stored indices matches the search index.

60. The method of claim 59 wherein generating the row address indication further comprises encoding the plurality of match signals into a row address.

61. A method of operation within an integrated circuit device, the method comprising:

generating a plurality of indices based on a search value;

selecting, according to a select value, one of the plurality of indices; and

determining whether the search value matches a data value stored at a memory location indicated by the one of the plurality of indices.

62. The method of claim 61 wherein generating a plurality of indices based on a search value comprises selecting a portion of the search value, and generating each of the plurality of indices based on the selected portion of the search value.

63. The method of claim 62 wherein selecting the portion of the search value comprises selecting the portion of the search value in accordance with a configuration value stored within the integrated circuit device.

64. The method of claim 62 wherein generating each of the plurality of indices based on the search value comprises:

assembling dispersed fields of bits within the search value to form a search key; and

generating each of the plurality of indices based on the search key.

65. The method of claim 64 further comprising masking selected bits within the search key prior to generating the plurality of indices.

66. The method of claim 65 wherein masking selected bits within the search key comprises masking bits within the search key in accordance with a configuration value within the integrated circuit device.

67. The method of claim 61 wherein selecting one of the plurality of indices comprises selecting one of the plurality of indices in accordance with a configuration value within the integrated circuit device.

68. The method of claim 61 wherein generating a plurality of indices based on a search value comprises generating a plurality of different indices based on the search value.

69. The method of claim 68 wherein generating a plurality of plurality of different indices comprises inputting at least a portion of the search value to a plurality of hash function circuits, each hash function circuit being adapted to generate a respective hash index based on a hash function that is different from the others of the hash function circuits.

70. The method of claim 61 wherein determining whether the search value matches a data value stored at a memory location indicated by the one of the plurality of indices comprises comparing the search value with the data value and generating a match signal the indicates whether the search value matches the data value.

71. The method of claim 70 wherein comparing the search value with the date value comprises comparing a selected portion of the search value with a selected portion of the data value, the selected portions of the search values and data value being indicated by a mask value.

72. The method of claim 71 further comprising retrieving the mask value from the memory location indicated by the one of the plurality of indices.

73. A method of operation within an integrated circuit device, the method comprising:

generating a plurality of indices based on a search value;

retrieving a plurality of data values from a plurality of memories, each data value being retrieved from a respective one of the memories at a location indicated by a respective one of the plurality of indices;

comparing the search value to each of the plurality of data values to identity one of the data values that matches the search value; and

generating a value that identifies the respective one of the memories from which the one of the data values that matches the search value was retrieved.

74. The method of claim 73 wherein generating a plurality of indices based on a search value comprises generating a plurality of hash indices based on at least a portion of the search value, each of the hash indices having fewer constituent bits than the search value.

75. The method of claim 74 wherein generating the plurality of hash indices comprises generating a plurality of cyclic redundancy check (CRC) values.

76. The method of claim 73 wherein comparing the search value to each of the plurality of data values comprises comparing the search value with a selected portion of each of the data values, the selected portion of each of the data values being indicated by a respective mask value.

77. The method of claim 76 further comprising retrieving the respective mask value from a respective one of the memories at a location indicated by a respective one of the plurality of indices.

78. The method of claim 73 wherein retrieving a plurality of data values from a plurality of memories comprises retrieving a first data value from a first one of the plurality of memories, and retrieving a second data value from a second one of the plurality of memories, the second one of the plurality of memories having a different storage capacity than the first one of the plurality of memories.

79. A method of operation within an integrated circuit device, the method comprising:

receiving a search value and a corresponding search code;

comparing the search code to a plurality of configuration values, each of the configuration values corresponding to a respective one of a plurality of data memories within the integrated circuit device;

generating a plurality of indices based on the search value;

retrieving a plurality of data value from the plurality of data memories, each data value being retrieved from a respective one of the data memories at a location indicated by a respective one of the indices; and

generating, for each of the plurality of data memories, a respective match signal having a first state if the search value matches the data value retrieved from the data memory and if the search code matches the configuration value that corresponds to the data memory.

80. The method of claim 79 wherein receiving a search code comprises receiving a search code that indicates a formatting of the corresponding search value.

81. The method of claim 79 wherein receiving a search code comprises receiving a search code that indicates positions of maskable bits within the corresponding search value.

82. The method of claim 79 wherein generating a match signal having a first state if the search value matches the data value retrieved from the data memory and if the search code matches the configuration value that corresponds to the data memory comprises:

comparing a selected portion of the search value and a selected portion of the data value; and

generating a match signal having a first state if the selected portion of the search signal matches the selected portion of the data value and if the search code matches the configuration value.

83. The method of claim 79 further comprising retrieving a plurality of priority values from the plurality of data memories, each priority value being retrieved from a respective one of the data memories at a location indicated by a respective one of the indices.

84. The method of claim 79 further comprising generating an identifier based on the plurality of priority values and the match signals generated for the plurality of data memories, the identifier indicating one of the plurality of date memories.

85. The method of claim 84 wherein generating an identifier that indicates one of the plurality of data memories comprises generating an identifier that indicates a data memory of the plurality of data memories that contains a highest priority one of the plurality of priority values and for which the respective match signal has the first state.

86. A method of operation within an integrated circuit device, the method comprising:

generating an index based on an input value;

retrieving a first value from a location, indicated by the index, within a first memory;

comparing the first value to the input value to generate a first match signal that indicates whether the input value matches the first value; and

comparing the input value simultaneously to each of a plurality of values stored in a second memory to generate a second match signal that indicates whether the input value matches one of the plurality of values stored in the second memory.

87. The method of claim 86 wherein comparing the input value simultaneously to each of a plurality of values stored in the second memory comprises comparing the input value to a plurality of values stored in an array of content addressable memory (CAM) cells, each CAM cell including a storage element end a compare circuit.

88. The method of claim 86 further comprising:

outputting a first priority value from the location within the first memory;

outputting a second priority value from the second memory; and

comparing the first priority value and the second priority value in accordance with the states of the first and second match signals to determine a highest priority one of the priority values.

89. The method of claim 88 wherein comparing the first priority value and the second priority value in accordance with the states of the first and second match signals to determine a highest priority one of the priority values comprises determining the first priority value to be the highest priority value if the first match signal is asserted and the first priority value indicates a higher priority than the second priority value.

90. The method of claim 86 wherein generating an index based on an input value comprises generating an index having fewer constituent bits than the input value.

91. The method of claim 86 wherein generating the index based on the search value comprises selecting a portion of the search value, and generating the index based on the selected portion of the search value.

92. The method of claim 91 wherein selecting the portion of the search value comprises selecting the portion of the search value in accordance with a configuration value within the integrated circuit device.

93. The method of claim 91 wherein generating an index based on the search value comprises:

assembling dispersed fields of bits within the search value to form a search key, and generating the index based on the search key.

94. The method of claim 93 further comprising masking selected bits within the search key prior to generating the index.

95. The method of claim 94 wherein masking selected bits within the search key comprises masking bits within the search key in accordance with a configuration value within the integrated circuit device.

96. A method of operation within an integrated circuit device, the method comprising:

generating a plurality of priority values in response to a first instruction, each priority value indicating a storage capacity of a respective one of a plurality of circuit blocks; and

generating, based on the priority values, a block identifier that identifies one of the circuit blocks.

97. The method of claim 96 wherein generating the block identifier based on the priority values comprises generating a block identifier that identifies a least filled one of the plurality of circuit blocks.

98. The method of claim 96 wherein generating the block identifier based on the priority values comprises generating a block identifier that identifies a most filled one of the plurality of circuit blocks.

99. The method of claim 96 further comprising storing in response to generation of the block identifier, a data value in the one of the plurality of circuit blocks identified by the block identifier.

100. A method of operation within an integrated circuit device, the method comprising:

generating a plurality of indices based on a search value; and

for each of a plurality of circuit blocks within the integrated circuit device;

selecting one of the indices;

retrieving a data value from a first storage location within the circuit block, the first storage location being indicated by the one of the indices; and

determining whether the date value matches the search value.

101. The method of claim 100 wherein generating the plurality of indices based on the search value comprises generating a plurality of indices that each have fewer constituent bits than the search value.

102. The method of claim 100 wherein generating the plurality of indices based on the search value comprises generating each of the plurality of indices based on a selected portion of the search value.

103. The method of claim 100 wherein selecting one of the indices comprises selecting one of the indices in accordance with a configuration value within the integrated circuit.

104. The method of claim 100 wherein determining whether the data value matches the search value comprises comparing a selected portion of the data value with a selected portion of the mask value.