Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-05-18
2001-10-09
Gossage, Glenn (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130, C711S005000, C711S167000
Reexamination Certificate
active
06301636
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a content addressable memory (CAM) system in which a plurality of CAM chips are cascade-connected.
BACKGROUND INFORMATION
In known CAMs, data is selected based on contents, rather than physical location. This function is useful for many applications, especially when performing a look-up for the purposes of mapping a long identification word data to a shorter word data. This operation is required in many telecommunications (telecom) functions, including Asynchronous Transfer Mode (ATM) address translation.
Often, system storage requirements exceed the number of entries stored on a single CAM chip. Multiple chips are then required, and it is necessary that a means be developed to cascade these multiple chips such that they may be searched as a single entity. An appropriate “user-friendly” cascading capability enables the same chip to be used in a range of systems with different capacity requirements, and allows for easy expandability and scalability, as well.
U.S. Pat. No. 5,568,416 granted to K. Kawana et al on Oct. 22, 1996 discloses an associative memory in which multiple CAM chips are cascaded by propagating a result address and status through all chips in the cascade. Each chip contains a status register for itself, and another for all upstream chips. It also discloses means of identifying the last device in the cascade, and separate storage areas for common and unique data entries.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an improved content addressable memory system.
According to one aspect of the present invention, there is provided a system comprising a common bus and a plurality of content addressable memory (CAM) chips which are cascaded and connected to the common bus, each of the CAM chips comprising a CAM array, timing signal means, hit propagation means and match address transfer means. In the system, each CAM array includes encoding means and an array of core cells, of w words×b bits, associated with the encoding means, each of the core cells comprising data storage means, the core cells of each word being associated with a respective match line. The CAM array of each CAM chip is able to provide, through its encoding means, hit and match address signals resulting from a search operation on that CAM chip in response to a clock signal. The timing signal means generates a self-timed signal in response to the clock signal. The hit propagation means provides a propagation-out hit signal to a downstream CAM chip in response to the self-timed signal. The match address transfer means for transferring the match address signal resulting from the search operation on that CAM chip to the common bus in response to the self-timed signal.
For example, the hit propagation means of each of the CAM chips comprises a first logic circuit for responding to the self-timed signal provided from the timing signal means of that CAM chip, the hit signal provided from the CAM array of that CAM chip and the propagation-in hit signal provided from the upstream CAM chip. The match address transfer means of each of the CAM chips comprises a second logic circuit for responding to the self-timed signal provided from the timing signal means of that CAM chip, the hit signal provided from the CAM array of that CAM chip and the propagation-in hit signal provided from the upstream CAM chip. The second logic circuit comprises gate means for preventing more than one CAM chip from transferring the match address signals from the CAM arrays of the CAM chips to the common bus simultaneously.
In another example of the system, the CAM array of each of the CAM chips further comprises an extra row for providing a modelmiss signal, the extra row being associated with the encoding means of that CAM array, the extra row including a model match line and a plurality of modified core cells connected to the model match line, the self-timed signal being provided in response to the modelmiss signal provided from that extra row and the clock signal. For example, one of the modified core cells is a mismatch cell and the others are match cells. The mismatch core cell is the farthest placed from the encoding means of that CAM chip.
In another example of the system, the CAM array of each of the CAM chips further comprises an extra row for providing a modelhit signal, the extra row being associated with the encoding means of that CAM array, the extra row including a chain of divided model match lines, each of the divided model match line being associated with a plurality of match core cells, two adjacent divided model match lines being coupled by a logic circuit for providing a logic output to the encoding means of that CAM array, the logic output being the modelhit signal.
In another example of the system, each of the w words is divided into two word divisions, each word division being one of two halves of each word, the two divided match lines of the two halves being coupled by a logic gate circuit for providing an output to the encoding means of that CAM array. The logic gate circuit may include a NAND circuit.
In another example of the system, each of the w words is divided into a plurality of word slices, that CAM array further comprising data means for providing each of the word slices with reference data for a search operation on that CAM chip.
In the system, each word slice of each word may be further divided into a plurality of word divisions, the core cells of each word division being associated with a divided match line of that word, two adjacent divided match lines of two word divisions of each word slice being coupled by a logic circuit for providing a logic output to the encoding means of that CAM array.
REFERENCES:
patent: 4670858 (1987-06-01), Almy
patent: 5018111 (1991-05-01), Madland
patent: 5031141 (1991-07-01), Guddat
patent: 5034919 (1991-07-01), Sasai et al.
patent: 5289403 (1994-02-01), Yetter
patent: 5517441 (1996-05-01), Dietz et al.
patent: 5555397 (1996-09-01), Sasama et al.
patent: 5568416 (1996-10-01), Kawana et al.
patent: 5828593 (1998-10-01), Schultz et al.
patent: 5859791 (1999-01-01), Schultz et al.
patent: 6022707 (2000-09-01), Schultz et al.
K.J. Schultz et al, “Architectures for Large Capacity CAMs,” Integration: the VLSI Journal, vol. 18, 1995, pp. 151-171.*
Moors et al, “Cascading Content Addressable Memories,” IEEE Micro, vol. 12, No. 3, Jun. 1, 1997, pp. 56-66.*
“Self-Timed Hit Circuit for A Content Addressable Memory,” IBM Tech. Disc. Bull., vol. 38, No. 2, Feb. 1, 1995, pp. 65-66.*
Yamagata et al, “A 288-kb Fully Parallel Content Addressable Memory Using A Stacked Capacitor Cell Structure,” IEEE Journal of Solid State Circuits, vol. 27, No. 12, Dec. 1, 1992, pp. 1927-1933.
Gibson Garnet Frederick Randall
Schultz Kenneth James
Shafai Farhad
Gossage Glenn
Haszko Dennis R.
Nortel Networks Limited
LandOfFree
Content addressable memory system with cascaded memories and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Content addressable memory system with cascaded memories and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory system with cascaded memories and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2602452