Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2002-02-14
2004-06-22
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S216000, C365S230020, C326S040000
Reexamination Certificate
active
06754766
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to memory circuits, and more particularly to memory circuits of the type known as content-addressable memories.
A content-addressable memory (“CAM”) is a memory that can store a plurality of different data words in respective different address locations in the memory. When a search data word is applied to the CAM, the CAM outputs the address of the location (if any) in the CAM that contains that data word, or the CAM may output a simple “match” signal. CAMs are also sometimes referred to as associative memories, but CAM is the term chosen for use herein.
Many programmable logic device integrated circuits (“PLDs”) include blocks of memory that can be used in any of several different ways. For example, such memory blocks may be usable as single- or multi-port random access memory (“RAM”), read-only memory (“ROM”), or product-term (“Pterm”) logic, etc. (See, for example, Heile U.S. Pat. No. 6,020,759.) It is even known to give such memory blocks the capability of optionally operating as CAMs. (See, for example, Heile U.S. Pat. No. 6,144,573.) Although significant, the demand for CAM capability tends to be less than the demand for other types of memory capability, so it can be uneconomical to include, in a PLD, circuitry that is dedicated to supporting CAM capability. Also, it can be difficult or impossible to provide such dedicated circuitry that is capable of efficiently supporting very large CAMs and/or CAMs requiring changes to the data stored in the CAM.
In view of the foregoing, one aspect of the present invention relates to using circuitry on a PLD that does not include dedicated CAM capability to allow the PLD to emulate a CAM. The invention will be illustratively described primarily in such a PLD context. But it will be understood that the invention is also applicable to emulating CAM capability in other contexts, such as in application-specific integrated circuits (“ASICs”) that include suitable memory resources (e.g., RAM or ROM) and systems that include multiple integrated circuits (e.g., systems that include multiple RAM or ROM chips).
SUMMARY OF THE INVENTION
In accordance with the present invention CAMs are implemented in PLDs by configuring (i.e., programming) the PLD to emulate the required CAM. The CAM data is stored in memory blocks in the PLD. The programmable logic of the PLD is used to control such functions as storage of the CAM data in the memory blocks, retrieval of the CAM data from the memory blocks for comparison to search data, and the actual comparisons of CAM data and search data. As part of the storage of CAM data in the memory blocks, the programmable logic of the PLD may convert CAM addresses to actual memory block addresses. Similarly, as part of the retrieval of CAM data from the memory blocks and comparison of that data to search data, the programmable logic of the PLD may convert the actual memory block address of CAM data that matches the search data to a CAM address. Time-division multiplexing (“TDM”) may be used in comparing the CAM data to the search data. Circuitry on the PLD (e.g., phase locked loop (“PLL”) circuitry and programmable logic circuitry) may be used to provide a faster clock signal for use in these TDM operations. In each cycle of the faster clock signal, multiple CAM data words may be retrieved in parallel from the memory blocks and compared in parallel to the search data.
As an alternative to the foregoing, the invention may be similarly applied to other circuitry having memory blocks generally like those on a PLD as described above. Such other circuitry may be an ASIC or a system including multiple memory chips (integrated circuits).
Further features of the invention, its nature and various advantages will be more apparent from the accompanying drawings and the following detailed description.
REFERENCES:
patent: 4244033 (1981-01-01), Hattori
patent: 5550782 (1996-08-01), Cliff et al.
patent: 5940597 (1999-08-01), Chung
patent: 6020759 (2000-02-01), Heile
patent: 6118720 (2000-09-01), Heile
patent: 6144573 (2000-11-01), Heile
patent: 6278289 (2001-08-01), Guccione et al.
patent: 6308218 (2001-10-01), Vasa
patent: 6344989 (2002-02-01), Heile
patent: 6351143 (2002-02-01), Guccione et al.
patent: 6353332 (2002-03-01), Brelet
patent: 6356110 (2002-03-01), Reddy et al.
patent: 6556500 (2003-04-01), Heile
patent: 2002/0057621 (2002-05-01), Heile
“Apex 20KC Programmable Logic Device”, Data Sheet, Mar. 2001, ver. 1.0, Altera Corporation, San Jose, CA, pp. 1, and 24-35.
“Apex II Programmable Logic Device Family”, Data Sheet, Apr. 2001, ver. 1.0, Altera Corporation, San Jose, CA, pp. 1, and 24-36.
“Apex 20K Programmable Logic Device Family”, Data Sheet, Aug. 2001, ver. 4.0, Altera Corporation, San Jose, CA, pp. 1, and 25-36.
J.-L. Brelet, “An Overview of Multiple CAM Designs in Virtex Family Devices,” Application Note XAPP201, Sep. 23, 1999 (Version 1.1), Xilinx, Inc., San Jose, CA. p. 1-6.
M. Defossez, “Content Addressable Memory (CAM) in ATM Applications,” Application Note: Virtex Series and Virtex II Series XAPP202 (v1.2) Jan. 6, 2001, Xilinx, Inc., San Jose, CA. p. 1-12.
J.-L. Brelet et al., “Designing Flexible, Fast CAMs with Virtex Family FPGAs,” Application Note XAPP203, Sep. 23, 1999 (Version 1.1), Xilinx, Inc., San Jose, CA. p. 1-17.
J.-L. Brelet, “Using Block RAM for High Performance Read/Write CAMs,” Application Note: Virtex Series XAPP204 (v1.2) May 2, 2000, Xilinx, Inc., San Jose, CA. p. 1-19.
Altera Corporation
Fish & Neave
Jackson Robert R.
Peugh Brian R.
Sparks Donald
LandOfFree
Emulation of content-addressable memories does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Emulation of content-addressable memories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Emulation of content-addressable memories will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3366179