Cascading content addressable memory devices with programmable input/output connections

• US 7,043,600 B2
• Filed: 05/12/2003
• Issued: 05/09/2006
• Est. Priority Date: 05/12/2003
• Status: Expired due to Term

• Current Assignee: MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management)
• Original Assignee: Integrated Silicon Solution Incorporated (Uphill Investment Co.)
• Inventors: Chow, Nelson L., Cheng, Paul C.
• Primary Examiner(s): Bataille, Pierre
• Assistant Examiner(s): TSAI, SHENG JEN
• Application Number:
  US10/249,842
• Publication Number:
  US 20040230740A1
• Time in Patent Office: 1,093 Days
• Field of Search: 711/108, 713/160
• US Class Current: 711/108
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

CAM devices that can be cascaded together to form CAM systems of different sizes are disclosed. The system has one or more clusters of M CAM devices, each device including (M−1) disable connections. Disable signals are used to avoid contention so that one CAM device generates the system output on a shared bus. To reduce pin count, the CAM device of priority N within each cluster has (N−1) of its disable connections programmed as inputs for disable-in signals received from higher-priority CAM devices, and its remaining (M−N) disable connections programmed as outputs for disable-out signals provided to lower-priority CAM devices. Some embodiments include two or more clusters of CAM devices and a controller. In some embodiments, the CAM system works as fast as a single CAM device. Some embodiments impose no architectural limits on the number of CAM devices that can be cascaded together.

Claims

1. A CAM system for generating an output on a bus in response to a key, the CAM system comprising:

at least two clusters that each include M CAM devices, wherein each CAM device has a priority N within the cluster to which it belongs, where N ranges from 1 to M, and each CAM device includes;

i) a CAM array configured to hold entries and to determine if each entry matches the key;

ii) (M−

1) disable connections, where the CAM device of priority N has (N−

1) of the disable connections programmed as inputs configured to receive disable-in signals from the (N−

1) higher-priority CAM devices within the cluster, and has the remaining (M−

N) disable connections programmed as outputs configured to provide a disable-out signal to the (M−

N) lower-priority CAM devices within the cluster; and

iii) a cascade circuit configured to disable the CAM device from driving the output onto the bus when any of the disable-in signals received by the CAM device are asserted; and

a controller configured to receive a cluster-match signal from the clusters and to generate a cluster-disable signal for the clusters, wherein the cluster-disable signal for a particular cluster is asserted when any cluster-match signal received by the controller from any cluster having higher priority than that particular cluster is asserted;

wherein each CAM device further includes a connection configured to receive the cluster-disable signal for the cluster containing the CAM device and a connection configured to provide the cluster-match signal for that cluster; and

wherein each cascade circuit is further configured to disable the CAM device from driving the output onto the bus when the cluster-disable signal is asserted.

2. The CAM system of claim 1, wherein the cluster-disable connection is a programmable connection and in a CAM memory system having only a single cluster the cluster-disable connection can be configured to support an additional CAM device within the single cluster.

3. The CAM system of claim 1, wherein the cluster-match connection is a programmable connection and in a CAM memory system having only a single cluster the cluster-match connection can be configured to support an additional CAM device within the single cluster.

4. The CAM system of claim 1, wherein each CAM device is an integrated circuit having the same design as the other CAM devices.

5. The CAM system of claim 1, wherein the maximum number of entries that can be held within at least one of the CAM devices is not equal to the maximum number of entries that can be held within another one of the CAM devices.

6. The CAM system of claim 1, wherein each CAM device further includes a priority encoder configured such that, the priority encoder selects one of the matching entries, encodes the selected entry into an encoded row, and drives the encoded row onto the bus as the output when at least one entry within the CAM array matches the key and when enabled by the cascade circuit.

7. The CAM system of claim 1, wherein each CAM device further includes a no-operation register that is configured to hold a no-operation value and that drives the no-operation value onto the bus as the output when there is no lookup operation in progress and the CAM device is the last CAM device in the CAM system.

8. The CAM system of claim 1, wherein each CAM device further includes a no-match register that is configured to hold a no-match value and that drives the no-match value onto the bus as the output when there is no entry in the CAM system that matches the key and the CAM device is the last CAM device in the system.

9. The CAM system of claim 1, wherein the entries and the key are binary, and the rows are further configured to determine that the key and the entry match when equal.

10. The CAM system of claim 1, wherein at least one of the key and the entry is ternary, and the rows are further configured to determine that the key and the entry match when bits selected by a mask within the key field and the entry field are equal.

11. The CAM system of claim 1, wherein the rows are further configurable either to hold a binary entry and to determine that the key field and the entry field match based on a binary determination, or to hold a ternary entry and to determine the key field and the entry field match based on a ternary determination.

12. A method of generating a CAM output on a bus in response to a key, the method comprising:

holding entries in at least one cluster of M CAM devices, wherein each CAM device has a priority N within the cluster to which the CAM device belongs, where N ranges from 1 to M;

programming (N−

1) programmable connections within each CAM device to receive a disable-in signal;

programming (M−

N) programmable connections within each CAM device to generate a disable-out signal;

loading into each CAM device a key;

searching for entries within each CAM device that match the key;

asserting from each CAM device the (M−

N) disable-out signals only when a matching entry is found within that CAM device;

receiving into each CAM device (N−

1) disable-in signals, each being the disable-out signal from one of the (N−

1) higher priority devices within the cluster to which that CAM device belongs;

encoding one of the matching rows and driving the encoded row onto the bus when there is at least one matching entry within a CAM device and when no disable-in signal received by that CAM device is asserted.

13. The method of claim 12, further comprising:

receiving into each CAM device a cluster-disable signal for the cluster of CAM devices to which the CAM device belongs;

generating from each cluster a cluster-match signal whenever at least one entry held within the CAM devices within that cluster matches the key;

not asserting the cluster-disable signal of the cluster that is the highest priority cluster that has an asserted cluster-match signal, and asserting the cluster-disable signals of the other clusters.

14. A CAM system for generating an output on a bus in response to a key, the CAM system comprising:

at least two clusters that each include M CAM means, wherein each CAM means has a priority N within the cluster to which it belongs, where N ranges from 1 to M, and each CAM means includes;

i) a means for holding entries and for determining if each entry matches the key;

ii) (M−

1) means, each programmable either as an input for receiving a disable-in signal from one of the (N−

1) higher-priority CAM means within the cluster or as an output for providing a disable-out signal to one of the (M−

N) lower-priority CAM means within the cluster; and

iii) means for driving the output from the CAM means onto the bus, wherein the driving means does not drive the bus when any of the disable-in signals received by the CAM means are asserted; and

means for generating a cluster-disable signal for each of the clusters, wherein the cluster-disable signal for each cluster is asserted when the cluster-match signal received by the controller from any cluster having higher priority than that cluster is

wherein each CAM means further includes means for receiving the cluster-disable signal for the cluster containing the CAM means and means for providing the cluster-disable signal for that cluster; and

wherein each driving means does not drive the output onto the bus either when the cluster-disable signal is asserted.