Method and apparatus for implementing a learn instruction in a content addressable memory device

• US 6,219,748 B1
• Filed: 05/11/1998
• Issued: 04/17/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): Yoo, Do Hyun
• Assistant Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US09/076,337
• Time in Patent Office: 1,072 Days
• Field of Search: 711/101, 711/1-5, 711/104-108, 711/150-152, 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 content address memory (CAM) device that implements a “LEARN” instruction. In response to the LEARN instruction, the CAM device compares comparand data with data stored in a CAM array of the CAM device. If a match is not found, the comparand data is written into the CAM array. For one example, the comparand data is written to the next free address of the CAM array. The learn instruction may further cause the CAM device to output the next free address after the comparand data has been written into the CAM array. For one embodiment, the learn instruction may be implemented in a single clock cycle.

Claims

1. A method of updating a synchronous CAM device, comprising:

instructing the CAM device to compare comparand data with data stored in a CAM array in the CAM device;

writing the comparand data as invalid data to a location in the CAM array;

comparing the comparand data with valid data stored in the CAM array; and

subsequently validating the comparand data written into the CAM array if the comparand data does not match the valid data stored in the CAM array.

2. The method of claim 1, wherein the instructing, writing, comparing and validating occur in one clock cycle.

3. The method of claim 1, wherein the writing comprises writing the comparand data to an empty location in the CAM array.

4. The method of claim 1, wherein the writing comprises writing the comparand data to a next free location in the CAM array.

5. The method of claim 1, further comprising outputting an address of the location in the CAM array.

6. The method of claim 5, wherein the instructing, writing, comparing, validating, and outputting occur in less than four clock cycles.

7. The method of claim 6, wherein the instructing, writing, comparing, validating, and outputting occur in one clock cycle.

8. The method of claim 1, further comprising determining if the CAM array is full prior to writing the comparand data into the CAM array.

9. The method of claim 1, further comprising asserting a flag signal when the valdiating is complete.

10. A method of updating a content addressable memory (CAM) device comprising:

providing an instruction to an instruction decoder within the CAM device;

decoding the single instruction and in response thereto;

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

writing the comparand data to a location in the CAM array.

11. The method of claim 10, wherein the writing further comprises writing the comparand data to the location in the CAM array if the comparand data does not match the data stored in the CAM array.

12. The method of claim 10, further comprising outputting an address of the location in the CAM array.

13. The method of claim 10, wherein the CAM device is a synchronous CAM device and the instruction is performed by the CAM device in less than four clock cycles.

14. The method of claim 10, wherein the CAM device is a synchronous CAM device and the instruction is performed by the CAM device in one clock cycle.

15. The method of claim 10, wherein the location in the CAM array is an empty location.

16. The method of claim 10, wherein the location in the CAM array is a next free location.

17. The method of claim 10, wherein the writing occurs before the comparing.

18. The method of claim 17, wherein the comparand data is marked as invalid for the writing, and the method further comprises validating the written comparand data if the comparand data does not match the data stored in the CAM array.

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

a CAM array having a plurality of CAM cells for storing data;

an input for receiving comparand data; and

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.

20. The CAM device of claim 19, further comprising an output to provide a flag signal indicative of when the instruction is completed.

21. The CAM device of claim 19, wherein the CAM device is a synchronous CAM device and includes an input for receiving a clock signal.

22. The CAM device of claim 21, wherein the CAM device is configured to execute the instruction in less than four clock cycles.

23. The CAM device of claim 21, wherein the CAM device is configured to execute the instruction in a single clock cycle.

24. The CAM device of claim 19, further comprising a write circuit coupled to the CAM array and configured to write the comparand data into the available location in the CAM array.

25. The CAM device of claim 24, further comprising a storage element configured to store the address of the available location in the CAM array.

26. The CAM device of claim 25, further comprising circuitry coupled to the CAM array and configured to generate a match flag signal, wherein the match flag signal indicates if there is a match between the comparand data and the data stored in the CAM array.

27. The CAM device of claim 24, further comprising full flag logic coupled to the CAM array to generate a full flag signal indicating if the CAM array is full.

28. The CAM device of claim 27, wherein the instruction decoder enables the comparand data to be written into the available location of the CAM address if (i) the match flag indicates that the comparand data does not match data stored in the CAM array, and (ii) the full flag signal indicates that the CAM array is not full.

29. The CAM device of claim 28, further comprising a timing generator coupled to the instruction decoder, the write circuit and the storage element, wherein the timing generator outputs a plurality of signals to the storage element and the write circuit in response to the decoding of the instruction by the instruction decoder.

30. The CAM device of claim 29, wherein the timing generator is configured to provide a first timing signal to the write circuit to write the comparand data into the CAM array before the comparand data is compared with the data stored in the CAM array.

31. The CAM device of claim 30, wherein each location in the CAM array has at least one corresponding memory element for storing an indication of whether the data stored at the corresponding location is valid, and wherein the timing generator is configured to provide a second timing signal to the write circuit to write a valid bit into the memory element for the location in the CAM array of the comparand data if the comparand data does not match the other data stored in the CAM array.

32. The CAM device of claim 28, further comprising a signal generator coupled to the instruction decoder to provide a sampling signal for sampling when the match flag signal is valid.

33. The CAM device of claim 28, wherein the instruction decoder comprises a pulse generator coupled to receive the match flag signal and the full flag signal and output a pulse signal to the timing generator.

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

a CAM array having a plurality of CAM cells for storing data and comparing valid data with comparand data;

means for decoding an instruction instructing the device to compare the comparand data with data stored in the CAM array;

means for writing the comparand data into the CAM array as invalid data; and

means for validating the comparand data in the CAM array when there is no match between the comparand data and the data stored in the CAM array.

35. The CAM device of claim 34, further comprising means for generating a flag signal indicative of when the instruction has been executed by the CAM device.

36. The CAM device of claim 34, further comprising means for outputting from the CAM device the address of where the comparand data is written.

37. The CAM device of claim 34, wherein the CAM device is a synchronous CAM device and includes means for receiving a clock signal.

38. The CAM device of claim 37, wherein the instruction is executed by the CAM device in less than four clock cycles of the clock signal.

39. The CAM device of claim 37, wherein the instruction is executed by the CAM device is a single clock cycle of the clock signal.