Content addressable memory system with self-timed signals...

Details Content addressable memory system with self-timed signals... Content addressable memory system with self-timed signals...

2000-02-10

2001-04-17

Gossage, Glenn (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C365S049130, C365S210130

Reexamination Certificate

active

06219749

ABSTRACT:

TECHNICAL FIELD
The present invention relates to a content addressable memory (CAM) system in which a plurality of CAM arrays are cascaded.
BACKGROUND INFORMATION
Content addressable memories (CAMs) are known. In 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. 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 array. Multiple CAM arrays, possibly on multiple chips, are then required, and it is necessary to cascade the multiple CAM arrays such that they may be searched as a single entity. An appropriate “user-friendly” cascading capability enables the same CAM array 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; a plurality of content addressable memory (CAM) arrays, each CAM array comprising encoding means and an array of core cells, of w words×b bits, associated with the encoding means, each CAM array being able to provide, through its respective encoding means, a hit signal and a match address signal resulting from a search operation in response to a clock signal; and a plurality of logic circuits, each logic circuit being associated with a respective CAM array to receive the hit signal and the match address signal provided therefrom. Each logic circuit comprises: (i) timing signal generation means for generating a self-timed signal in response to the clock signal; (ii) hit propagation circuit for providing a propagation-out hit signal to a downstream logic circuit, by logically combining: a propagation-in hit signal provided from an upstream logic circuit; the hit signal provided from the respective CAM array; and the self-timed signal provided from the timing signal generation means; and (iii) match address transfer circuit for transferring the match address signal provided from the respective CAM array to the common bus.
In the system according to the present invention, the hit, match address and multiple match signals are provided from the CAM arrays to the logic circuits associated CAM arrays. The hit signals provided from the CAM arrays are propagated from upstream to downstream logic circuits in response to the self-timed signal. The logic circuits prevent more than one match address signal from being transferred simultaneously to the common bus. By observing the propagated hit signal provided from the furthest downstream logic circuit and the match address signal on the common bus, a hit result of the system in a search operation is provided.
According to the present invention, it is possible to implement a plurality of CAM arrays that has the same kind of search result outputs as a single CAM (e.g., hit, match address). It is thus possible that n CAM arrays, each with a capacity of w entries (or words), are integrated into a single multi-chip CAM system with n×w words.
According to another aspect of the present invention, there is provided a system wherein each of the plurality of CAM arrays is further able to provide, through its respective encoding means, a multiple match signal resulting from a search operation in response to the clock signal and each of the plurality of logic circuits further comprises a multiple match propagation circuit for providing a propagation-out multiple match signal to a downstream logic circuit, in response to the propagation-in hit signal provided from the upstream logic circuit, the hit signal provided from the respective CAM array, the multiple match signal provided from the respective CAM array and a propagation-in multiple match signal provided from the upstream logic circuit.
In the system, the multiple match signals provided from the CAM arrays are propagated from upstream to down stream logic circuits. For example, by observing the propagation-out multiple match signal provided from the furthest-downstream array, a multiple match status of the cascaded CAM arrays is provided.


REFERENCES:
patent: 4670858 (1987-06-01), Almy
patent: 5018111 (1991-05-01), Madland
patent: 5289403 (1994-02-01), Yetter
patent: 5568416 (1996-10-01), Kawana et al.
patent: 5828593 (1998-10-01), Schultz et al.
patent: 5859791 (1999-01-01), Schultz et al.
K.J. Schultz et al, “Architectures for Large Capacity CAM's” INEGRATION: the VLSI Journal, vol. 18, 1995, pp. 151-171.*
Moors et al, “Cascading Content Addressable Memories,” IEEE Micro, vol. 12, No. 3, Jun. 1992, pp. 56-66.*
“Self-Timed Hit Circuit for a Content Addressable Memory,” IBM Tech. Disc. Bull., vol. 38, No. 2, Feb. 1995, pp. 65-66.*
Yamagata et al, “A 288-Kb Fully Parallel Content Addressable Memory Using a Stacked Capacitor Cell Structure,” IEEE Jour. Sol. St-Ccts., Dec. 1992, pp. 1927-1933.

Affiliated with

Also associated with

Rating

Content addressable memory system with self-timed signals... 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 self-timed signals..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory system with self-timed signals... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2494912