Word search in content addressable memory

Abstract

A content addressable memory (CAM) is provided that can perform wide word searches. At least one CAM memory core having a plurality of bit pattern entry rows is included in the CAM. In addition, search logic is included that, is capable searching particular rows during each cycle. The search logic is also capable of allowing match line results of unsearched rows to remain unchanged during a cycle. The CAM further includes a serial AND array in communication with the bit pattern entry rows, wherein the serial AND array is capable of computing a match result for wide word entries that span multiple bit pattern entry rows. In one aspect, a match line enable signal is provided to the serial AND array, which facilitates computation of the match result.

1. A content addressable memory (CAM) capable of performing wide word searches, comprising:
 at least one CAM memory core having a plurality of bit pattern entry rows; 
 a boundary array having a plurality of word boundary bits, each word boundary bit corresponding to a bit pattern entry row; and 
 a serial AND array in communication with the bit pattern entry rows and the word boundary bits, wherein the serial AND array is capable of utilizing the word boundary bits to compute a match result for wide word entries that span multiple bit pattern entry rows. 
 
     
     
       2. A CAM as recited in  claim 1 , wherein specific word boundary bits indicate word boundaries of stored word entries. 
     
     
       3. A CAM as recited in  claim 2 , wherein word boundary bits having a value of “1” indicate a beginning of a new word entry. 
     
     
       4. A CAM as recited in  claim 1 , wherein the serial AND array includes a plurality of serial AND computational units. 
     
     
       5. A CAM as recited in  claim 4 , wherein each serial AND computational unit is in electrical communication with a bit pattern entry row and a word boundary bit corresponding to the bit pattern entry row. 
     
     
       6. A CAM as recited in  claim 5 , wherein each serial AND computational unit receives a match line from the corresponding bit pattern entry row and a word boundary bit from the boundary array as input signals. 
     
     
       7. A CAM as recited in  claim 6 , further including a plurality of CAM memory cores that are serially coupled. 
     
     
       8. A CAM as recited in  claim 7 , wherein the CAM is capable of storing word entries spanning multiple CAM memory cores. 
     
     
       9. A content addressable memory (CAM) capable of performing wide word searches, comprising:
 a boundary array having a plurality of word boundary bits, each word boundary bit corresponding to a bit pattern entry row of a CAM memory core; and 
 a serial AND array having a plurality of serial AND computational units, each serial AND computational unit in communication with a corresponding bit pattern entry row of the CAM memory core and a word boundary bit corresponding to the bit pattern entry row, wherein the serial AND computational units receive as inputs a word boundary bit and an internal match line result corresponding to an adjacent bit pattern entry row, 
 wherein the serial AND array is capable of utilizing the word boundary bits to compute a match result for wide word entries that span multiple bit pattern entry rows. 
 
     
     
       10. A CAM as recited in  claim 9 , wherein specific word boundary bits indicate word boundaries of stored word entries. 
     
     
       11. A CAM as recited in  claim 10 , wherein word boundary bits having a value of “1” indicate a beginning of a new word entry. 
     
     
       12. A CAM as recited in  claim 11 , wherein each serial AND computational unit is capable of outputting a “1” only when the corresponding word boundary bit is a “1.” 
     
     
       13. A CAM as recited in  claim 12 , wherein the internal match line result for a particular serial AND computational unit is a match line result before processing the word boundary bit corresponding to the serial AND computational unit. 
     
     
       14. A CAM as recited in  claim 9 , wherein a bit pattern entry row having a lowest priority of the bit pattern entry rows comprising a word entry is searched before remaining bit pattern entry rows of the word entry. 
     
     
       15. A CAM as recited in  claim 14 , wherein a bit pattern entry row having a highest priority of the bit pattern entry rows comprising the word entry is searched after other bit pattern entry rows of the word entry. 
     
     
       16. A content addressable memory (CAM) capable of performing wide word searches, comprising:
 a boundary array having a plurality of word boundary bits, each word boundary bit corresponding to a bit pattern entry row of a CAM memory core; and 
 a serial AND array having a plurality of serial AND computational units, each serial AND computational unit in communication with a corresponding bit pattern entry row of the CAM memory core and a word boundary bit corresponding to the bit pattern entry row, wherein the serial AND computational units receive as inputs a control signal indicating a beginning of a search and a control signal indicating an end of a search, 
 wherein the serial AND array is capable of utilizing the word boundary bits to compute a match result for wide word entries that span multiple bit pattern entry rows. 
 
     
     
       17. A CAM as recited in  claim 16 , wherein serial AND computational units further receive as an input a match result from an adjacent serial AND computational unit. 
     
     
       18. A CAM as recited in  claim 17 , wherein specific word boundary bits indicate word boundaries of stored word entries. 
     
     
       19. A CAM as recited in  claim 18 , wherein word boundary bits having a value of “1” indicate a beginning of a word entry spanning multiple bit pattern entry rows. 
     
     
       20. A CAM as recited in  claim 16 , further including a plurality of CAM memory cores that are serially coupled, wherein the CAM is capable of storing word entries spanning multiple CAM memory cores. 
     
     
       21. A content addressable memory (CAM) capable of performing wide word searches, comprising:
 at least one CAM memory core having a plurality of bit pattern entry rows; 
 search logic capable of searching particular rows during each cycle, the search logic further capable of allowing match line results of unsearched rows to remain unchanged during a cycle; and 
 a serial AND array in communication with the bit pattern entry rows, wherein the serial AND array is capable of computing a match result for wide word entries that span multiple bit pattern entry rows. 
 
     
     
       22. A CAM as recited in  claim 21 , further comprising a match line enable signal that is provided to the serial AND array, the match line enable signal facilitating computation of the match result. 
     
     
       23. A CAM as recited in  claim 22 , wherein the serial AND array includes a plurality of serial AND computational units. 
     
     
       24. A CAM as recited in  claim 23 , wherein each serial AND computational unit is in electrical communication with a bit pattern entry row and the match line enable signal. 
     
     
       25. A CAM as recited in  claim 24 , wherein each serial AND computational unit receives a match line from the corresponding bit pattern entry row and the match line enable signal. 
     
     
       26. A CAM as recited in  claim 25 , further including a plurality of CAM memory cores that are serially coupled. 
     
     
       27. A CAM as recited in  claim 26 , wherein the CAM is capable of storing word entries spanning multiple CAM memory cores. 
     
     
       28. A method of performing word searches, the method comprising:
 storing word entries in at least one content addressable memory (CAM) core having a plurality of bit pattern entry rows;   storing a plurality of word boundary bits in a boundary array, wherein individual ones of the plurality of word boundary bits correspond to individual ones of the plurality of bit pattern entry rows; and   computing a match result for a word entry that spans multiple bit pattern entry rows.    
     
     
       29. The method of claim 28, wherein the computing a match result comprises computing a plurality of match line results for the plurality of bit pattern entry rows.  
     
     
       30. The method of claim 29, wherein the computing a match result comprises determining a beginning and an end the word entry according to the plurality of word boundary bits.  
     
     
       31. The method of claim 30, wherein the computing a match result comprises combining the match line results corresponding to the plurality of bit pattern entry rows of the wide word entry to compute the match result.  
     
     
       32. The method of claim 28, wherein word boundary bits have a value of “1” indicate a beginning of a wide word entry.  
     
     
       33. The method of claim 28, wherein the storing comprises storing word entries in a plurality of CAM cores, wherein the CAM cores are serially coupled.  
     
     
       34. A method, comprising:
 storing word entries in at least one content addressable memory (CAM) core having a plurality of bit pattern entry rows:   computing a plurality of match line results for selected bit pattern entry rows during a search cycle; and   computing a match result for word entries that span multiple bit pattern entry rows.    
     
     
       35. The method of claim 34, wherein match line results for unselected bit pattern entry rows remain unchanged during the search cycle.  
     
     
       36. The method of claim 34, further comprising:
 combining the match line results corresponding to the bit pattern entry rows of word entries to compute the match result.    
     
     
       37. The method of claim 28, wherein the computing a match result is using a serial AND array that is in communication with the plurality of bit pattern entry rows and the plurality of word boundary bits.  
     
     
       38. The method of claim 34, wherein the computing a match result comprises using a serial AND array that is in communication with the plurality of bit pattern entry rows.  
     
     
       39. The method of claim 34, wherein the computing a match result comprises using a match line enable output signal from a match line enable latch.  
     
     
       40. The method of claim 34, further comprising searching only odd rows or only even rows of the plurality of bit pattern entry rows.  
     
     
       41. The method of claim 34, further comprising specifying widths of the word entries using differential width tags.  
     
     
       42. The method of claim 34, further comprising using a first control signal to indicate a beginning of the search cycle and a second control signal to indicate an ending of the search cycle.