Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-12-18
2003-05-13
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06564289
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to content addressable memory (CAM) devices, and more particularly to accessing multiple match locations in a CAM device.
BACKGROUND
A content addressable memory (CAM) device is a storage device that can be instructed to compare a specific pattern of comparand data with data stored in its associative CAM array. The entire CAM array, or segments thereof, are searched in parallel for a match with the comparand data. The CAM device typically indicates if a match occurs by asserting a match flag, and also typically indicates if multiple matches occur by asserting a multiple match flag. The CAM device can then be instructed to output the highest priority match address or index, data stored in one or more CAM cells at the matching address, and other status information including the match flags, a full flag, validity bits (e.g., skip and empty bits), and other status information.
It would be desirable to provide a CAM device that can efficiently access the highest priority matching location in response to a first instruction, and then access a subsequent lower priority matching location in response to a single second instruction.
SUMMARY OF THE INVENTION
A content address memory (CAM) device is disclosed 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 output the highest priority matching address in the same system or a later 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.
For one embodiment, the CAM array includes a column of multiple match (“MMR”) bits that are used by the RNHPM instruction to resolve a multiple match condition. The MMR bits store an indication of whether the corresponding CAM location has a match with the comparand data. For one example, the MMR bits are set to logic zeros at the beginning of the initial compare instruction. When it is determined which locations in the CAM array match the comparand data, then the MMR bits for those locations are updated to a logic one except for the highest priority matching location. In response to a subsequent RNHPM instruction, only the MMR bits need to be queried (e.g., compared with a logic one) to determine the next highest priority matching location. The match address of the next highest priority matching location, data stored in one or more of the CAM cells at the next highest priority matching location, and/or other status information may then be output from the CAM device. The MMR bit for that matching location is then reset to a logic zero such that a subsequent RNHPM instruction can then access lower priority matching locations by using the MMR bits.
Other objects, features, and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description which follows below.
REFERENCES:
patent: 3257646 (1966-06-01), Roth
patent: 3353159 (1967-11-01), Lee, III
patent: 3602899 (1971-08-01), Lindquist et al.
patent: 3675211 (1972-07-01), Raviv
patent: 3685020 (1972-08-01), Meade
patent: 3868642 (1975-02-01), Sachs
patent: 4112502 (1978-09-01), Scheuneman
patent: 4244033 (1981-01-01), Hattori
patent: 4472805 (1984-09-01), Wacyk et al.
patent: 4523301 (1985-06-01), Kadota et al.
patent: 4646271 (1987-02-01), Uchiyama et al.
patent: 4656626 (1987-04-01), Yudichak et al.
patent: 4670858 (1987-06-01), Almy
patent: 4747080 (1988-05-01), Yamada
patent: 4758982 (1988-07-01), Price
patent: 4780845 (1988-10-01), Threewitt
patent: 4785398 (1988-11-01), Joyce et al.
patent: 4791606 (1988-12-01), Threewitt
patent: 4813002 (1989-03-01), Joyce et al.
patent: 4845668 (1989-07-01), Sano et al.
patent: 4903234 (1990-02-01), Sakuraba et al.
patent: 4928260 (1990-05-01), Chuang et al.
patent: 4958377 (1990-09-01), Takahashi
patent: 4959811 (1990-09-01), Szczepanek
patent: 4975873 (1990-12-01), Nakabayashi et al.
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5010516 (1991-04-01), Oates
patent: 5014195 (1991-05-01), Farrell et al.
patent: 5036486 (1991-07-01), Noguchi et al.
patent: 5051948 (1991-09-01), Watabe et al.
patent: 5053991 (1991-10-01), Burrows
patent: 5072422 (1991-12-01), Rachels
patent: 5107501 (1992-04-01), Zorian
patent: 5111427 (1992-05-01), Kobayashi et al.
patent: 5226005 (1993-07-01), Lee et al.
patent: 5265100 (1993-11-01), McClure et al.
patent: 5339268 (1994-08-01), Machida
patent: 5383146 (1995-01-01), Threewitt
patent: 5388065 (1995-02-01), Yoneda
patent: 5396449 (1995-03-01), Atallah et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5440709 (1995-08-01), Edgar
patent: 5440715 (1995-08-01), Wyland
patent: 5454094 (1995-09-01), Montoye
patent: 5455576 (1995-10-01), Clark, II et al.
patent: 5469161 (1995-11-01), Bezek
patent: 5479366 (1995-12-01), Sasama
patent: 5485418 (1996-01-01), Hiraki et al.
patent: 5490102 (1996-02-01), Jubran
patent: 5491703 (1996-02-01), Barnaby et al.
patent: 5513134 (1996-04-01), Cooperman et al.
patent: 5517441 (1996-05-01), Dietz et al.
patent: 5621677 (1997-04-01), Jones
patent: 5649149 (1997-07-01), Stormon et al.
patent: 5706224 (1998-01-01), Srinivasan et al.
patent: 5818873 (1998-10-01), Wall et al.
patent: 5841874 (1998-11-01), Kempke et al.
patent: 5860085 (1999-01-01), Stormon et al.
patent: 5893931 (1999-04-01), Peng et al.
patent: 5905668 (1999-05-01), Takahashi et al.
patent: 5930359 (1999-07-01), Kempke et al.
patent: 5946704 (1999-08-01), Yoneda et al.
patent: 6081442 (2000-06-01), Igarashi et al.
patent: 6147890 (2000-11-01), Kawana et al.
patent: 0 660 332 (1993-12-01), None
patent: 0774758 (1997-05-01), None
patent: 08167295 (1996-06-01), None
Patent Abstracts of Japan, Publication No. 08273376, Publication date Oct. 18, 1996.
Masao Akata, “A Scheduling Content-Addressable Memory for ATM Space-Division Switch Control”, IEEE International Solid State Circuits Conference, Feb. 1991, New York.
Ghose et al., “Response Pipelined CAM Chips: The First Generation and Beyond”, 7thInternational conference on VLSI Design, Jan. 1994, pp. 365-368.
Takeshi Ogura, et al., “A 4-kbit Associative Memory LSI”, IEEE Journal of Solid-State Circuits, vol. SC-20, No. 6, Dec. 1985, pp. 1277-1281.
Simon R. Jones, et al., “A 9-kbit Associative Memory for High-Speed Parallel Processing Applications”, IEEE Journal of Solid-State Circuits, vol. 23, No. 2, Apr. 1988, pp. 543-548.
Anthony J. McAuley, et al., “A Self-Testing Reconfigurable CAM”, IEEE Journal of Solid-State Circuits, vol. 26, No. 3, Mar. 1991, pp. 257-261.
Yong-Chui Shin, et al., “A Special-Purpose Content Addressable Memory Chip For Real-Time Image Processing”, IEEE Journal of Solid-State Circuits, vol. 27, No. 5, May 1992, pp. 737-744.
KLSI, “Addressable Processor” KE5B064H series—Dual Port and Fixed Table Type-, Version 1.0.1, published approximately late 1995 or early 1996, pp. 1-1 through 14-1.
KLSI, “KE5B064A1 Address Processor” Version 2.0.2, published approximately late 1995 or ear
Khanna Sandeep
Nataraj Bindiganavale S.
Srinivasan Varadarajan
Moazzami Nasser
Netlogic Microsystems Inc.
Yoo Do Hyun
LandOfFree
Method and apparatus for performing a read next highest... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing a read next highest..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing a read next highest... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3082655