Method and apparatus for implementing a learn instruction in a depth cascaded content addressable memory system

• US 6,240,485 B1
• Filed: 05/11/1998
• Issued: 05/29/2001
• Est. Priority Date: 05/11/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Nataraj, Bindiganavale S., Khanna, Sandeep, Srinivasan, Varadarajan
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US09/076,336
• Time in Patent Office: 1,114 Days
• Field of Search: 711/5, 711/108, 711/101, 711/128, 365/49
• 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 implementing a LEARN instruction in a depth cascaded content address memory (CAM) system. Each CAM device in the CAM system may include a CAM array, an input coupled to the CAM array and configured to receive comparand data to be compared with data stored in the CAM array, circuitry coupled to the CAM array and configured to write the comparand data into the CAM array if the comparand data does not match the data stored in the CAM array, and cascade logic coupled to the circuitry and configured to receive a plurality of match flag input signals, the cascade logic configured to disable the circuitry from writing the comparand data into the CAM array if the comparand data matches the data stored in the CAM array. Each CAM device may have a match flag input pin and output pin coupled to a match flag output pin and input pin, respectively, of the previous device and next device in the depth cascaded CAM system. Each CAM device may further include a cascade input pin and output pin coupled to a cascade output pin and input pin, respectively, of the previous device and next device in the depth cascaded CAM system.

Claims

1. A content address memory (CAM) device comprising.

a CAM array;

an input coupled to the CAM array and configured to receive comparand data to be compared with data stored in the CAM array;

an instruction decoder coupled to the CAM array and configured to receive and decode an instruction instructing the CAM device to compare the comparand data with the data stored in the CAM array and write the comparand data into an available location in the CAM array if there is no match;

circuitry coupled to the CAM array and the instruction decoder and configured to write the comparand data into the CAM array; and

cascade logic coupled to the instruction decoder and having first inputs to receive a plurality of match flag input signals from other CAM devices.

2. The CAM device of claim 1, wherein when one of the match flag input signals is asserted the cascade logic is configured to communicate with the instruction decoder to override the instruction such that the comparand data is not written in the CAM array when it does not match the data stored therein.

3. The CAM device of claim 1, wherein the cascade logic further includes second inputs to receive a plurality of cascade input signals from the other CAM devices, wherein the cascade input signals are timing signals that indicate when one of the corresponding match flag input signals is valid.

4. The CAM device of claim 3, wherein the cascade logic comprises cascade output logic coupled to the second inputs and having outputs to provide a plurality of cascade output signals to the other CAM devices, wherein each cascade output signal is asserted a predetermined amount of time after a corresponding cascade input signal is asserted.

5. The CAM device of claim 3, wherein the cascade logic comprises match flag validation logic having outputs to provide a plurality of validated match flag signals in response to the plurality of match flag input signals and cascade input signals.

6. The CAM device of claim 4, further comprising a signal generator having an output to provide a timing signal.

7. The CAM device of claim 6, wherein the cascade output logic comprises:

a first cascade output circuit having an output to provide a first cascade output signal to one of the other CAM devices in response to the timing signal and a first one of the cascade input signals; and

a second cascade output circuit having an output to provide a second cascade output signal to another one of the other CAM devices in response to the timing signal and a second one of the cascade input signals.

8. The CAM device of claim 5, wherein the match flag validation logic comprises:

a first match flag validation circuit having an output to provide a first validated match flag signal to one of the other CAM devices in response to a first one of match flag input signals and a first one of the cascade input signals; and

a second match flag validation circuit having an output to provide a second validated match flag signal to another one of the other CAM devices in response to a second one of match flag input signals and a second one of the cascade input signals.

9. The CAM device of claim 5, further comprising an output bus coupled to the cascade logic and the CAM array, the CAM device providing to the output bus an address in the CAM device to which the comparand data is written.

12. The CAM device of claim 1, wherein the cascade logic comprises match flag output logic configured to generate a plurality of match flag output signals to the other CAM devices in response to the plurality of match flag input signals and an internal match flag signal, wherein the internal match flag signal indicates whether the comparand data matches the data stored in the CAM array.

13. The CAM device of claim 8, wherein the match flag output logic comprises:

a first match flag output circuit having an output to provide a first match flag output signal to one of the other CAM devices in response to a first one of match flag input signs and the internal match flag signal; and

a second match flag output circuit having an output to provide a second match flag output signal to another one of the other CAM devices in response to a second one of match flag input signals and the internal match flag signal.

14. The CAM device of claim 1, wherein the circuitry comprises:

a timing generator coupled to the instruction decoder and the CAM way,

a write circuit coupled to the timing generator; and

a storage element for storing an address of the CAM array at which the comparand data is written when the comparand data does not match the data stored in the CAM array.

15. The CAM device of claim 1, wherein the cascade logic comprises:

second inputs to receive a plurality of cascade input signals from the other CAM devices, wherein the cascade input signals indicate when one of the corresponding match flag input signals is valid;

a signal generator having an output to provide a timing signal;

cascade output logic coupled to the second inputs and the signal generator, the cascade output logic having outputs to provide a plurality of cascade output signals to the other CAM devices in response to the cascade input signals and the timing signal, wherein each cascade output signal is provided a predetermined amount of time after a corresponding cascade input signal is asserted;

match flag validation logic having outputs to provide a plurality of validated match flag signals in response to the plurality of match flag input signals and the plurality of cascade input signals; and

