Content addressable memory device having selective cascade logic and method for selectively combining match information in a CAM device

• US 6,493,793 B1
• Filed: 06/16/2000
• Issued: 12/10/2002
• Est. Priority Date: 06/16/2000
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Srinivasan, Varadarajan, Pereira, Jose Pio
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US09/595,773
• Time in Patent Office: 907 Days
• Field of Search: 711/108, 711/5, 365/49, 365/230.03
• US Class Current: 711/108
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

A content addressable memory (CAM) device having an array including a plurality of rows of CAM cells each coupled to a match line; match flag logic having inputs coupled to the match line, and having an output to provide an internal match flag signal indicative of match conditions between a comparand word and data stored in the array; a plurality of match flag inputs to receive input match information from one or more other CAM devices; a match flag output to provide output match information to one or more other CAM devices; and cascade logic coupled to the plurality of match flag inputs and the match flag output for selecting which input match information received from the match flag inputs is logically combined with the internal match flag to generate the output match information.

Claims

1. A content addressable memory (CAM) device comprising:

an array including a plurality of rows of CAM cells each coupled to a match line;

match flag logic having inputs coupled to the match lines, and having an output to provide an internal match flag signal indicative of match conditions between a comparand word and data stored in the array;

a plurality of match flag inputs to receive input match information from one or more other CAM devices;

a match flag output to provide output match information to one or more other CAM devices; and

cascade logic coupled to the plurality of match flag inputs and the match flag output for selecting which input match information received from the match flag inputs is logically combined with the internal match flag to generate the output match information.

2. The CAM device of claim 1, wherein the cascade logic further comprises means for forcing the output match information to a mismatch state regardless of the match conditions.

3. The CAM device of claim 1, wherein the cascade logic has an output for providing a first enable signal.

4. The CAM device of claim 3, further comprising:

a priority encoder having inputs coupled to the match lines, and having outputs to provide a match address; and

an output buffer having first inputs coupled to receive the match address from the priority encoder, a second input coupled to receive the first enable signal from the cascade logic and outputs to selectively output the match address from the CAM device in response to the first enable signal.

5. The CAM device of claim 4, wherein the cascade logic further comprises means for generating a second enable signal, wherein the first enable signal is gated by the second enable signal.

6. The CAM device of claim 5, wherein the means for generating the second enable signal comprises a pulse circuit.

7. The CAM device of claim 5, wherein the means for generating the second enable signal comprises a programmable delay circuit.

8. The CAM device of claim 5, wherein the means for generating the second enable signal comprises:

a memory circuit; and

a programmable pulse circuit coupled to the memory circuit.

9. The CAM device of claim 1, wherein the input match information includes one or more input match flags indicative of match conditions in one or more other CAM devices.

10. The CAM device of claim 9, wherein the cascade logic comprises:

a memory element to store one or more select values; and

one or more first logic circuits each having a first input coupled to receive a corresponding input match flag, a second input coupled to receive a corresponding select value, and an output to selectively provide the corresponding input match flag in response to the corresponding select value.

11. The CAM device of claim 10, wherein the cascade logic further comprises:

a second logic circuit having one or more first inputs coupled to the outputs of the one or more first logic circuits, a second input coupled to receive the internal match flag, and an output to provide the output match information.

12. The CAM device of claim 11, wherein the first logic circuits comprise AND logic gates, and the second logic circuit comprises an OR logic gate.

13. The CAM device of claim 11, wherein the cascade logic further comprises:

a third logic circuit having one or more first inputs coupled to receive the one or more input match flags, a second input coupled to receive the internal match flag, and an output to generate an enable signal.

14. The CAM device of claim 10, wherein the memory element comprises a look-up table having a plurality of rows for storing the one or more select values.

15. The CAM device of claim 14, wherein a first row comprises a first portion for storing a device identification (ID) of the CAM device and a second portion for storing a first one of the select values corresponding to the CAM device, and a second row comprises a first portion for storing a device ID of one of the other CAM devices and a second portion for storing a second one of the select values corresponding to the one of the other CAM devices.

16. The CAM device of claim 15, wherein the device ID of the CAM device indicates priority relative to the device ID of the one of the other CAM devices.

17. A content addressable memory (CAM) device comprising:

an array including a plurality of rows of CAM cells each coupled to a match line;

match flag logic having inputs coupled to the match lines, and having an output to provide an internal match flag signal indicative of match conditions between a comparand word and data stored in the array;

one or more match flag inputs to receive input match information from one or more other CAM devices;

a match flag output to provide output match information to one or more other CAM devices; and

programmable cascade logic coupled to the one or more match flag inputs and the match flag output.

18. The CAM device of claim 17, wherein the programmable cascade logic further comprises means for forcing the output match information to a mismatch state.

19. The CAM device of claim 17, wherein the programmable cascade logic comprises means for determining when to allow a logical combination of the input match information and the internal match flag signal to assert an output enable signal.

20. The CAM device of claim 17, wherein the programmable cascade logic has an output for providing a first enable signal.

21. The CAM device of claim 20, further comprising:

