Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1998-05-11
2001-04-17
Yoo, Do Hyun (Department: 2759)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S005000, C711S104000, C711S150000, C711S151000, C711S152000, C365S049130
Reexamination Certificate
active
06219748
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 content address memory (CAM) device is disclosed that implements a “LEARN” instruction. In response to the LEARN instruction, the CAM device compares comparand data with data stored in a CAM array of the CAM device. If a match is not found, the comparand data is written into the CAM array. For one example, the comparand data is written to the next free address of the CAM array. The LEARN instruction may further cause the CAM device to output the next free address after the comparand data has been written into the CAM array. For one embodiment, the learn instruction may be implemented in a single clock cycle.
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), 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: 4975876 (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), Threewitt
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), 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: 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-07-01), Peng et al.
patent: 5905668 (1999-05-01), Takahashi et al.
patent: 5940852 (1999-08-01), Rangasayee et al.
patent: 0 660 332 (1993-12-01), None
patent: 63-276645 (1988-11-01), None
patent: 08167295 (1996-06-01), None
Applicant's Admitted Prior Arts. pp. 2-3 of specification.*
PCT International Search Report for PCT Int'l Appln No. PCT/US99/0876, 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 x 64 CAM” MCM69C432, Jan. 1996, pp. 4 pages total.
Hiroshi Kadota, et al., “An 8-kbit Content-Addressable and Reentrant Memory”, IEEE Journal of Solid-State Circuits, vol. SC-20, No. 5, Oct. 1985, pp. 951-956.
Landrock et al., “Associative Storage Module”, IBM Technical Disclosure Bulletin, vol. 25, No. 5, Oct. 1982, pp. 2341-2342.
Soo-Ik Chae, et al., “Content-Addressable Memory for VLSI Pattern Inspection”, IEEE Journal of Solid-State Circuits, vol. 23, No. 1, Feb. 1988, pp. 74-78.
Sergio R. Ramirez-Chavez, “Encoding Don't Cares in Static and Dynamic Content-Addressable Memories”, Transaction Briefs IEEE Transactions on Circuits and System-II: Analog and Digital Signal Processing, vol. 39, No. 8, Aug. 1992, pp. 575-578.
Advanced Micro Devices, “Final Am99C10A 256 x 48 Content Addressable Memory” Publication No. 08
Khanna Sandeep
Nataraj Bindiganavale S.
Srinivasan Varadarajan
Blakely & Sokoloff, Taylor & Zafman
NetLogic Microsystems, Inc.
Nguyen Than
Yoo Do Hyun
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-2551217