match flag output logic configured to generate a plurality of match flag output signals to the other CAM devices in response to the plurality of match flag input signals and an internal match flag signal, wherein the internal match flag signal indicates whether the comparand data matches the data stored in the CAM array.

16. The CAM device of claim 15, wherein the cascade logic further comprises bus control logic coupled to the match flag validation logic, the bus control logic configured to enable an address in the CAM array to which the comparand data is written to be output from the CAM device in response to the plurality of validated match flag signals and the internal match flag signal.

10. The CAM device of 9, wherein the cascade logic further comprises bus control logic coupled to the match flag validation logic, the bus control logic configured to enable the address to be provided to the output bus in response to the plurality of validated match flag signals and an internal match flag signal, wherein the internal match flag signal indicates whether the comparand data matches the data stored in the CAM array.

11. The CAM device of claim 10, wherein the bus control logic further includes an input for receiving a signal indicative of whether the CAM array is full.

17. A system comprising:

a first content addressable memory (CAM) device comprising a match flag input pin and a match flag output pin; and

a second CAM device comprising a match flag output pin coupled to the match flag input pin of the first CAM device, and a match flag input pin coupled to the match flag output pin of the first CAM device.

18. The system of claim 17, wherein:

the first CAM device further comprises a cascade input pin and a cascade output pin; and

the second CAM device further comprises a cascade output pin coupled to the cascade input pin of the first CAM device, and a cascade input pin coupled to the cascade output pin of the first CAM device.

19. The system of claim 17, wherein the first and second CAM devices each comprise a CAM array, and wherein the first and second CAM devices are each configured to receive a LEARN instruction and comparand data, wherein the LEARN instruction instructs each CAM device to compare the comparand data with data stored in its CAM array and to load the comparand data into an available location in one of the CAM arrays if there is no match with the data stored in the CAM arrays of the CAM devices.

20. The system of claim 19, wherein the first CAM device is a synchronous CAM device configured to receive a clock signal, and the first CAM device performs the LEARN instruction in less than three clock cycles of the clock signal.

21. The system of claim 20, wherein the LEARN instruction further instructs the CAM device to output the address of the available location.

22. The system of claim 19, wherein the second CAM device loads the comparand data into an available location in its CAM array if there is no match with the data stored in the CAM arrays of the CAM devices and there is no available location for the comparand data to be stored in the first CAM device.

23. The system of claim 22, wherein the second CAM device is a synchronous CAM device configured to receive a clock signal, and the second CAM device performs the LEARN instruction in less than three clock cycles of the clock signal.

24. The system of claim 23, wherein the LEARN instruction further instructs the CAM device to output the address of the available location.

25. The system of claim 17, wherein each CAM device comprises:

a CAM array;

an input coupled to the CAM array and configured to receive comparand data to be compared with data stored in the CAM array;

an instruction decoder coupled to the CAM array and configured to receive and decode an instruction instructing the CAM device to compare the comparand data with the data stored in the CAM array and write the comparand data into an available location in the CAM array if there is no match;

circuitry coupled to the CAM array and the instruction decoder and configured to write the comparand data into the CAM array; and

cascade logic coupled to the instruction decoder, the match flag input pin, and the match flag output pin.

26. A method of performing a LEARN instruction in a depth cascade content addressable memory (CAM) system having a first CAM device coupled to a second CAM device each having a CAM array, wherein the first CAM device has higher priority addresses for its CAM array than the second CAM device, the method comprising:

providing a LEARN instruction and comparand data to the first and second CAM devices;

decoding the LEARN instruction in each device, and in response thereto;

comparing the comparand data with data stored in the CAM array of each CAM device; and

writing the comparand data into an available location in the second CAM device if neither CAM device has data matching the comparand data and the first CAM device is full.

27. The method of claim 26, further comprising:

generating a first match flag output signal from the first CAM device in response to the comparing step;

providing the first match flag output signal to the second CAM device;

generating a second match flag output signal from the second device in response to the comparing step; and

providing the second match flag output signal to the first CAM device.

28. The method of claim 27, further comprising:

generating a first cascade output signal from the first CAM device in response to the comparing step;

providing the first cascade output signal to the second CAM device to indicate when the first match flag signal is valid;

generating a second cascade output signal from the second device in response to the comparing step; and

providing the second cascade output signal to the first CAM device to indicate when the second match flag signal is valid.

29. The method of claim 28, further comprising outputting the address of the available location in the CAM array of the second CAM device after the writing step.

30. A content address memory (CAM) device comprising:

a CAM array;

an input coupled to the CAM array and configured to receive comparand data to be compared with data stored in the CAM array;

circuitry coupled to the CAM array and configured to write the comparand data into the CAM array if the comparand data does not match the data stored in the CAM array; and

cascade logic coupled to the circuitry and configured to receive a plurality of match flag input signals and a plurality of cascade input signals, the cascade logic configured to disable the circuitry from writing the comparand data into the CAM array, the cascade logic comprising bus control logic and match flag validation logic that generates a plurality of validated match flag signals in response to the plurality of match flag input signals and the cascade input signals;

an output bus coupled to the cascade logic and the CAM array, the CAM device providing to the output bus an address in the CAM device to which the compared data is written, the bus control logic configured to enable the address to be provided to the output bus in response to the plurality of validated match flag signals and an internal match flag signal, wherein the internal match flag signal indicates whether the comparand data matches the data stored in the CAM array.