Method and apparatus for performing a read next highest priority match instruction in a content addressable memory device

• US 6,381,673 B1
• Filed: 07/06/1998
• Issued: 04/30/2002
• Est. Priority Date: 07/06/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): GOODARZI, NASSER MOAZZAMI
• Application Number:
  US09/111,364
• Time in Patent Office: 1,394 Days
• Field of Search: 711/108, 380/9, 380/50, 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

Abstract

A content address memory (CAM) device that implements a read next highest priority or “RNHPM” instruction. The CAM device initially searches its CAM locations for a match with comparand data. If multiple matches are identified, then the CAM device initially outputs the highest priority matching address. The CAM device may output the highest priority matching address in the same system or a later clock cycle in which the compare instruction was provided. The CAM device may also output data stored in one or more of the CAM cells located at the highest priority matching location and/or status information including the match flags, a full flag, validity bits (e.g., skip and empty bits), and other status information. An RNHPM instruction may then be provided to the CAM device in the next clock cycle or a later clock cycle and cause the next highest priority matching address to be output by the CAM device. The next highest priority matching address may be output in the same or subsequent cycle as the RNHPM instruction and may also cause the CAM device to output data stored in one or more of the CAM cells located at the next highest priority matching location and/or status information for that location. RNHPM instructions can continue, to be supplied to the CAM device until no further matching locations are detected.

Claims

1. A method of determining the next highest priority matching location in a content addressable memory (CAM) device, comprising:

comparing comparand data with data stored in a plurality of rows of first CAM cells to determine match results;

determining the highest priority row of CAM cells that stores data matching the comparand data;

updating data stored in a plurality of second CAM cells in response to the match results, each of the second CAM cells associated with one of the corresponding rows of CAM cells; and

comparing the data stored in only the second CAM cells with a predetermined logic state to determine the next highest priority row of CAM cells that stores data matching the comparand data.

2. The method of claim 1, wherein the comparing the comparand data, updating, and determining occur in response to a first instruction supplied to the CAM device.

3. The method of claim 2, wherein the first instruction is completed in a single clock cycle.

4. The method of claim 2, wherein the comparing the data stored in only the second CAM cells occurs in response to a second instruction supplied to the CAM device.

5. The method of claim 4, wherein the second instruction is completed in a single clock cycle.

6. The method of claim 1, wherein the updating comprises:

writing a first logic state to the second CAM cell associated with the highest priority row of CAM cells that stores data that matches the comparand data, wherein the first logic state is indicative of a mismatch state; and

writing a second logic state to the second CAM cells associated with lower priority rows of CAM cells that store data that match the comparand data, wherein the second logic state is indicative of a match state.

7. The method of claim 6, wherein the comparing comprises comparing the data stored in the second CAM cells with the second logic state to determine the next highest priority row of CAM cells that stores data that matches the comparand data.

8. The method of claim 7, further comprising writing the first logic state to the second CAM cell associated with the next highest priority row of CAM cells that stores data that matches the comparand data.

9. The method of claim 1, wherein the updating comprises:

writing a first logic state to the second CAM cells associated with the rows of CAM cells that each store data that matches the comparand data; and

subsequently writing a second logic state to the second CAM cell associated with the highest priority row of CAM cells that stores data that matches the comparand data.

10. The method of claim 1, wherein the determining comprises determining the address of the highest priority row of CAM cells that stores data that matches the comparand data.

11. The method of claim 10, further comprising:

decoding the address of the highest priority row of CAM cells that stores data that matches to the comparand data; and

selecting the second CAM cell associated with the highest priority row of CAM cells that stores data that matches the comparand data.

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

a CAM array having a plurality of rows each having (1) a plurality of first CAM cells coupled to a match line and a first word line, a (2) a second CAM cell coupled to the match line and a second word line, the second CAM cell for storing match results between comparand data and data stored in the first CAM cells, and (3) control logic coupled to the first word line, the match line, and the second word line, the control logic to control access to the second CAM cell;

