Cascadable content addressable memory and system

• US 5,930,359 A
• Filed: 09/23/1996
• Issued: 07/27/1999
• Est. Priority Date: 09/23/1996
• Status: Expired due to Term

• Current Assignee: General Dynamics C4 Systems Incorporated (General Dynamics Corporation)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: McAuley, Anthony J., Kempke, Robert Alan, Lamacchia, Michael P.
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): SAYADIAN, HRAYR
• Application Number:
  US08/717,557
• Time in Patent Office: 1,037 Days
• Field of Search: 711/108, 365/49, 380/9, 380/56, 380/59
• US Class Current: 713/160
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• 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

A system for a pipeline cascaded content addressable memory CAM system for sequentially processing input data includes an input register, a CAM core, cascade logic and an output register. As the memory association functions produce matches in the CAM core, the cascade logic in parallel composites data associated with each matching CAM core. Each cascade processes a separate data input simultaneously then passes on the cumulative results to the next stage.

Claims

1. A content addressable memory (CAM) system for processing incoming input data, comprising:

an input register for receiving the incoming input data, the incoming input data comprising a data word, cascade data, and op code data;

a CAM core comprising means for selectively storing certain of the incoming input data as stored CAM data at addressable locations and means for comparing incoming data to the stored CAM data;

cascade logic responsive to the incoming input data;

an output register coupled to the cascade logic and the CAM core, for providing output register outputs of a data output, an op code output, and a cascade output, responsive to the CAM core and the cascade logic; and

means for determining a match between the stored CAM data of the CAM core and the incoming input data, and for producing a match address location;

wherein the cascade logic is further comprised of cascade interface means for providing the cascade output indicating whether a match has occurred anywhere in the CAM core, and whether multiple matches have occurred, and the match address location representing a lowest order address where a match was found in the CAM core, and when no match has occurred for providing an output of the match address location of an address for a next location after a last addressable location within the CAM subsystem.

2. The CAM system as in claim 1, wherein the input register, the CAM core, the cascade logic, and the output register in combination form a CAM stage;

wherein there are a plurality of the CAM stages, coupled together in a cascaded chain of CAM stages comprising an initial stage, and subsequent stages at least including a final stage; and

wherein the plurality of the CAM stages comprise a pipelined system, wherein the output register for the final stage provides the output register outputs corresponding to a complete pipelined system CAM comparison for the incoming input data.

3. The CAM system as in claim 2, further comprising:

means for providing input CAM data, RAM data, Op code data, and Cascade data to the initial stage; and

timing means for providing synchronizing signals to the plurality of CAM stages to effectuate pipelined transfer of at least part of the input data between a plurality of the CAM stages.

4. The CAM system as in claim 1, wherein each of the data output, the op code output, and the cascade output from each of the plurality of CAM stages are coupled to the data word, cascade data, and op code data as the incoming input data to an input register of a subsequent CAM subsystem stage.

5. The CAM system as in claim 1, wherein the initial stage has its cascade data and op code input data signals coupled from an external host processor, and the initial stage has its cascade inputs coupled to a predefined set of signals.

6. The CAM system as in claim 5, wherein the predefined set of signals are a logic low level.

7. The CAM system as in claim 1, wherein the cascade logic further comprises means for providing multiple matching address locations responsive to the op code input data.

8. The CAM system as in claim 1, further comprising:

a RAM memory, for selectively storing and retrieving RAM data as associated data at locations addressable by associative mapping to respective corresponding CAM address locations in the CAM; and

means for logic-OR'"'"'ing, on a bit-wise basis, the associated data for multiple matching address locations.

9. A cascadable pipelined content addressable memory CAM system responsive to input CAM data, RAM data, Op code data, and Cascade data, the CAM system comprising:

an input register for storing and outputting the input CAM Data, RAM Data, Op code data, and Cascade data;

an output register;

a CAM core comprising CAM memory having a location associative RAM memory, and a CAM comparator;

