Method and apparatus for cascading content addressable memory devices

• US 6,148,364 A
• Filed: 12/30/1997
• Issued: 11/14/2000
• Est. Priority Date: 12/30/1997
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Nataraj, Bindiganavale S., Khanna, Sandeep, Srinivasan, Varadarajan
• Primary Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US09/001,110
• Time in Patent Office: 1,050 Days
• Field of Search: 380/9, 380/5, 711/108, 365/49, 365/226
• 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
• CPC Class Codes: G11C 15/04 using semiconductor elements

Abstract

A method and apparatus for cascading content addressable memory (CAM) devices is disclosed. The method and apparatus may be particularly useful when depth cascading CAM devices that operate in a flow-through mode. In the flow-through mode, a compare instruction may be simultaneously provided to each CAM device in the cascade, and the match address, data stored at the matched location, or other status information may then be output to a common output data bus by the highest priority matching CAM device in the same cycle that the instruction is provided to the CAM devices. Each CAM device may have a cascade input and a cascade output to perform the cascade function. The cascade output of a higher priority CAM device may be connected to the cascade input of the next lower priority CAM device. The higher priority CAM device may assert a cascade signal on its cascade output at a predetermined time after receiving an input signal (e.g., a clock signal). Asserting the cascade signal may indicate that the higher priority CAM device has completed the compare instruction. When the lower priority CAM device detects that the cascade signal has been asserted on its cascade input, the lower priority CAM device may sample the match flag of the higher priority CAM device to determine if the lower priority CAM device may output its data to the common output data bus.

Claims

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

a CAM circuit for storing data;

data inputs for providing comparand data for comparison with the data of the CAM circuit;

a cascade circuit coupled to the CAM circuit;

a match flag output coupled to the cascade circuit, the match flag output for providing a match flag output signal indicative of whether the comparand data matches the data of the CAM circuit; and

a cascade output coupled to the cascade circuit, the cascade output for providing a cascade output signal indicative of when the match flag output signal is valid.

2. The CAM device of claim 1, further comprising a cascade input coupled to the cascade circuit, the cascade input for receiving a cascade input signal from another CAM device indicative of when the other CAM device has completed a compare operation.

3. The CAM device of claim 2, further comprising a match flag input coupled to the cascade circuit, the match flag input for receiving a match flag input signal from the other CAM device, wherein the cascade input signal from the other CAM device further indicates when the match flag input signal from the other CAM device is valid.

4. The CAM device of claim 3, wherein the CAM circuit outputs an internal match flag signal indicative of whether the comparand data matches the data of the CAM circuit, and wherein the CAM device further comprises match flag output logic coupled to receive the internal match flag signal and coupled to the match flag input, wherein the match flag output logic is configured to generate the match flag output signal in response to the match flag input signal and the internal match flag signal.

5. The CAM device of claim 4, further comprising bus control logic coupled to the CAM circuit, the cascade input, and the match flag input, the bus control logic configured to output an address from the CAM device corresponding to the data of the CAM circuit that matches the comparand, the bus control logic configured to output the address in response to the match flag input signal, the cascade input signal and the internal match flag signal.

6. The CAM device of claim 2, wherein the cascade circuit comprises:

a cascade signal generator configured to output an internal cascade signal in response to an input signal; and

cascade output logic coupled to the cascade signal generator and the cascade input the cascade output logic configured to generate the cascade output signal in response to the internal cascade signal and the cascade input signal.

7. The CAM device of claim 1, further comprising a clock input coupled to the cascade circuit, the clock input for receiving a clock signal.

8. The CAM device of claim 7, wherein the match flag output signal and the cascade output signal are generated by the cascade circuit in a single clock cycle of the clock signal.

9. The CAM device of claim 1, further comprising an instruction decoder coupled to the CAM circuit.

10. The CAM device of claim 9, further comprising a timing generator coupled to the CAM circuit and the instruction decoder.

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

a CAM circuit for storing data;

data inputs for providing comparand data for comparison with the data of the CAM circuit, a cascade circuit coupled to the CAM circuit;

a match flag input coupled to the cascade circuit, the match flag input for receiving a match flag input signal from another CAM device; and

a cascade out coupled to the cascade circuit, the cascade input for receiving a cascade input signal from the other CAM device indicative of when the match flag input signal from the other CAM device is valid.