a write circuit coupled to each of the second CAM cells, the write circuit to provide data to be written into each of the second CAM cells;

an encoder coupled to the match lines; and

a decoder coupled to the encoder and the first word lines.

13. The CAM device of claim 12, further comprising a comparand storage element coupled to the plurality of rows of CAM cells, the comparand storage element for storing comparand data to be compared with data stored in the plurality of rows.

14. The CAM device of claim 12, further comprising a storage element coupled between the match lines and the control logic.

15. The CAM device of claim 12, further comprising an instruction decoder coupled to the write circuit.

16. The CAM device of claim 15, further comprising cascade logic coupled to the instruction decoder, the cascade logic configured to inhibit evaluation of data stored in the second CAM cells in response to a match flag input signal and a multiple match flag input signal to the CAM device.

17. The CAM device of claim 13, further comprising:

an instruction decoder coupled to the write circuit; and

a timing generator coupled to the instruction decoder and the comparand storage element.

18. The CAM device of claim 12, wherein the control logic comprises:

a first logic circuit having a first input coupled to receive the first word line, a second input coupled to receive the match lines, and an output; and

a second logic circuit having a first input coupled to receive a control signal, a second input coupled to the output of the first logic circuit, and an output coupled to the second word line.

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

means for comparing comparand data with data stored in a plurality of rows of first CAM cells to determine match results for each row;

means for determining the highest priority row of CAM cells that stores data that matches the comparand data;

means for updating data stored in a plurality of second CAM cells in response to the match results, each of the second CAM cells associated with a corresponding one of the rows of first CAM cells; and

means for comparing the data stored in the second CAM cells with a predetermined logic state to determine the next highest priority row of CAM cells that stores data that matches the comparand data.

20. The CAM device of claim 19, wherein the means for updating comprises:

means for writing a first logic state the second CAM cell associated with the highest priority row of CAM cells that stores data that matches the comparand data, the first logic state indicative of a mismatch state; and

means for writing a second logic state the second CAM cells associated with lower priority rows of CAM that store data that match the comparand data, the second logic state indicative of a match state.

21. The CAM device of claim 20, wherein the means for comparing the data stored in the second CAM cells comprises means for comparing the data stored in the second CAM cells with the second logic state to determine the next highest priority row of CAM cells that stores data that matches the comparand data.

22. The CAM device of claim 21, further comprising means for writing the first logic state to the second CAM cell associated with the next highest priority row of CAM cells that stores data that matches the comparand data.

23. The CAM device of claim 19, wherein the means for updating comprises means for writing a first logic state to the second CAM cells associated with the rows of CAM cells that each store data that matches the comparand data, and subsequently writing a second logic state to the second CAM cell associated with the highest priority row of CAM cells that stores data that matches the comparand data.

24. The CAM device of claim 23, wherein the means for determining comprises means for determining the address of the highest priority row of CAM cells that stores data that matches the comparand data.

25. The CAM device of claim 24, further comprising:

means for decoding the address of the highest priority row of CAM cells that stores data that matches the comparand data; and

means for selecting the second CAM cell associated with the highest priority row of CAM cells that stores data that matches the comparand data.

26. A depth cascaded content addressable memory (CAM) system comprising:

a first CAM device having a match flag output to provide a match flag output signal; and

a second CAM device comprising;

a match flag input coupled to the match flag output of the first CAM device;

a CAM array having a plurality of rows each having (1) a plurality of first CAM cells coupled to a match line and a first word line, (2) a second CAM cell coupled to the match line and a second word line, the second CAM cell for storing match results between comparand data and data stored in the first CAM cells, and (3) control logic coupled to the first word line, the match line, and the second word line, the control logic to control access to the second CAM cell;

a comparand storage element coupled to the CAM array;

a write circuit coupled to each of the second CAM cells;

an instruction decoder coupled to the write circuit;

a timing generator coupled to the instruction decoder and comparand storage element; and

