Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1998-05-11
2001-05-29
Nguyen, Than (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S101000, C711S128000, C365S049130
Reexamination Certificate
active
06240485
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to content addressable memory (CAM) devices.
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. If a match exists, the CAM device indicates the match by asserting a match flag. If no matching entries are found, the CAM device can be subsequently instructed to write the comparand data into the next available empty memory location in the CAM array. The next free empty location is commonly referred to as the next free address or “NFA”.
A typical process of comparing comparand data with a CAM array and updating the CAM array with non-repetitive data (i.e., data not already stored in the CAM array) generally requires multiple instructions and multiple clock cycles. A typical process includes the following steps: (1) a first instruction and clock cycle to write comparand data into the CAM device and instruct the CAM device to perform a comparison operation; (2) a second clock cycle for external logic to determine if the match flag has been asserted and decide how to proceed; (3) a second instruction and third clock cycle to instruct the CAM device to load the comparand data into the next free address from the comparand register; and, (4) a third instruction and fourth clock cycle to instruct the CAM device to output the next free address that received the comparand data, and which may be required by other external memories that may store associated data or other information for this memory location.
Because of the multiple number of instructions and clock cycles required to update a CAM device with non-repetitive data, the overall operating speed of the CAM device is reduced. Additionally, the maximum search rate of the CAM device cannot be maintained as it generally requires at least one clock cycle for external logic to determine whether a match occurred in the search.
Thus, it would be desirable to have a CAM device that can update the CAM array with non-repetitive data in fewer instructions and fewer clock cycles. It would also be desirable to have a CAM device that may sustain its maximum search rate during the operation. Such a CAM device may be loaded with non-repetitive data at faster rates than is conventionally possible.
SUMMARY OF THE INVENTION
A method and apparatus for implementing a LEARN instruction in a depth cascaded content address memory (CAM) system is described. Each CAM device in the CAM system may include a CAM array, an input coupled to the CAM array and configured to receive comparand data to be compared with data stored in the CAM array, circuitry coupled to the CAM array and configured to write the comparand data into the CAM array if the comparand data does not match the data stored in the CAM array, and cascade logic coupled to the circuitry and configured to receive a plurality of match flag input signals, the cascade logic configured to disable the circuitry from writing the comparand data into the CAM array if the comparand data matches the data stored in the CAM array. Each CAM device may have a match flag input pin and output pin coupled to a match flag output pin and input pin, respectively, of the previous device and next device in the depth cascaded CAM system. Each CAM device may further include a cascade input pin and output pin coupled to a cascade output pin and input pin, respectively, of the previous device and next device in the depth cascaded CAM system.
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: 3800286 (1974-03-01), Brown et al.
patent: 3868642 (1975-02-01), Scahs
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: 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), Threewit
patent: 5414704 (1995-05-01), Spinney
patent: 5440709 (1995-08-01), Edgar
patent: 5454094 (1995-09-01), Montoye
patent: 5455576 (1995-10-01), Clark, II et al.
patent: 5469161 (1995-11-01), Bezek
patent: 5485418 (1996-01-01), Hiraki et al.
patent: 5485526 (1996-01-01), Tobin
patent: 5490102 (1996-02-01), Jurban
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: 5649149 (1997-07-01), Stormon et al.
patent: 5706224 (1998-01-01), Srinivasan et al.
patent: 5758148 (1998-05-01), Lipovski
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-03-01), Peng et al.
patent: 5905668 (1999-05-01), Takahashi et al.
patent: 5930359 (1999-07-01), Kempke et al.
patent: 5940852 (1999-08-01), Rangasayee et al.
patent: 5999435 (1999-12-01), Henderson et al.
patent: 0 660 332 (1993-12-01), None
patent: 63276645A (1988-11-01), None
patent: 08167295 (1996-06-01), None
patent: WO 98/12651 (1998-03-01), None
Music Semiconductor, the MU9C1480 LANCAM Handbook, Rev. 3, Nov. 1994, pp.1-1 to 7-12.*
PCT International Search Report for PCT Int'l Appln No. PCT/US99/08767, mailed Jul. 23, 1999, 6 pgs.
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-Chul 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, “Address 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 early 1996, pp. 1-1 through 12-1.
Motorola Semiconductor Technical Data, “Advance Information 16K × 64 CAM” MCM69C432, Jan. 1996, pp. 4 pages total.
Hiroshi Kadota, et al., “An 8-kbit Content-Addressable and Reentrant Memory”
Khanna Sandeep
Nataraj Bindiganavale S.
Srinivasan Varadarajan
Blakely & Sokoloff, Taylor & Zafman
NetLogic Microsystems, Inc.
Nguyen Than
LandOfFree
Method and apparatus for implementing a learn instruction in... 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 implementing a learn instruction in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing a learn instruction in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2570348