Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2002-03-28
2004-07-13
Moazzami, Nasser (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06763426
ABSTRACT:
TECHNICAL FIELD
The present invention relates to content addressable memory (CAM) devices, and particularly to CAM based systems that can include multiple CAM devices.
BACKGROUND OF THE INVENTION
Content addressable memory (CAM) systems typically include one or more CAM devices. A CAM device can include circuitry for performing one or more types of search operations. In a search operation, a comparand (or key) may be compared to multiple entries to see if all or a portion of the key matches an entry. After a search operation, a CAM device may give a search result as an output. Typically a search result may include an “index” value which may be used to access associated data or to provide data itself.
CAM devices may take a variety of forms. As but a few of the possible examples, some CAM devices are based on particular types of CAM cells. Such cells may include storage circuits integrated with compare circuits. Examples of storage circuits may be static random access memory (SRAM) type cells or dynamic random access memory (DRAM) type cells. Alternate approaches may include random access memories (RAM) arrays, or the like, with separate matching circuits and/or processes.
To better understand the various features and aspects of CAM systems, and CAM system performance, two conventional CAM systems will now be described.
A first conventional CAM system is shown in FIG.
16
and designated by the general reference character
1600
. A conventional CAM system
1600
may include one or more CAM devices, each of which may perform a search operation. In the example of
FIG. 16
, a CAM system
1600
includes “n+1” CAM devices, shown as
1602
-
0
to
1602
-n. A CAM system
1600
may perform search operations in response to commands from a requesting device. In
FIG. 16
, a requesting device is a network processing unit (NPU)
1604
.
FIG. 16
shows an example of a bus based CAM system. In a bus based CAM system, CAM devices may be commonly connected to a requesting device and to one another by a common bus. Thus, in
FIG. 16
CAM devices (
1602
-
0
to
1602
-n) can be commonly connected to each other and to an NPU
1604
by a bus
1606
.
A drawback to bus based systems can be speed limitations. Larger interconnect lengths of bus lines as well as the input capacitances of each device can present considerable capactive loads for an NPU
1604
and CAM devices (
1602
-
0
to
1602
-n). Thus, while a bus based CAM system
1600
may be scaled up by increasing the number of CAM devices (
1602
-
0
to
1602
-n), such an approach may increase bus loading, reducing performance.
A bus based CAM system
1600
may have other drawbacks. Some sort of bus arbitration may be necessary to select one of multiple possible results. That is, while a search request may be issued from an NPU
1604
to CAM devices (
1602
-
0
to
1602
-n) simultaneously, individual search results for the CAM devices (
1602
-
0
to
1602
-n) can be generated, and some sort of mechanism may have to be included to select which particular response would be received separately by an NPU
1604
. Special bus arbitration hardware may allow a “winning” device to transmit a result to an NPU
1604
. Such bus arbitration hardware may be undesirably complex in the event a system includes software assigned priority between CAM devices (
1602
-
0
to
1602
-n).
Further, some additional processing is needed to process multiple results from multiple CAM devices. As but one example, more than one CAM device (
1602
-
0
to
1602
-n) may generate a match result in response to a key. Some sort of evaluation would then be necessary to establish a precedence between CAM devices (
1602
-
0
to
1602
-n). It is noted that such a precedence may make a system inflexible. As more and more CAM devices (
1602
-
0
to
1602
-n) are added, evaluating a search result can require that precedence between all devices must be known to ensure a highest precedence device result is provided as an output.
A second conventional CAM system is set forth in FIG.
17
and designated by the general reference character
1700
. A second conventional CAM system
1700
may include a number of CAM devices (
1702
-
0
to
1702
-
3
) having common connections to a command and data bus
1704
, as well as separate common connections to an index or result bus
1706
. Optionally, an index or result bus
1706
may be connected to one or more memory devices
1708
, such as a static random access memory (SRAM).
In a system like that shown in
FIG. 17
, a search command may be issued from a host device
1710
on a command and data bus
1704
. CAM devices (
1702
-
0
to
1702
-
3
) may process such commands and generate results, which may be output on an index or result bus
1706
. Results may be returned to a command issuing host device
1710
by way of a result bus. Optionally, results may be applied to one or more memory devices
1708
to generate data that may then be accessed by a host device
1710
.
A second conventional system
1700
may suffer from many of the drawbacks noted above. If a number of CAM devices is increased, bus loading can grow correspondingly. Further, some sort of logical protocol may be necessary to establish priority between results of multiple CAMs. As the number of CAM devices grows, such a protocol may get more complex or involve greater time periods for execution.
In light of the above, it would be desirable to arrive at a CAM system that does not rely on a common bus between a request issuing device and multiple CAM devices, but at the same time can provide improved performance over conventional cascaded approaches.
It would also be desirable to arrive at some way of addressing the drawback of having to process multiple CAM device results in a CAM system.
It would also be desirable to arrive at a CAM device that may be cascaded with other like CAM devices, and yet not suffer from the various drawbacks of conventional CAM systems.
SUMMARY OF THE INVENTION
According to the present invention, a content addressable memory (CAM) system may include a plurality of CAM devices arranged in series. A CAM system may include at least one input port that receives requests to perform particular operations. A CAM system may also include at least one output port that may provide a response based on responses generated by each CAM device.
According to one aspect of the embodiments, each CAM device may include a request path for transferring a request received at an input port to one or more output ports. Thus, requests may flow through sequential CAM devices, and not on a common bus.
According to another aspect of the embodiments, each CAM device can vote between multiple responses. In particular, each CAM device may include a first vote portion. A first vote portion may generate an output response based on a “local” response generated by the CAM device and a “remote” response generated by some other CAM device at a previous location in the series.
According to another aspect of the embodiments, further voting capabilities may be provided by a second vote portion in each CAM device. A second vote portion may generate a response based on two or more remote responses, each generated by different CAM devices at previous locations in the series.
According to another aspect of the embodiments, one response may be based on multiple responses according to precedence data associated with each response. Such precedence data may take a variety of forms. In one arrangement, precedence data may include a status value and a chip value. A status value may be assigned to a particular response type or according to a programmed priority value. A chip value may be a unique value assigned to a CAM device generating a response. Selection of response may be accomplished with a magnitude comparator circuit that compares status and chip values of responses.
According to another aspect of the embodiments, CAM devices in the system may be arranged into two or more branches. Thus, requests may be supplied to multiple branches by “branching” CAM devices. Similarly, responses from multiple bran
James David V.
Rajamanickam Jagadeesan
Cypress Semiconductor Corporation
Moazzami Nasser
Sako Bradley T.
LandOfFree
Cascadable content addressable memory (CAM) device 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 Cascadable content addressable memory (CAM) device and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cascadable content addressable memory (CAM) device and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3216161