a priority encoder having inputs coupled to the match lines, and having outputs to provide a match address; and

an output buffer having first inputs coupled to receive the match address from the priority encoder, a second input coupled to receive the first enable signal from the programmable cascade logic and outputs to selectively output the match address from the CAM device in response to the first enable signal.

22. The CAM device of claim 21, wherein the programmable cascade logic comprises means for determining when to assert the first enable signal.

23. The CAM device of claim 21, wherein the programmable cascade logic further comprises means for generating a second enable signal, wherein the first enable signal is gated by the second enable signal.

24. The CAM device of claim 23, wherein the means for generating the second enable signal comprises a programmable delay circuit.

25. The CAM device of claim 23, wherein the means for generating the second enable signal comprises:

a memory circuit; and

a programmable pulse circuit coupled to the memory circuit.

26. A method for selectively combining match information in a content addressable memory (CAM) device, the method comprising:

generating an internal match flag indicative of match conditions in the CAM device;

receiving input match information from one or more other CAM devices;

storing one or more select values in the CAM device; and

selectively enabling, in response to the one or more select values, the input match information to be logically combined with the internal match flag to generate output match information.

27. The method of claim 26, wherein the input match information includes one or more input match flags received from one or more other corresponding CAM devices, the selectively enabling comprising, for each input match flag:

combining the input match flag with the internal match flag to generate the output match information if the corresponding select value is in a first state; and

providing the internal match flag as the output match information if the corresponding select value is in a second state.

28. The method of claim 26, further comprising:

determining an address of a CAM row in the CAM device that stores data matching a comparand word; and

outputting the match address from the CAM device only after the output match information from other CAM devices has been resolved.

29. The method of claim 28, further comprising:

programming when to output the match address.

30. A method for selectively combining match information in one or more of a plurality of content addressable memory (CAM) devices, the method comprising:

generating an internal match flag indicative of match conditions in a corresponding CAM device;

receiving input match information from another CAM device;

storing a select value;

combining the input match information with the internal match flag to generate output match information if the select value is in a first state; and

providing the internal match flag as the output match information, and ignoring the input match information, if the select value is in a second state.

31. The method of claim 30, further comprising asserting the select value for the corresponding CAM device to the second state only when (i) the input match information is provided to a lower-priority CAM device other than the corresponding CAM device and (ii) the next immediate lower-priority CAM device does not receive input match information from all higher-priority CAM devices other than the corresponding CAM device.

32. A content addressable memory (CAM) device comprising:

an array including a plurality of rows of CAM cells each coupled to a match line;

match flag logic having inputs coupled to the match lines, and having an output to provide an internal match flag signal indicative of match conditions between a comparand word and data stored in the array;

one or more match flag inputs to receive one or more input match flags indicative of match conditions in one or more other CAM devices;

a match flag output to provide output match information to one or more other CAM devices; and

cascade logic coupled to the one or more match flag inputs and the match flag output for selectively enabling the one or more input match flags on the one or more match flag inputs to be logically combined with the internal match flag to generate the output match information, the cascade logic comprising;

a memory element to store one or more select values; and

one or more first logic circuits each having a first input to receive a corresponding input match flag, a second input to receive a corresponding select value, and an output to selectively provide the corresponding input match flag in response to the corresponding select value.

33. The CAM device of claim 32, wherein the cascade logic further comprises:

a second logic circuit having one or more first inputs coupled to the outputs of the one or more first logic circuits, a second input to receive the internal match flag, and an output to provide the output match information.

34. The CAM device of claim 33, wherein the first logic circuits comprise AND logic gates, and the second logic circuit comprises an OR logic gate.

35. The CAM device of claim 33, wherein the cascade logic further comprises:

a third logic circuit having one or more first inputs to receive the one or more input match flags, a second input to receive the internal match flag, and an output to generate an enable signal.

36. The CAM device of claim 32, wherein the memory element comprises a look-up table having a plurality of rows each for storing the one or more select values for a corresponding CAM device.

37. The CAM device of claim 36, wherein each row comprises a first portion for storing a device identification (ID) of the corresponding CAM device and a second portion for storing the one or more select values for the corresponding CAM device.

38. The CAM device of claim 37, wherein each device ID indicates priority for the corresponding CAM device relative to another CAM device.

39. A content addressable memory (CAM) device comprising:

an array including a plurality of rows of CAM cells each coupled to a match line;

match flag logic having inputs coupled to the match lines, and having an output to provide an internal match flag signal indicative of match conditions between a comparand word and data stored in the array;

a plurality of match flag inputs to receive input match information from other CAM devices;

a match flag output to provide output match information to one or more other CAM devices; and

cascade logic coupled to the plurality of match flag inputs and the match flag output, the cascade logic comprising;

means for storing a plurality of select values, each corresponding to one of the match flag inputs; and

means for selectively combining the input match information with the internal match flag in response to the plurality of select values to generate the output match information.

40. The CAM device of claim 39, wherein the cascade logic further comprises:

means for combining the input match information with the internal match flag to generate an enable signal that allows access to a common output bus.