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

• US 20020129199A1
• Filed: 12/18/2001
• Published: 09/12/2002
• Est. Priority Date: 07/06/1998
• Status: Active Grant

• 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
• Granted Patent: US 6,564,289 B2
• Time in Patent Office: Days
• 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 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 accessing the next highest priority matching location in a content addressable memory (CAM) device, comprising the steps of:

comparing comparand data with data stored in a first plurality of CAM locations in response to a first instruction and determining the highest priority matching CAM location in the first plurality of CAM locations;

updating the data stored in a second plurality of CAM cells corresponding to the first plurality of CAM cells, wherein the second plurality of CAM cells indicate whether a match occurred in the first plurality of CAM cells; and

comparing the data stored in the second plurality of CAM cells with a logic state in response to a second instruction to determine the next highest priority matching location in the first plurality of CAM locations.