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

• US 6,564,289 B2
• Filed: 12/18/2001
• Issued: 05/13/2003
• 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): MOAZZAMI, NASSER G
• Application Number:
  US10/025,661
• Publication Number:
  US 20020129199A1
• Time in Patent Office: 511 Days
• Field of Search: 711/108, 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 text 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 row of content addressable memory (CAM) cells in a CAM array, the row comprising:

a plurality of first CAM cells coupled to a match line and a first word line;

a second CAM cell coupled to the match line and a second word line; and

control logic coupled to the first world line, the second word line, and the match line, the control logic to control access to the second CAM cell.

2. The row of CAM cells of claim 1, further comprising a reset line coupled to the control logic, the rest line for carrying a reset signal that causes the control logic to reset the second CAM cell to a predetermined state.

3. The row of CAM cells of claim 1, 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 line, 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.

4. The row of CAM cells of claim 1, further comprising a match latch wherein the control logic is coupled to the match line using the match latch.

5. The row of CAM cells of claim 1, wherein each of the plurality of first CAM cells comprises:

a comparator coupled to the match line; and

a random access memory cell coupled to the first word line.

6. The row of CAM cells of claim 1, wherein the second word line is independent of the first word line.

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

an address decoder; and

a CAM array coupled to the address decoder, the CAM array comprising a plurality of rows of CAM cells, each row of the plurality of rows of CAM cells comprising;

a plurality of first CAM cells coupled to a match line and a first word line;

a second CAM cell coupled to the match line and a second word line; and

control logic coupled to the first world line, the second word line, and the match line, the control logic to control access to the second CAM cell.

8. The CAM device of claim 7, wherein the address decoder is coupled to each row of the plurality of rows of CAM cells to drive the first word line.

9. The CAM device of claim 8, further comprising a match latch coupled to the match line of each row of the plurality of rows of CAM cells.

10. The CAM device of claim 9, further comprising a priority encoder coupled to the match latch.

11. The CAM device of claim 10, further comprising a comparand register coupled to each of the plurality of CAM cells of each row of CAM cells to provide comparand data to the CAM cells.

12. A method, comprising:

driving a first word line to select one or more of a first plurality of content addressable memory (CAM) cells;

performing a compare operation in the selected one or more first plurality of CAM cells;

indicating match results of the compare operations in the one or more of the first plurality of CAM cells on a match line; and

determining the selection of a second CAM cell by controlling a second word line in response to a word line signal on the first word line and a match signal from the match line.

13. The method of claim 12, wherein the second word line is further controlled in response to a reset signal on a reset line.

14. The method of claim 13, further comprising comparing data stored in a selected second CAM cell with a predetermined logic state.

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

means for driving a first word line to select one or more of a first plurality of content addressable memory (CAM) cells;

means for performing a compare operation in the selected one or more first plurality of CAM cells;

means for indicating match results of the compare operations in the one or more of the first plurality of CAM cells on a match line; and

means for determining the selection of a second CAM cell by controlling a second word line in response to a word line signal on the first word line and a match signal from the match line.

16. The CAM device of claim 15, further comprising means for comparing data stored in a selected second CAM cell with a predetermined logic state.

17. The CAM device of claim 16, further comprising means for generating an address corresponding to at least one of the first plurality of CAM cells having a match.