Block programmable priority encoder in a cam

Abstract

A priority encoder (PE) for a CAM, comprising a plurality of PE blocks, each receiving a plurality of match results corresponding to data entries in a corresponding data array block and, for determining an address of a highest priority data entry based on a physical location in the data array block during a CAM search-and-compare operation a register for storing a user defined priority value assigned to each PE block and means for evaluating priority values and the address determined by the plurality of PE blocks to select a PE block having the highest priority data entry.

1. A priority encoder for providing a low physical address match data or a high physical address match data as a highest priority match data, the low physical address match data having higher priority than the high physical address match data, comprising:
 a multiplexor for passing the high physical address match data as the highest priority match data in response to a first state of a control signal, the multiplexor passing the low physical address match data in response to a second state of the control signal; 
 logic circuitry for receiving a first priority value corresponding to the low physical address match data and a second priority value corresponding to the high physical address match data, the logic circuitry comparing the first priority value to the second priority value and generating the first state of the control signal if the second priority value is greater than the first priority value. 
 
     
     
       2. The priority encoder of  claim 1 , wherein the low physical address match data and the high physical address match data each include a match address and a match flag. 
     
     
       3. The priority encoder of  claim 2 , wherein the low physical address match data includes the first priority value, and the high physical address match data includes the second priority value. 
     
     
       4. The priority encoder of  claim 1 , wherein the logic circuitry includes a subtractor for subtracting the first priority value from the second priority value, the subtractor generating the control signal if a difference between the second priority value and the first priority value is greater than 0. 
     
     
       5. The priority encoder of  claim 4 , further including a logical AND circuit having a first input for receiving the control signal and a second input for receiving a match flag corresponding to the high physical address match data, the logical AND circuit passing the control signal if the match flag corresponds to a match condition for the high physical address match data. 
     
     
       6. A method for providing a low physical address match data or a high physical address match data as a highest priority match data, the low physical address match data having higher priority than the high physical address match data, comprising:
 a) receiving a first priority value corresponding to the low physical address match data and a second priority value corresponding to the high physical address match data; 
 b) comparing the first priority value to the second priority value; and, 
 c) passing the high physical address match data as the highest priority match data if the second priority value is greater than the first priority value. 
 
     
     
       7. The method of  claim 6 , wherein the step of comparing includes subtracting the first priority value from the second priority value. 
     
     
       8. The method of  claim 7 , wherein the step of comparing further includes generating a control signal when the second priority value is greater than the first priority value. 
     
     
       9. The method of  claim 8 , wherein the step of passing includes passing the high physical address match data in response to the control signal. 
     
     
       10. The method of  claim 9 , wherein the step of generating a control signal includes passing the control signal in response to a logical state of a match flag corresponding to the high physical address match data. 
     
     
       11. The method of  claim 10 , wherein the control signal is passed with the high physical address match data. 
     
     
       12. The method of  claim 6 , wherein the low physical address match data and the high physical address match data each include a match address and a match flag. 
     
     
       13. The method of  claim 6 , wherein the low physical address match data includes the first priority value, and the high physical address match data further includes the second priority value. 
     
     
       14. The priority encoder of claim 1, wherein the logic circuitry generates the second state of the control signal if the second priority value is less than the first priority value. 
     
     
       15. The priority encoder of claim 14, wherein the logic circuitry generates the second state of the control signal if the second priority value is equal to the first priority value. 
     
     
       16. The method of claim 6, further comprising passing the low physical address match data as the highest priority match data if the second priority value is less than the first priority value. 
     
     
       17. The method of claim 16, further comprising passing the low physical address match data as the highest priority match data if the second priority value is equal to the first priority value. 
     
     
       18. A priority encoder for providing a first priority match data or a second priority match data, comprising:
 a multiplexor for passing the first priority match data as the highest priority match data in response to a first state of a control signal and passing the second priority match data in response to a second state of the control signal;   logic circuitry for receiving a first priority match data and a second priority match data, the logic circuitry comparing the first priority match data to the second priority match data and generating the first state of the control signal if the second priority match data is greater than the first match data and generating the second state of the control signal if the second priority match data is less than or equal to the first priority match data.   
     
     
       19. The priority encoder of claim 18, wherein the first priority match data and the second priority match data each include a match address and a match flag. 
     
     
       20. The priority encoder of claim 19, wherein the first priority match data includes the first priority value, and the second priority match data includes the second priority value. 
     
     
       21. The priority encoder of claim 18, wherein the logic circuitry includes a subtractor for subtracting the first priority value from the second priority value, the subtractor generating the first state of the control signal if a difference between the second priority value and the first priority value is greater than 0, the subtractor generating the second state of the control signal if the difference between the second priority value and the first priority value is less than or equal to 0. 
     
     
       22. The priority encoder of claim 21, further including a logical AND circuit having a first input for receiving the control signal and a second input for receiving a match flag corresponding to the second priority match data, the logical AND circuit passing the control signal if the match flag corresponds to a match condition for the second priority match data. 
     
     
       23. A method for providing a first priority match data and a second priority match data, comprising:
 a) receiving a first priority value corresponding to the first priority match data and a second priority value corresponding to the second priority match data;   b) comparing the first priority value to the second priority value;   c) passing the first priority match data as the highest priority match data if the second priority value is greater than the first priority value; and   d) passing the second priority match data as the highest priority match data if the second priority value is less than or equal to the first priority value.   
     
     
       24. The method of claim 23, wherein comparing includes subtracting the first priority value from the second priority value. 
     
     
       25. The method of claim 24, wherein comparing further includes generating a first state of a control signal when the second priority value is greater than the first priority value, and generating a second state of the control signal when the second priority is less than or equal to the first priority value. 
     
     
       26. The method of claim 25, wherein passing includes passing the first priority match data in response to the first state of the control signal. 
     
     
       27. The method of claim 26, further comprising passing the control signal in response to a logical state of a match flag corresponding to the first priority match data. 
     
     
       28. The method of claim 27, wherein the control signal is passed with the first priority match data. 
     
     
       29. The method of claim 23, wherein the first priority match data and the second priority match data each include a match address and a match flag. 
     
     
       30. The method of claim 23, wherein the first priority match data includes the first priority value, and the second priority match data further includes the second priority value. 
     
     
       31. A system comprising:
 a processor; and   a content addressable memory in communication with the processor, the content addressable memory comprising:   at least one memory block; and   a priority encoder having:   a priority register for receiving at least one priority value assigned by the processor; and   logic circuitry for receiving from the at least one memory block a first priority match data and a second priority match data,   the logic circuitry being responsive to the at least one priority value to selectively pass one of the first priority match data and the second priority match data.   
     
     
       32. The system of claim 31, wherein:
 the logic circuitry is responsive to a first state of the at least one priority value to selectively pass the first priority match data; and   the logic circuitry is responsive to a second state of the at least one priority value to selectively pass the second priority match data.   
     
     
       33. The system of claim 31, wherein:
 the at least one priority value comprises:   a first priority value corresponding to the first priority match data; and   a second priority value corresponding to the second priority match data; and   the logic circuitry being responsive to the at least one priority value comprises the logic circuitry being responsive to a difference between the first priority value and the second priority value.   
     
     
       34. The system of claim 33, wherein the first priority match data and the second priority match data each include a match address and a match flag. 
     
     
       35. The system of claim 34, wherein the first priority match data includes the first priority value, and the second priority match data includes the second priority value. 
     
     
       36. The system of claim 33, wherein the logic circuitry includes a subtractor for subtracting the first priority value from the second priority value, the logic circuitry passing the first priority match data if a difference between the second priority value and the first priority value is greater than 0, the logic circuitry passing the second priority match data if the difference between the second priority value and the first priority value is less than 0. 
     
     
       37. A content addressable memory comprising:
 at least one memory block; and   a priority encoder for receiving from the at least one memory block a first priority match data and a second priority match data,   the priority encoder being responsive to at least one user-assigned priority value to select one of the first priority match data and the second priority match data.   
     
     
       38. The content addressable memory of claim 37, wherein:
 the priority encoder is responsive to a first state of the at least one priority value to selectively pass the first priority match data; and   the priority encoder is responsive to a second state of the at least one priority value to selectively pass the second priority match data.   
     
     
       39. The content addressable memory of claim 37, wherein:
 the at least one priority value comprises:   a first priority value corresponding to the first priority match data; and   a second priority value corresponding to the second priority match data; and   the priority encoder being responsive to the at least one priority value comprises the priority encoder being responsive to a difference between the first priority value and the second priority value.   
     
     
       40. The content addressable memory of claim 39, wherein the first priority match data and the second priority match data each include a match address and a match flag. 
     
     
       41. The content addressable memory of claim 40, wherein the first priority match data includes the first priority value, and the second priority match data includes the second priority value. 
     
     
       42. The content addressable memory of claim 39, wherein the priority encoder includes a subtractor for subtracting the first priority value from the second priority value, the priority encoder passing the first priority match data if a difference between the second priority value and the first priority value is greater than 0, the priority encoder passing the second priority match data if the difference between the second priority value and the first priority value is less than 0. 
     
     
       43. A content addressable memory comprising:
 a plurality of data array blocks; and   a plurality of priority encoder blocks for receiving a plurality of match results from respective ones of the data array blocks,   each of the priority encoder blocks containing logic circuitry providing a priority selection algorithm for selecting a highest priority match result from the plurality of received match results based on a user-defined priority.   
     
     
       44. The content addressable memory of claim 43, wherein:
 the logic circuitry is responsive to a first state of the at least one priority value to selectively pass the first priority match data; and   the logic circuitry is responsive to a second state of the at least one priority value to selectively pass the second priority match data.   
     
     
       45. The content addressable memory of claim 43, wherein:
 the at least one priority value comprises:   a first priority value corresponding to the first priority match data; and   a second priority value corresponding to the second priority match data; and   the logic circuitry being responsive to the at least one priority value comprises the logic circuitry being responsive to a difference between the first priority value and the second priority value.   
     
     
       46. The content addressable memory of claim 45, wherein the first priority match data and the second priority match data each include a match address and a match flag. 
     
     
       47. The content addressable memory of claim 46, wherein the first priority match data includes the first priority value, and the second priority match data includes the second priority value. 
     
     
       48. The content addressable memory of claim 45, wherein the logic circuitry includes a subtractor for subtracting the first priority value from the second priority value, the logic circuitry passing the first priority match data if a difference between the second priority value and the first priority value is greater than 0, the logic circuitry passing the second priority match data if the difference between the second priority value and the first priority value is less than 0. 
     
     
       49. A control circuit for a content addressable memory, the control circuit containing logic circuitry operative to:
 a) receive a first priority value corresponding to the first priority match data and a second priority value corresponding to the second priority match data;   b) compare the first priority value to the second priority value;   c) pass the first priority match data as the highest priority match data if the second priority value is greater than the first priority value; and   d) pass the second priority match data as the highest priority match data if the second priority value is less than or equal to the first priority value.   
     
     
       50. The control circuit of claim 49, wherein:
 the logic circuitry is responsive to a first state of the at least one priority value to selectively pass the first priority match data; and   the logic circuitry is responsive to a second state of the at least one priority value to selectively pass the second priority match data.   
     
     
       51. The control circuit of claim 49, wherein:
 the at least one priority value comprises:   a first priority value corresponding to the first priority match data; and   a second priority value corresponding to the second priority match data; and   the logic circuitry being responsive to the at least one priority value comprises the logic circuitry being responsive to a difference between the first priority value and the second priority value.   
     
     
       52. The control circuit of claim 51, wherein the first priority match data and the second priority match data each include a match address and a match flag. 
     
     
       53. The content addressable memory of claim 52, wherein the first priority match data includes the first priority value, and the second priority match data includes the second priority value. 
     
     
       54. The control circuit of claim 51, wherein the logic circuitry includes a subtractor for subtracting the first priority value from the second priority value, the logic circuitry passing the first priority match data if a difference between the second priority value and the first priority value is greater than 0, the logic circuitry passing the second priority match data if the difference between the second priority value and the first priority value is less than 0.