Prioritized content addressable memory

Details Prioritized content addressable memory Prioritized content addressable memory

2003-04-28

2004-02-24

Bragdon, Reginald G. (Department: 2188)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S158000, C711S207000

Reexamination Certificate

active

06697912

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a data search method and apparatus for locating data in a content addressable memory.
A content addressable memory (“CAM”) typically stores data in a plurality of memory locations. The CAM may include value matching logic that compares input data against the stored data and generates an indicator signal identifying those memory locations where the input value matches a stored value. A value match often is called a “hit.” Such properties of CAMs are well-known.
A CAM may be used as part of a prioritized search. That is, if input data causes several hits, there may be only desired match. The desired match may be identified by a prioritization scheme that operates independently of the CAM process. In this case, a search may be performed against the matching entries to identify the one that should be identified as a match. Unfortunately, a prioritized search typically implies an entry-for-entry search of the matching locations, a process that can introduce severe latency into the search process.
By way of example, consider a CAM search that is applied to a circular FIFO queue. The search may attempt to identify an oldest match in the queue. In a straightforward search algorithm, content addressing may identify one or more matching entries. Matches may be recorded as flags in a register. If there are multiple matches, an iterative register shift might be used to identify the oldest matching location. The iterative nature of the shift takes time.
Accordingly, there is a need in the art for a fast prioritized CAM search algorithm. What is desired is a CAM that outputs at most one hit even when there are multiple matching CAM locations—the hit corresponding to the location that is ranked highest according to the priority scheme.
SUMMARY
Embodiments of the present invention provide a prioritized content addressable memory having an at most one hit property despite the presence of redundant values stored therein.


REFERENCES:
patent: 5446686 (1995-08-01), Bosnyak et al.
patent: 5588126 (1996-12-01), Abramson et al.
patent: 5606670 (1997-02-01), Abramson et al.
patent: 5664137 (1997-09-01), Abramson et al.
patent: 5680566 (1997-10-01), Peng et al.
patent: 5694574 (1997-12-01), Abramson et al.
patent: 5717885 (1998-02-01), Kumar et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 6006306 (1999-12-01), Haywood et al.
patent: 6069573 (2000-05-01), Clark et al.
patent: 6157986 (2000-12-01), Witt

Affiliated with

Also associated with

Rating

Prioritized content addressable 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 Prioritized content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prioritized content addressable memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3302827