cascade logic coupled to the instruction decoder and the timing generator, the cascade logic operative to inhibit evaluation of data stored in each of the second CAM cells in response to the match flag input signal.

27. The CAM system of claim 26, wherein the first CAM device further having a multiple match flag output, and the second CAM device further having a multiple match flag input coupled to the multiple match flag output of the first CAM device.

32. The CAM system of claim 27, wherein the second CAM device further comprises:

an encoder coupled to the match lines and operative to generate an encoded match address; and

a decoder coupled to the encoder and the first word lines.

33. The CAM system of claim 32, wherein the second CAM device further comprises a status register coupled to the priority encoder to receive the encoded match address.

34. The CAM system of claim 33, wherein the cascade logic is operative to generate a control signal that indicates that the encoded match address is output from the second CAM device from the status register rather than from the priority encoder.

35. The CAM system of claim 34, wherein the first CAM device comprises:

a CAM array having a plurality of rows each having (1) a plurality of first CAM cells coupled to a match line a first word line, (2) a second CAM cell coupled to the match line and a second word line, the second CAM cell for storing match results between comparand data and data stored in the first CAM cells, and (3) control logic coupled to the first word line, the match line, and the second word line, the control logic to control access to the second CAM cell;

a comparand storage element coupled to the CAM array;

a write circuit coupled to the second CAM cells;

an instruction decoder coupled to the write circuit;

a timing generator coupled to the instruction decoder and comparand storage element; and

cascade logic coupled to the instruction decoder, the timing generator, and the match flag output.

28. A method of operating a depth cascaded content addressable memory (CAM) system having at least a first and second CAM device each having a CAM array, comprising:

determining that each CAM array has at least one row of CAM cells that stores data that matches comparand data;

updating data stored in a plurality of second CAM cells in each CAM device in response to the match results, each of the second CAM cells associated with a corresponding row of CAM cells;

asserting a match flag signal to a first state from the first CAM device to the second CAM device to indicate a match in the first CAM device;

inhibiting comparison of the data stored in the second CAM cells in the second CAM device with a predetermined logic state in response to the asserted match flag signal; and

outputting from the first CAM device an address of the highest priority row of CAM cells that stores data that matches the comparand data.

29. The method of claim 28, further comprising:

providing an instruction to both CAM devices to determine the next highest priority row of CAM cells of the CAM system that stores data that matches the comparand data;

determining that the first CAM device has the next highest priority row of CAM cells;

comparing the data stored in the second CAM cells of the first CAM device to determine the address of next highest priority row of CAM cells; and

outputting an address of the next highest priority row of CAM cells from the first CAM device.

30. The method of claim 28, further comprising:

providing an instruction to both CAM devices to determine the next highest priority row of CAM cells of the CAM system that stores data that matches the comparand data;

deasserting the match flag signal to a second state from the first CAM device to the second CAM device to indicate a mismatch in the first CAM device;

comparing the data stored in the second CAM cells of the second CAM device to determine the address of next highest priority row of CAM cells; and

outputting an address of the next highest priority row of CAM cells from the second CAM device.

31. The method of claim 30, further comprising:

providing another instruction to both CAM devices to determine another row of CAM cells of the CAM system that stores data that matches the comparand data;

comparing the data stored in the second CAM cells of the second CAM device to determine the address of the another row of CAM cells; and

outputting an address of the another row of CAM cells from the second CAM device.

36. A method of determining the next highest priority matching location in a content addressable memory (CAM) device, comprising:

determining that a plurality of rows of first CAM cells store data that matches comparand data, wherein each row of the first CAM cells has a corresponding second CAM cell for storing the match results for the row; and

simultaneously writing (i) a mismatch result to the second CAM cell associated with the highest priority row of CAM cells that stores data that matches the comparand data, and (ii) a match result to each of the second CAM cells associated with the lower priority rows of the first CAM cells that store data that matches the comparand data.

37. The method of claim 36, wherein the determining writing are executed in a single clock cycle.