Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-08-10
2004-06-08
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S128000, C711S156000, C365S049130
Reexamination Certificate
active
06748484
ABSTRACT:
BACKGROUND
A. Technical Field
The present invention relates generally to associative memories, and in particular to content addressable memories. More particularly, the present invention relates to an associative memory having a match resolution circuit for determining a best match from among multiple matches.
B. Background of the Invention
An associative memory, such as a content addressable memory (CAM), is a device that permits the contents of the memory to be searched and matched instead of having to specify a memory location address in order to retrieve data from the memory. A CAM may be used to accelerate any application requiring fast searching of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. A CAM provides a performance advantage over conventional memory devices with conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired information against the entire list of entries simultaneously, giving an order-of-magnitude reduction in search time. For example, a binary search through a database of 1000 entries may take ten separate search steps whereas a CAM device with 1000 entries may be searched in a single operation resulting in a search which takes ten times less time. One example of an application in which CAM devices are often used is to store a routing table for high speed switching systems which need to rapidly search the routing table to look for a matching destination address so that a data packet may be routed to the appropriate destination address.
A CAM device is organized somewhat differently from typical SRAM or DRAM devices. Information stored in a CAM may be accessed by comparing the data stored in the memory with data placed in a special register known as a search input or compare register as opposed to RAM devices in which information is accessed by specifying a particular memory address. If there is a match in particular memory locations with every corresponding bit in the register, a Match Flag is asserted to let the user know that the data in the register was found in the CAM device. Thus, with a CAM device, the user supplies a piece of data she would like to match to the CAM and gets back the address of any matching pieces of data in the CAM. There are two common types of CAM memory, binary CAM and ternary CAM. Binary cam requires an exact match of all bits in the search input and comparand for a match. Ternary CAM uses a mask to allow some bits to be treated as “don't care” bits and ignored in the determination of a match.
Data in a Binary CAM location typically comprises 2 fields: a comparand and an associated data field. Unlike a random access memory (“RAM”), when a search is performed on a CAM, all comparands in a CAM are compared simultaneously with a search input stored in a register. As each comparand is compared with the search input, a match line for that comparand is activated if the comparand matches the search word. Prior art ternary CAM devices may also contain an additional field known as a mask. The mask may be used to filter off portions of the comparand during the search procedure. In other words, the mask allows a comparison between the search input and only certain portions of the comparand as determined by the mask.
A search on a CAM may result in several matches in response to the search input, however, only one result should be returned. Therefore, one problem in the prior art is determining which match from a plurality of matches should be returned as the best match for a particular search input. One solution in the prior art is to implement a priority resolution circuit that uses the position of the data item in the CAM array to determine which match to output. One disadvantage in using a priority resolution circuit based on the position of the data item in the CAM array is that it only offers one criteria, (i.e. position) for determining a best match. Additionally, in order to change the priority of a particular CAM data item, it is necessary to move the data items to different positions in the CAM array. This process is cumbersome and slows down the operation of the CAM. Accordingly it is desirable to provide a priority resolution system that is capable of determining a best match among a plurality of CAM matches. More specifically, it is advantageous to provide a priority resolution system that can be dynamically updated and can use criteria other than position to determine a best match among a plurality of matches.
SUMMARY OF THE INVENTION
The present invention overcomes the deficiencies and limitations of the prior art with a unique system and method for determining a best match from a plurality of matches resulting in response to a search input performed on an associative memory. The system and method for determining a best match from a plurality of matches comprises a priority field associated with each data item stored in the associative memory. The priority field corresponds to criteria that is used to order the priority of the data items. A match resolution module is coupled to receive match signals from an associative memory and the priority fields associated with the matching data entries. The match resolution structure compares the priority fields of the plurality of matching data items to determine which data item has the highest priority. The match resolution structure then indicates the data item having the highest priority as the best match of the associative memory for the particular search input.
REFERENCES:
patent: 4897814 (1990-01-01), Clark
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5555397 (1996-09-01), Sasama et al.
patent: 5566170 (1996-10-01), Bakke et al.
patent: 5619446 (1997-04-01), Yoneda et al.
patent: 5726942 (1998-03-01), Yoneda et al.
patent: 6289414 (2001-09-01), Feldmeier et al.
patent: 0 622 805 (1994-04-01), None
“Memory Organization Scheme for the Implementation of Routing Tables in High Performance IP Routers”, IBM Technical Disclosure Bulletin, vol. 36, No. 2, Feb. 1993, pp. 151-153.
Chu Raymond M.
Croft Walter E.
Henderson Alex E.
Sarin Vishal
Chace Christian P.
Intel Corporation
Sparks Donald
Tweet Kerry D.
LandOfFree
Match resolution circuit for an associative memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Match resolution circuit for an associative memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Match resolution circuit for an associative memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3293165