Method and apparatus for determining an exact match in a content addressable memory device

• US 6,574,702 B2
• Filed: 05/09/2002
• Issued: 06/03/2003
• Est. Priority Date: 02/23/1999
• 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): PEIKARI, BEHZAD
• Application Number:
  US10/142,855
• Publication Number:
  US 20030028713A1
• Time in Patent Office: 390 Days
• Field of Search: 365/189.07, 365/230.06, 710/14, 710/48, 710/49, 710/262, 710/266, 711/1, 711/108, 711/154, 712/5, 712/224, 712/244, 714/3
• US Class Current: 711/108
• CPC Class Codes: G11C 15/04 using semiconductor elements
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming

Abstract

A method and apparatus for determining an exact match in a ternary CAM device. Each ternary CAM cell includes CAM cells for storing CAM data, local mask cells for storing prefix mask data for the corresponding CAM cells, and a mask override circuit. Each local mask cell includes a masking circuit that masks the prefix mask data or CAM data provided to the comparison circuit, or masks the comparison result from the match line of a CAM cell. The mask override circuit effectively overrides the prefix mask data stored in the local mask cell. The mask override circuit performs the override function by negating the operation of the mask circuit such that no masking operation occurs when an exact match compare or invalidate function is performed by the ternary CAM device. For example, during an exact match operation, the CAM cells compare comparand data with unmasked CAM data and provide the compare results to CAM match lines. The local mask cells also compare mask data with the stored prefix mask data and provide the results to mask match lines. If both compares result in a match, then an exact match entry is located in the ternary CAM device. The locations or indexes of the exact match entries may then be output from the CAM device. One or more of the exact match locations may also be invalidated or deleted.

Claims

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

a CAM array to store CAM data and mask data, the CAM array including a mask override circuit operable to override the mask data; and

an instruction decoder coupled with the CAM array, the instruction decoder to receive an exact match instruction, the instruction decoder to decode the exact match data to enable the mask override circuit.

2. The CAM device of claim 1, wherein the exact match instruction is an exact match compare instruction.

3. The CAM device of claim 1, wherein the exact match instruction is an exact match invalidate instruction.

4. The CAM device of claim 1, wherein the exact match instruction is an exact match delete instruction.

5. The CAM device of claim 1, wherein the exact match instruction is an exact match erase instruction.

6. The CAM device of claim 1, wherein the CAM device further comprises means for updating a validity bit in response to the exact match instruction.

7. The CAM device of claim 6, further comprising a match line coupled with the CAM cell and wherein the means for updating comprises:

a latch coupled with the match line;

a multiplexer coupled with the latch; and

a memory cell coupled to the multiplexer.