12. The CAM device of claim 11, wherein the cascade circuit is further configured to generate a match flag output signal indicative of whether the comparand data matches the data of the CAM circuit.

13. The CAM device of claim 12, wherein the cascade circuit is further configured to generate a cascade output signal that indicates when the match flag output signal is valid.

14. The CAM device of claim 12 a clock input coupled to the cascade circuit and the CAM circuit, the clock input for receiving a clock signal, wherein the cascade output signal and the match flag output are generated by the cascade circuit in a single cycle of the clock signal.

15. The CAM device of claim 11, wherein the cascade circuitry comprises:

a cascade signal generator configured to output an internal cascade signal in response to an input signal; and

cascade output logic coupled to the cascade signal generator, the cascade output logic configured to generate the cascade output signal in response to the internal cascade signal and a cascade input signal to the CAM device.

16. The CAM device of claim 15, wherein the the cascade signal generator comprises a one-shot circuit.

17. The CAM device of claim 11, further comprising bus control logic coupled to the CAM circuit, the cascade input, and the match flag input, the bus control logic configured to output an address from the CAM device corresponding to the data of the CAM circuit that matches the comparand, the bus control logic configured to output the address in response to the match flag input signal, the cascade input signal and the internal match flag signal.

18. A system comprising:

a first content addressable memory (CAM) device having a cascade output and a match flag output, the match flag output for providing a match flag output signal indicative of whether comparand data matches data of the first CAM device, the cascade output for providing a cascade output signal indicative of when the match flag output signal is valid; and

a second content addressable memory (CAM) device coupled in a depth cascade configuration with the first CAM device, the second CAM device having a cascade input, a match flag input, and a cascade output, the cascade input of the second CAM device coupled to the cascade output of the first CAM device, the match flag input of the second CAM device coupled to the match flag output of the first CAM device.

19. The system of claim 18, wherein the system is incorporated into an integrated circuit.

20. The system of claim 18, wherein the second CAM device is configured to assert a cascade output signal to a logic state on its cascade output a predetermined amount of time after it receives at its cascade input the cascade output signal from the first CAM device asserted to the logic state.

21. The system of claim 20, wherein the first and second CAM device each have data outputs coupled to a common data output bus.

22. The CAM device of claim 21, wherein the cascade signal generator comprises a one-shot circuit.

23. The system of claim 21, wherein each CAM has data inputs coupled to a common data input bus, and wherein each CAM device is configured to simultaneously determine whether the comparand data provided on the data input bus data matches data of the respective CAM device.

24. The system of claim 23, wherein the second CAM device is configured to outputs its address of the matching data to the common data output bus if the first CAM device does not have a match.

25. The system of claim 24, wherein the second CAM device is configured to determine whether the comparand data provided on the data input bus data matches data of the CAM device in the same clock cycle of the clock signal that the second CAM is configured to outputs its address of the matching data to the common data output bus.

26. A method of depth cascading first and second content addressable memory (CAM) devices comprising:

instructing the first and second CAM devices to execute a compare operation between comparand data and first data stored in the first CAM device and second data stored in the second CAM device;

providing a match flag signal from the first CAM device to the second CAM device, the match flag signal indicating whether the comparand data matches the first data; and

providing a cascade output signal from the first CAM device to the second CAM device, the cascade output signal indicating when the the match flag signal is valid for sampling by the second CAM device.

27. The method of claim 26, wherein the first and second memory devices have outputs coupled to a common output bus, and further comprising only the first CAM device outputting data to the common output bus when the comparand data matches the first data.

28. The method of claim 27, wherein the method is performed by the CAM devices in one clock cycle.

29. The method of claim 27, further comprising only the second CAM device outputting data to the common output bus when the comparand data matches the second data stored and does not match the first data.

30. The method of claim 29, wherein the method is performed in one clock cycle.

31. A method of operating a content addressable memory (CAM) device comprising:

instructing the CAM device to execute a compare operation between comparand data and data stored in the CAM device;

generating a match flag signal from the CAM device, the match flag signal indicatative of whether the comparand data matches the data stored in the CAM device; and

generating an output signal from the CAM device, the output signal indicating when the the match flag signal is valid.