Content based content addressable memory block enabling using search key
View Patent ↗A content addressable memory includes a plurality of CAM blocks, each including an array of CAM cells to store a predetermined range of data values, a parsing circuit having an input to receive the search key and having an output to provide a selected portion of the search key in response to a select signal, and a plurality of block select circuits, each configured to enable a corresponding CAM block if the selected portion of the search key falls within the predetermined range of data values for the corresponding CAM block.
1. A content addressable memory (CAM) device for comparing a search key to data values stored therein, comprising:
a plurality of CAM blocks, each including an array of CAM cells to store a predetermined range of data values;
means for extracting a selected portion of the search key in response to a select signal, wherein the selected portion of the search key is less than the search key; and
means for selectively enabling each CAM block in response to a comparison between the selected portion of the search key and the predetermined range of data values that are stored in the corresponding CAM block, wherein only the selectively enabled CAM blocks participate in the next compare operation with the search key.
2. The CAM device of claim 1 , wherein the means for extracting comprises a parsing circuit.
3. The CAM device of claim 1 , wherein the data values comprise network addresses.
4. The CAM device of claim 1 , wherein each CAM block is assigned to store a unique range of data values.
5. The CAM device of claim 1 , wherein one or more CAM blocks are assigned to store overlapping ranges of data values.
6. The CAM device of claim 1 , wherein the selected portion of the search key comprises a number of most significant bits of the search key.
7. The CAM device of claim 1 , wherein each data value has an associated priority value.
8. The CAM device of claim 1 , wherein the means for selectively enabling comprises a plurality of block select circuits, each configured to enable a corresponding CAM block if the selected portion of the search key falls within the predetermined range of data values stored in the corresponding CAM block.
9. The CAM device of claim 8 , wherein the block select circuit includes a function generator.
10. The CAM device of claim 9 , wherein the function generator performs a hashing function on the selected portion of the search key.
11. The CAM device of claim 8 , wherein each block select circuit disables the corresponding CAM block if the selected portion of the search key does not fall within the predetermined range of data values stored in the corresponding CAM block.
12. A content addressable memory (CAM) device for comparing a search key to data stored therein, comprising:
a plurality of CAM blocks, each including an array of CAM cells to store a predetermined range of data values;
a parsing circuit having an input to receive the search key and having an output to provide a selected portion of the search key in response to a select signal, wherein the selected portion of the search key is less than the search key; and
a plurality of block select circuits, each configured to enable a corresponding CAM block for the next compare operation with the search key if the selected portion of the search key falls within the predetermined range of data values that are stored in the corresponding CAM block.
13. The CAM device of claim 12 , wherein each block select circuit comprises:
a storage element to store a lower range value and an upper range value for the corresponding CAM block; and
a compare circuit having a first input to receive the selected portion of the search key, second inputs to receive the lower and upper range values, and an output to generate a block select signal for the corresponding CAM block.
14. The CAM device of claim 13 , wherein the compare circuit asserts the block select signal if the selected portion of the search key is greater than the lower range value and less than the upper range value for the corresponding CAM block.
15. The CAM device of claim 13 , wherein the compare circuit de-asserts the block select signal if the selected portion of the search key is less than the lower range value or greater than the upper range value for the corresponding CAM block.
16. The CAM device of claim 13 , wherein each block select circuit further comprises a function generator having an input to receive the selected portion of the search key and having an output connected to the first input of the compare circuit.
17. The CAM device of claim 16 , wherein the function generator performs a logical function on the selected portion of the search key.
18. The CAM device of claim 17 , wherein the logical function comprises a hashing function.
19. The CAM device of claim 12 , wherein the data values comprise network addresses.
20. The CAM device of claim 12 , wherein each CAM block is assigned to store a unique range of data values.
21. The CAM device of claim 12 , wherein one or more CAM blocks are assigned to store overlapping ranges of data values.
22. The CAM device of claim 12 , wherein the selected portion of the search key comprises a number of most significant bits of the search key.
23. The CAM device of claim 12 , wherein each data value has an associated priority value.
24. A method of operating a content addressable memory (CAM) device including a plurality of CAM blocks each for storing a predetermined range of data values to be compared with a search key, comprising:
extracting a selected portion of the search key in response to a select signal, wherein the selected portion of the search key is less than the search key; and
for each CAM block,
determining whether the selected portion of the search key falls within the predetermined range of data values stored in the CAM block; and
selectively enabling the CAM block, in response to the determining, to participate in the next compare operation with the search key.
25. The method of claim 24 , wherein the determining comprises:
comparing the selected portion of the search key with lower and upper range values associated with the predetermined range of data values stored in the CAM block.
26. The method of claim 25 , wherein the selectively enabling comprises:
generating a plurality of block enable signals in response to the comparing.
27. The method of claim 25 , further comprising:
storing the data values into the CAM blocks according to their predetermined ranges.
28. The method of claim 24 , further comprising:
performing a logical function on the selected portion of the search key.
29. A method of selectively enabling a plurality of CAM blocks each for storing a predetermined range of data values, comprising:
extracting a selected portion of a search key in response to a select signal, wherein the selected portion of the search key is less than the search key;
for each CAM block, determining whether the selected portion of the search key falls within the predetermined range of data values that are stored in the corresponding CAM block; and
generating a plurality of block enable signals, in response to the determining, for selectively enabling the CAM blocks to participate in the next compare operation with the search key.
30. The method of claim 29 , wherein the determining comprises:
comparing the selected portion of the search key to a lower range value and an upper range value associated with each of the plurality of CAM blocks.