Circuit for multiple match hit CAM readout

Details Circuit for multiple match hit CAM readout Circuit for multiple match hit CAM readout

2002-11-25

2004-10-12

Le, Thong (Department: 2818)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S239000

Reexamination Certificate

active

06804132

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to content addressable memory (CAM), and more particularly, to a circuit for reading out multiple match hits from a CAM.
2. Background Art
A content addressable memory (CAM) includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information. The bits stored in a row of memory cells in the CAM constitute a CAM word. During compare (i.e., “search”) operations, a comparand word is received at appropriate input terminals of the CAM and then simultaneously compared in parallel to all the CAM words in the CAM. If the comparand word matches one of the CAM words (i.e., a matchline “hit” occurs), a matchline corresponding to the matching CAM word is asserted to indicate a match condition. If the comparand word matches more than one of the CAM words, the matchline corresponding to each of the matching CAM words is asserted, and a “multiple match” flag is asserted to indicate the multiple match condition.
The asserted matchline(s) are prioritized in a predetermined manner and subsequently decoded into their corresponding CAM addresses using a priority encoder. When multiple matches are present, the time required to examine and encode all of the addresses corresponding to the asserted matchlines is dependent upon the minimum cycle time between address reads. In particular, the greater the minimum cycle time, the longer it takes the priority encoder to encode all of the addresses corresponding to the asserted matchlines.
An example of a system for reading multiple matched addresses is disclosed in U.S. Pat. No. 6,118,682 to Martin, which is incorporated herein by reference. In Martin, the signal level of every matchline of the CAM must be tested in succession with the addition of a gate delay, whether matching or not. The minimum cycle time in this system is limited by the AND gate delay of a signal rippling through a plurality of AND gates (see, e.g., AND gates
26
,
28
,
30
, . . . ,
FIG. 1
of Martin). Since, for each matchline of the CAM, another AND gate is required, the minimum cycle time increases dramatically as the size of the CAM increases. In particular, the minimum cycle time in Martin is given by:
min_cycle=gate delay*#of matchlines.
As an example, for a 16-word CAM, the minimum cycle time (gate delays) is 16, while for a 1024-word CAM, the minimum cycle time (gate delays) is 1024.
As a result, there exists a need for a circuit for reading out multiple match hits from a CAM in a more time efficient manner. In particular, there exists a need for a circuit for reading out multiple match hits from a CAM that reduces the minimum cycle time between address reads.
SUMMARY OF THE INVENTION
A first aspect of the invention provides an apparatus for reading out multiple match hits from a content addressable memory (CAM), comprising a priority encoder for receiving a plurality of matchlines from a CAM and for encoding addresses of the CAM that are associated with the matchlines that indicate a match, and a matchline mask system for selectively masking off a matchline that indicates a match from the priority encoder after the address associated with that matchline is encoded by the priority encoder.
A second aspect of the invention provides an apparatus for masking matchlines of a content addressable memory (CAM), comprising a plurality of matchline mask units, wherein each matchline of the CAM passes through a respective one of the matchline mask units, and wherein each matchline mask unit is configured to mask its associated matchline from a priority encoder, and a decoder system for sequentially masking each matchline that indicates a match from the priority encoder using the matchline's respective matchline mask unit.
A third aspect of the invention provides a method for reading out multiple match hits from a content addressable memory (CAM), comprising receiving a plurality of matchlines from a CAM, determining and prioritizing the matchlines that indicate a match, sequentially encoding the addresses of the CAM that are associated with the matchlines that indicate a match, and selectively masking off a matchline that indicates a match after the address associated with that matchline has been encoded.
The exemplary aspects of the present invention are designed to solve the problems herein described and other problems not discussed, which are discoverable by a skilled artisan.


REFERENCES:
patent: 3602899 (1971-08-01), Lindquist et al.
patent: 4670858 (1987-06-01), Almy
patent: 4928260 (1990-05-01), Chuang et al.
patent: 5396448 (1995-03-01), Takayanagi et al.
patent: 5406508 (1995-04-01), Hayashibara
patent: 5495382 (1996-02-01), Albon
patent: 5649149 (1997-07-01), Stormon et al.
patent: 5852569 (1998-12-01), Srinivasan et al.
patent: 6118682 (2000-09-01), Martin
patent: 6157558 (2000-12-01), Wong
patent: 6175513 (2001-01-01), Khanna
patent: 6181592 (2001-01-01), Aoki
patent: 6181698 (2001-01-01), Hariguchi
patent: 6307798 (2001-10-01), Ahmed et al.
patent: 6418042 (2002-07-01), Srinivasan et al.
patent: 2003/0033326 (2003-02-01), Kumar et al.
patent: 2003/0145178 (2003-07-01), Jiang et al.
patent: WO 98/53458 (1998-11-01), None
IBM Technical Disclosure Bulletin, E.E. Davidson, vol. 17, No. 3, “Encoder/Resolver Array for Content Addressable Memory”, Aug. 1974, pp. 855-858.
IBM Technical Disclosure Bulletin, vol. 34, No. 2, “Addressed Writeable and Associative Readable Memory”, Jul. 1991, pp. 326-329.

Affiliated with

Also associated with

Rating

Circuit for multiple match hit CAM readout does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Circuit for multiple match hit CAM readout, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit for multiple match hit CAM readout will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3290305