Result compare circuit and method for content addressable memory (CAM) device
View Patent ↗A content addressable memory (CAM) device ( 100 ) may include a number of blocks ( 102 -[ n− 1 , n, n+ 1]) that each generate CAM search results and result compare circuits ( 104 -[ n− 1 , n, n+ 1] that receive CAM search results from multiple blocks ( 102 -[ n− 1 , n, n− 1]), and compare at least a portion of such CAM search results. According to such a comparison result, a compare circuit ( 104 -[ n− 1 , n, n+ 1]) can generate an output CAM search result for subsequent comparison with CAM search result in another compare circuit ( 104 -[ n −1 , n, n+ 1]).
1. A result compare circuit, comprising:
a comparator circuit that compares input values to one another, the comparator circuit having a first input coupled to receive a first result status value from a first portion of a content addressable memory (CAM and a second input coupled to receive a second result status value from a second portion of the CAM.
2. The result compare circuit of claim 1 , wherein:
the comparator circuit includes a plurality of bit comparators having a significance with respect to one another, each comparator circuit generating a bit comparison result.
3. The result compare circuit of claim 2 , further including:
a subsequent result compare circuits in a result compare flow;
a prior result compare circuit in the result compare flow; and
the comparator circuit provides the bit comparison results to the subsequent result compare circuits in the result compare flow and receives bit comparison results from the prior result compare circuit in the result compare flow.
4. The result compare circuit of claim 2 , wherein:
the bit comparison results include a greater-than result, a less-than result and equal-to result.
5. The result compare circuit of claim 2 , wherein:
each bit comparator includes
a first portion that receives a bit from a first result status value, a bit from a second result status value, and a compare result from a higher significance bit comparator, and generates an output bit comparison result for a bit comparator of less significance.
6. The result compare circuit of claim 5 , wherein:
each bit comparator includes
a second portion that receives a bit from a first result status value, a bit from a second result status value, and a compare result from a higher significance bit comparator, and outputs the bit from the first result status value if a compare result is greater-than, outputs the bit from the second result status value if a compare result is less-than, and outputs a highest of the bits from the first or second result status values if a compare result is equal to.
7. The result compare circuit of claim 1 , wherein:
the comparator circuit further includes a summary result generator that outputs one value if a selected portion of a first status result value matches a corresponding portion of a second status result value.
8. The result compare circuit of 1 , further including:
a second result comparator circuit; and
a multiplexer (MUX) having a first MUX input that receives result data from the first portion of the CAM, a second MUX input that receives result data from the second portion of the CAM, a control input coupled to the comparator circuit, and an output coupled to an input of the second result comparator circuit.
9. A method of generating search results in a content addressable memory (CAM) device, comprising the steps of:
generating search results in a plurality of CAM sections that each include a plurality of CAM entries, each search result including a priority value; and
comparing multiple priority values to generate a highest priority search result from the plurality of search results.
10. The method of claim 9 , wherein:
the step of comparing multiple priority values includes comparing a first priority value from a first search result with a second priority value from a second search result to generate a compare result; and
selectively outputting at least a portion of either the first search result or the second search result according to the compare result.
11. The method of claim 10 , further including:
forwarding at least a portion of the compare result between the first priority value and the second priority value for comparison with a third priority value from a third search result before selectively outputting either the first search result or the second search result.
12. The method of claim 10 , wherein:
comparing the first priority value to the second priority value includes comparing bits of the first priority value to corresponding bits of the second priority value in a sequential fashion, from a more significant bit to a less significant bit.
13. The method of claim 12 , wherein:
comparing a bit of the first priority value to a corresponding bit of the second priority value includes
generating a bit compare result if a more significant bit compare result is an equal-to result,
generating a greater-than result if a more significant bit compare result is a greater-than result, and
generating a less-than result if a more significant bit compare result is a less-than result.
14. The method of claim 12 , wherein:
comparing a bit of the first priority value to a corresponding bit of the second priority value includes
outputting the bit of the first priority value if a more significant bit compare result is a greater-than result,
outputting the higher of the bit of the first priority value and bit of the second priority value if the more significant bit compare result is an equal-to result, and
outputting the bit of the second priority value if a more significant bit compare result is a less-than result.
15. A content addressable memory (CAM) device, comprising:
a plurality of sub-blocks that each compare a key value to stored data values; and
at least one sub-block magnitude comparator for selectively providing an output of one of the plurality of sub-blocks according to a priority value associated with the one sub-block.
16. The CAM device of claim 15 , further including:
the plurality of sub-blocks are arranged into blocks; and
a block magnitude comparator for selectively providing an output of one of the blocks according to a priority value associated with at least one of the sub-blocks in the one block.
17. The CAM device of claim 15 , further including:
a multiplexer having a first input coupled to one of the plurality of sub-blocks, a second input coupled to another one of the plurality of sub-blocks, and a control input coupled to the at least one sub-block magnitude comparator.
18. A content addressable memory system, comprising:
at least one CAM that determines a search result precedence using a predetermined set of weighted search result factors, the at least one CAM including entries divided into blocks; and
the search result factors include a priority value for a block containing a free entry.
19. The content addressable memory system of claim 18 , wherein:
the search result factors include a priority value for a block containing a matching entry.
20. The content addressable memory system of claim 18 , wherein:
the search result factors include a priority value for a free block.
21. The content addressable memory system of claim 18 , wherein:
the blocks are divided into sub-blocks.
22. The content addressable memory system of claim 21 , wherein:
the search result factors include a priority value for a sub-block containing a matching entry.
23. The content addressable memory system of claim 21 , wherein
the search result factors include a priority value for a sub-block containing a free entry.