wherein the input CAM data is first coupled to the input register, and then coupled to the CAM memory, and then coupled to the output register;

wherein the cascade data derives from a cascade logic subsystem coupled to the input register for combinationally determining cascade conditions and for providing an output of cascade conditions, responsive to the input CAM data;

means for comparing the input CAM Data to each and all individual CAM memory location contents responsive to the Op code data;

a multimatch buffer for storing a matching CAM location responsive to detecting a match and responsive to the Cascade data and coupled to the input register; and

a cascade logic subsystem determining cascade conditions and for providing an output of cascade conditions, responsive to the multimatch buffer.

10. The CAM system as in claim 9, wherein the cascade logic subsystem is further comprised of means for wire-OR'"'"'ing the RAM data for all associated matched locations with the cascade data from a previous stage to produce a wired-OR output.

11. The CAM system as in claim 10, wherein the output register provides a time-delayed version of the input CAM data, and provides a cascade output representative of the wired-OR output, and indicative of cascade conditions based on operations occurring within the CAM system, and outside the CAM system.

12. The CAM system as in claim 9, wherein an output from the input register corresponding to the RAM data and the Op code data is coupled to the output register and provides a time delayed cascade output.

13. The CAM system as in claim 9, further comprising

a binary-to-ternary converter coupled between the input register and the CAM memory of the CAM core;

wherein the input CAM data is converted from binary-to-ternary format before storing the incoming input data and before comparing the incoming input data to the CAM memory; and

wherein the multimatch buffer is coupled to a RAM comparator output, wherein the multimatch buffer provides an output representative of all locations in the CAM where a match exists between the input CAM data and entries stored in the CAM memory.

14. A cascadable pipelined content addressable memory (CAM) system, the CAM system comprising:

an input register for receiving input data comprising input CAM data, Op code data, and Cascade data that includes status data and RAM data;

a binary-to-ternary converter coupled to the input register for converting the CAM data therefrom into ternary CAM data responsive to write and compare conversion logic;

a CAM core comprising an associated CAM memory for storing data at one of a plurality of memory locations each having a unique associated address, a CAM comparator, each memory location in the CAM core having a specific address, the CAM memory and the CAM comparator coupled to the binary-to-ternary converter;

a multimatch buffer comprising a plurality of flip flops for indexed storage and retrieval of data associated with each of the plurality of CAM memory locations; and

a cascade logic subsystem determining cascade conditions and for providing an output of cascade conditions, responsive to the multimatch buffer

wherein the CAM comparator compares the ternary CAM data to the stored data for all CAM memory locations responsive to the input op code data; and

wherein an associated flip flop is activated for each CAM memory location found to be matching.

15. The CAM system as in claim 14, further comprising:

a sorter for determining a lowest order address, responsive to the multimatch buffer; and

an address generator for generating an address output match responsive to the sorter.

16. The CAM system as in claim 15, further comprising:

means for outputting addresses for multiple ones of the address output match.

17. The system as in claim 15, further comprising:

an address blocker to block the address output match responsive to a compare by the RAM comparator between the RAM data and a preloaded RAM mask to prevent a matched CAM core address from reaching the cascade logic subsystem.

18. The CAM system as in claim 14, further comprising:

an output register for storing the cascade data and CAM data from the input register responsive to the Op code data; and

means for transferring, after a time delay, the stored cascade data and CAM data as a next stage output.

19. The CAM system as in claim 14, further comprising:

means for inhibiting additional addresses from being accepted for input by the cascade logic subsystem.

20. The CAM system as in claim 19, wherein the means for inhibiting is further characterized as setting an address valid bit in the cascade logic subsystem.

21. The CAM system as in claim 14, wherein the cascade logic subsystem logically OR'"'"'s each bit position for all the CAM memory locations found to be matching to produce a composite RAM value.

