System and method for low power searching in content addressable memories using sampling search words to save power in compare lines

Abstract

An invention is provided for lowLow power searching in a CAM usinguses sample words to save power in the compare lines. The inventionA method includes comparing a sample section of stored data to a corresponding sample section of search data on a plurality of rows in the CAM. If a sample section of the stored data on any row of the plurality of rows is equivalent to the corresponding sample section of the search data, a remaining section of search data is allowed to propagate to the local compare lines coupled to the remaining section of the stored data of each row. However, if the sample section of the stored data is different from the corresponding sample section of the search data, the local compare lines coupled to the remaining section of the stored data on each row are latched.

What is claimed is: 
     
       1. A method for low power searching in a content addressable memory (CAM), comprising the operations of:
 comparing a sample section of stored data to a corresponding sample section of search data on a plurality of rows in the CAM; 
 allowing a remaining section of search data to propagate to local compare lines coupled to a remaining section of the stored data of each row if a sample section of the stored data on any row of the plurality of rows is equivalent to the corresponding sample section of the search data; and 
 latching the local compare lines coupled to the remaining section of the stored data on each row if the sample section of the stored data is different from the corresponding sample section of the search data. 
 
     
     
       2. A method as recited in  claim 1 , further comprising the operation of loading the search data onto global compare lines, each global compare line spanning a width of the CAM. 
     
     
       3. A method as recited in  claim 2 , further comprising the operation of providing results of a comparison between the sample section of the stored data and the corresponding sample section of the search data for each row of the plurality of rows as an inputs to a logic gate. 
     
     
       4. A method as recited in  claim 3 , further comprising the operation of allowing search data to propagate from the global compare lines to the local compare lines if an output of the logic gate indicates a comparison result is a match. 
     
     
       5. A method as recited in  claim 4 , further comprising the operation of latching the local compare lines if the output of the logic gate indicates all the comparison results are misses. 
     
     
       6. A method as recited in  claim 1 , wherein the remaining section of the stored data is not compared to the corresponding remaining section of the search data if the sample section of the stored data is different from the corresponding section of the search data. 
     
     
       7. A method as recited in  claim 1 , wherein the sample section of the stored data is smaller than the remaining section of the stored data. 
     
     
       8. A method as recited in  claim 7 , wherein a match line coupled to the stored data comprises a first section and a second section, both the first section and the second section being coupled to a latch via a gate. 
     
     
       9. A method as recited in  claim 8 , wherein a first portion of the sample section of the stored data is coupled to the first section of the match line and a second portion of the sample section of the stored data is coupled to the second section of the match line. 
     
     
       10. A match line for a content addressable memory (CAM), the match line being one of a plurality of match lines forming a group of match lines, the match line comprising:
 a sample match line coupled to a first set of CAM cells; 
 a sub-match line coupled to a second set of CAM cells, each CAM cell of the second set of CAM cells being coupled to local compare lines, the local compare lines being in electrical communication with global compare lines via a plurality of local compare line latches; and 
 a compare line propagation control circuit coupled to the local compare line latches, wherein the compare line propagation control circuit latches the local compare lines if a sample section of search data corresponding to the first set of CAM cells is different from data stored in the first set of CAM cells for each sample match line in the group of match lines. 
 
     
     
       11. A match line as recited in  claim 10 , wherein the compare line propagation control circuit allows the search data to propagate from the global compare lines to the local compare lines if the sample section of search data corresponding to the first set of CAM cells is equivalent to data stored in the first set of CAM cells for any sample match line in the group of match lines. 
     
     
       12. A match line as recited in  claim 11 , wherein the compare line propagation control circuit includes a logic gate having a plurality of inputs, each input of the logic gate being in electrical communication with the sample match line of each match line in the group of match lines. 
     
     
       13. A match line as recited in  claim 12 , wherein the search data is allowed to propagate from the global compare lines to the local compare lines if an output of the logic gate indicates a match on any sample match line of the group of match lines. 
     
     
       14. A match line as recited in  claim 13 , wherein the local compare lines are latched if the output of the logic gate indicates a “miss” on all the sample match lines of the group of match lines. 
     
     
       15. A content addressable memory (CAM), comprising:
 a group of match lines, each match line including a sample match line coupled to a first set of CAM cells, and a submatch line coupled to a second set of CAM cells, each CAM cell of the second set of CAM cells being coupled to a pair of local compare lines; 
 a plurality of global compare lines, each global compare lines spanning a width of the CAM, each global compare line in electrical communication with a plurality of local compare lines via a plurality of local compare line latches; and 
 a compare line propagation control circuit coupled to the local compare line latches, wherein the compare line propagation control circuit latches the local compare lines if a sample section of search data corresponding to the first set of CAM cells is different from data stored in the first set of CAM cells for each sample match line in the group of match lines. 
 
     
     
       16. A CAM as recited in  claim 15 , wherein the compare line propagation control circuit allows the search data to propagate from the global compare lines to the local compare lines if the sample section of search data corresponding to the first set of CAM cells is equivalent to data stored in the first set of CAM cells for any sample match line in the group of match lines. 
     
     
       17. A CAM as recited in  claim 16 , wherein the compare line propagation control circuit includes a logic gate having a plurality of inputs, each input of the logic gate being in electrical communication with the sample match line of each match line in the group of match lines. 
     
     
       18. A CAM as recited in  claim 16 , wherein the search data is allowed to propagate from the global compare lines to the local compare lines if an output of the logic gate indicates a match on any sample match line of the group of match lines. 
     
     
       19. A CAM as recited in  claim 18 , wherein the local compare lines are latched if the output of the logic gate indicates a “miss” on all the sample match lines of the group of match lines. 
     
     
       20. An apparatus, comprising:
 means for comparing a sample section of stored data to a corresponding sample section of search data on one or more rows in a content addressable memory;   means for allowing a remaining section of search data to propagate to local compare lines coupled to a remaining section of the stored data of one or more rows if a sample section of the stored data on any row of the one or more rows is equivalent to the corresponding sample section of the search data; and   means for latching the local compare lines coupled to the remaining section of the stored data on one or more rows if the sample section of the stored data is different from the corresponding sample section of the search data.   
     
     
       21. An apparatus as claimed in claim 20, further comprising means for loading the search data onto global compare lines, one or more of the global compare lines spanning a width of the content addressable memory. 
     
     
       22. An apparatus as claimed in claim 21, further comprising means for providing results of a comparison between the sample section of the stored data and a corresponding sample section of the search data for one or more of the one or more rows as an input to a logic gate. 
     
     
       23. An apparatus as claimed in claim 22, further comprising means for allowing search data to propagate from the global compare lines to the local compare lines if an output of the logic gate indicates a comparison result is a match. 
     
     
       24. An apparatus as claimed in claim 23, further comprising means for latching the local compare lines if the output of the logic gate indicates all the comparison results are misses. 
     
     
       25. An apparatus as claimed in claim 20, further comprising means for preventing comparing of the remaining section of the stored data to a corresponding remaining section of the search data if the sample section of the stored data is different from a corresponding section of the search data. 
     
     
       26. An apparatus as claimed in claim 20, wherein the sample section of the stored data is smaller than the remaining section of the stored data. 
     
     
       27. An apparatus as claimed in claim 26, further comprising a match line coupled to the stored data comprising a first section and a second section, and further comprising means for coupling the first section or the second section, or combinations thereof, to a latch via a gate. 
     
     
       28. An apparatus as claimed in claim 27, further comprising means for coupling a first portion of the sample section of the stored data to the first section of the match line, and means for coupling a second portion of the sample section of the stored data to the second section of the match line. 
     
     
       29. A method, comprising:
 comparing a first portion of stored data to a corresponding first portion of search data on a row in a content addressable memory; and   providing a second portion of search data to a compare line coupled to a second portion of the stored data of the row if the first portion of the stored data is equivalent to the corresponding first portion of the search data.   
     
     
       30. The method of claim 29, wherein the first portion of stored data is compared to a corresponding first portion of search data on a plurality of rows of the content addressable memory, wherein the second portion of search data is provided to compare lines coupled to the second portion of the stored data of each of the plurality of rows if the first portion of the stored data on any row of the plurality of rows is equivalent to the corresponding first potion of the search data. 
     
     
       31. The method of claim 30, further comprising latching the compare line coupled to the second portion of the stored data if the first portion of the stored data is different from the corresponding first portion of the search data.