Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2000-06-16
2001-11-13
Mai, Son (Department: 2818)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S189070, C711S108000
Reexamination Certificate
active
06317350
ABSTRACT:
BACKGROUND
1. Field of Invention
This invention relates generally to semiconductor memories and specifically to content addressable memories.
2. Description of Related Art
A content addressable memory (CAM) device is a storage device having an array of memory cells that can be instructed to compare the specific pattern of a compared data with data words stored in corresponding rows of the array. The entire CAM array, or segments thereof, are searched in parallel for a match with the compared data. If a match exists, the CAM device indicates the match condition by asserting a match flag, and may indicate the existence of multiple matches by asserting a multiple match flag. The CAM device typically includes a priority encoder that provides the highest priority matching address (e.g., the lowest CAM index) to a status register. The highest priority matching address, the contents of the matched location, and other status information (e.g., skip bit, empty bit, full flag, as well as match and multiple match flags) may be output from the CAM device to an output bus.
CAM devices may be depth cascaded together to form a larger CAM device or system. For example, two 1k×64 CAM devices may be depth cascaded together to form a 2k×64 CAM.
Depth cascading may be implemented in a first configuration by forming a chain of CAM devices each having a match flag input pin and a match flag output pin, and for each CAM device, connecting its match flag output pin to the match flag input pin of the next CAM device. The first CAM device in the chain, which may represent the highest priority addresses (e.g., lowest CAM index), has its match flag input pin connected to a predetermined logic level to indicate that there is no previous CAM device. The match output pin of the last CAM device in the cascaded chain provides a system match flag indicative of match conditions in the CAM devices.
In response to a compare instruction, each CAM device simultaneously compares a compared word with data stored in its respective CAM array. If a CAM device has a match, it forwards its asserted match flag to the next CAM device (e.g., the next highest priority CAM device). The CAM device may then output its match address to a common output bus, and the lower priority CAM device will be disabled from outputting data to the common output bus. If, however, the CAM device does not have a match, it will not assert its match flag output, and the lower priority CAM device may provide its match address to the common output data bus (if it has a match).
If there are many CAM devices depth cascaded together, then the lowest priority CAM device in the cascade will only be able to output its data to the common output bus if no other CAM devices in the cascade have a match. In this first prior art configuration, the lowest priority CAM device must wait until the match flag signals from the previous CAM devices have rippled through each device in the cascaded chain. This may result in an undesirably long time to generate the system match flag, and for the last CAM device to output data to the common output data bus. Since match flag information must ripple through each device in this cascaded system, the time required to generate the system match flag, as well as the time required for the last CAM device to resolve its match priority, is linearly related to the number of cascaded devices, and may be expressed as t=t
mf
+(n−1)&agr;, where t
mf
is the time delay associated with generating a match flag for a CAM device, n is the number of cascaded devices, and a is the delay associated with combining match information from a previous CAM device with the internal match flag for the CAM device. Where many devices are cascaded in this manner, the time t=t
mf
+(n−1)&agr; may become large and no longer fit within a period of the system clock. As a result, the clock period may need to be increased to accommodate the delay in generating the system match flag and resolving priority, which in turn may adversely affect the operating frequency of the cascaded system.
One solution to increase speed is to provide the match flag of each CAM device to all lower priority devices in the cascaded chain. This second prior art configuration eliminates the gate delay associated with waiting for the higher priority match flags to ripple through the cascaded chain, but undesirably increases the number of match flag input pins required for each CAM device linearly with an increase in the number of cascaded devices. Since each CAM device would receive the match flags of all previous CAM devices in the chain, the last CAM device of such a system having n devices requires n−1 match flag input pins. Thus, although able to generate the system match flag much faster than the first prior art configuration, the second prior art configuration undesirably requires an additional match flag input pin for each additional cascaded device, and therefore consumes more silicon area than the first prior art configuration. In addition, connecting a match flag output pin to a match flag input pin of each lower-priority device may undesirably increase loading of the match flag output pin, which in turn may degrade performance.
Therefore, there is a need for a cascade configuration that achieves a balance between the number of match flag input pins required per cascaded device and the time required to generate a system flag for the cascaded devices.
SUMMARY
A method and apparatus are disclosed for hierarchically cascading a number of memory devices in a manner that achieves a balance between the number of match flag input pins and the time required to generate the system match flag. In some embodiments, the number of match pins required for each cascaded device and the time required to generate a system match flag are each logarithmically related to the number of cascaded devices. In one embodiment, an m-level hierarchy of groups are defined for up to n memory devices, where m=log
2
n and m is an integer greater than 2. The first hierarchy may include n/2 groups of 2 memory devices, the second hierarchy may include n/4 groups of 4 memory devices, and so on, where the last hierarchy may include one group of n devices. Each group in a given hierarchical level includes a pair of groups from the preceding hierarchical level. At each hierarchical level, the match flag generated by the first of the group's pair may be provided to the highest priority and the lowest priority device (e.g., the first and the last device) in the second of the group's pair. In some embodiments, the system match flag may be generated in a time t=t
mf
+m&agr;, where t
mf
is the time required to generate a match flag, and &agr; is the gate delay associated with logically combining an internal match flag with match flags received from other devices.
In other embodiments, at each hierarchical level, the match flag(s) generated by devices in the first of the pair defined in the previous hierarchical are selectively provided to all devices in the second of the pair defined in the previous hierarchical level. In such embodiments, the selective interconnections made between groups defined in different hierarchical levels may allow for generating the system match flag and resolving priority amongst the CAM devices in a time t=t
mf
+m&agr;.
In alternate embodiments, unused input match flag pins of selected cascaded devices may be coupled to receive match information from higher-priority devices to generate the system match flag and resolve priority in a time t=t
mf
+(m−1)&agr;.
Other objects, features, and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows.
REFERENCES:
patent: 4845668 (1989-07-01), Sano et al.
patent: 5010516 (1991-04-01), Oates
patent: 5072422 (1991-12-01), Rachels
patent: 5440715 (1995-08-01), Wyland
patent: 5621677 (1997-04-01), Jones
patent: 5649149 (1997-07-01), Stormon et al.
patent: 5841874 (1998-11-
Pereira Jose Pio
Srinivasan Varadarajan
Mai Son
NetLogic Microsystems, Inc.
Paradice III William L.
LandOfFree
Hierarchical depth cascading of content addressable memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical depth cascading of content addressable memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical depth cascading of content addressable memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2615135