22. A memory system for implementing a secure ATM communication system for an ATM network that transmits a plurality of cells, each of the plurality of cells comprising payload data and header data comprised of VPI and VCI address data, the memory system being responsive to a plurality of Data Input signals, encryption VPI and VCI addresses, and associated key data signals, the memory system comprising:

a pipelined cascadable content addressable memory (CAM) subsystem for storing CAM data to produce stored CAM data and for comparing the plurality of Data Input signals to the stored CAM data, and for providing a match output address when one of the plurality of Data Input signals matches the stored CAM data;

an addressable lookup table subsystem for storing the associated key data signals and selectively outputting key data responsive to the match output address;

wherein the CAM subsystem and the addressable lookup table subsystem form a memory subsystem; and

means for initializing the memory subsystem comprising;

means for storing the encryption VPI and VCI address data as the stored CAM data in the CAM subsystem;

means for storing the key data associated with the encryption VPI and VCI address data in the addressable lookup table subsystem;

means for separating the payload data from the header data for each of the plurality of cells;

means for coupling the separated header data to the CAM subsystem, wherein the CAM subsystem selectively provides the match output address when the separated header data at least partially matches the VPI and VCI address data stored in the CAM subsystem;

wherein the addressable lookup table provides an output of the key data associated with a respective match output address;

means for encrypting the payload data responsive to the key data; and

means for combining the encrypted payload data with the separated header data to form an encrypted cell.

23. The system as in claim 22, further comprising means for transmitting the encrypted cell to the ATM network.

24. A memory subsystem for implementing a secure ATM communication system that transmits a plurality of signals, comprising encryption key data, and cells, each of the cells comprised of payload data and header data comprised of VPI/VCI data, wherein respective ones of the encryption key data is associated with respective ones of the VPI/VCI data, the memory subsystem comprising:

a content addressable memory (CAM) subsystem, comprised of a plurality of CAM stages, coupled together as a pipelined system in an intercoupled cascaded chain of the plurality of CAM stages comprising an initial stage, and subsequent stages at least including a final stage; and

wherein each of the plurality of CAM stages is comprised of an input register, a CAM core, cascade logic, and an output register;

wherein the input register receives incoming data that includes a data word, cascade data, and op code data;

the CAM core comprising means for selectively storing certain of the incoming data as stored CAM data at addressable locations, and means for comparing the incoming data to the stored CAM data, responsive to the incoming data;

the cascade logic being responsive to the incoming data;

the output register being coupled to the cascade logic and the CAM core, for providing output register outputs that include a data output, an op code output, and a cascade output;

wherein the CAM core is further comprised of means for determining a match between the stored CAM data and the incoming data, and for producing a match address location output responsive thereto; and

wherein the cascade logic is further comprised of cascade interface means for providing the cascade output indicating whether a match has occurred anywhere in the CAM core, and means for determining whether multiple matches have occurred, wherein the match address location output represents a lowest order address where a match was found in the CAM core, and when no match has occurred, means for providing an output of the match address location output of an address corresponding to a next location after a last addressable location within the CAM subsystem; and

wherein the plurality of the CAM stages comprise a pipelined system, wherein the output register for the final stage provides the output register outputs corresponding to a complete pipelined system CAM comparison for the incoming input data.

25. The memory subsystem as in claim 24, further comprising:

an addressable lookup table;

a processor for storing VPI/VCI data into the CAM subsystem, each at a respective storage address, and for storing the respective associated encryption key data into the lookup table at a location mapped to the respective storage address;

a decoder for separating the header data from the payload data for each of the cells;

the CAM subsystem, providing means for comparing the stored data therein to the separated header data to selectively provide a match address output when the separated header matches any of the stored data therein;

wherein the lookup table is responsive to the match address output to provide an output of the associated encryption key data;

an encryptor, responsive to the encryption key data output from the lookup table for encrypting the separated payload data;

a combiner for combining the encrypted payload data with the separated header to form an encrypted cell; and

means for communicating the encrypted cell through standard ATM infrastructure systems.