Data compression for LPM in TCAM

A content addressable memory circuit comprising:

• an interface to receive an IP address key;
• a memory array that includes multiple respective memory devices that include memory locations that share a common address and are coupled for simultaneous access;
• hash logic operative to use modulo math to determine a shared common memory address within the memory array based upon non-X values within a received IP address key;
• wherein a plurality of memory locations within memory devices of the memory array each stores non-X values of a different IP address key in a format that includes a field-size value indicative of how many non-X IP values are stored at the memory location;
• multiple respective selector logic circuits, each operatively coupled to receive a field-size value output from a corresponding memory device;
• multiple respective comparator circuits, each operatively coupled to a receive non-X address key values output from a corresponding memory device;
• and
• memory control logic operative during a read operation in response to the received IP address key, to cause multiple respective memory devices to output stored field-size values and non-X IP address key values from memory locations at the determined shared common memory address;
• wherein each selector logic circuit is operative in response to the read operation to determine a respective number of non-X value comparisons that a corresponding comparator circuit is to make based upon a respective field size value output from a corresponding memory device;
• and
• wherein each comparator circuit is operative in response to the read operation to compare the determined respective number of non-X values in the received IP address key with non-X values output from a corresponding memory device and to provide a respective comparison result.

A method to control a content addressable memory circuit that includes a memory array that includes multiple respective memory devices that include memory locations that share a common address and are coupled for simultaneous access, the method comprising:

• receiving an IP address key;
• using modulo math to determine a shared common memory address within the memory array based upon non-X values within a received IP address key and a modulus based upon a number of memory locations within the memory array;
• storing non-X values of different IP address keys at different memory locations in a format that includes at each different memory location a field-size value indicative of how many non-X values are stored at the different memory location;
• outputting stored field-size values and non-X IP address key values from memory locations in the memory array at the determined shared common memory address;
• for each memory address location that outputs a stored field-size value and non-X IP address key values, determining a respective number of non-X IP address key values of the received IP address key to compare based upon the outputted field size value;
• and
• for each memory address location that outputs a stored field-size value and non-X IP address key values, comparing the determined respective number of non-X IP address key values of the received IP address key with the outputted non-X IP address key value, and providing respective a comparison result.

A content addressable memory circuit comprising:

• an interface to receive IP address keys for use with a write operation or for use with a read operation;
• multiple random access memory devices that each includes a plurality of worldlines, each wordline of each random access memory device operable to store multiple data bits, wherein each wordline of each random access memory device corresponds to at least one wordline of each of the other random access memory devices, and wherein corresponding wordlines of different random access devices have shared wordline addresses and are coupled to permit simultaneous access;
• hash logic operative to use modulo math to determine shared wordline addresses within the random access memory devices, based upon non-X values within the received IP address keys;
• memory controller logic;
• wherein the memory controller logic is operative during a write operation to cause a random access memory device, from among the multiple random access memory devices, to store at a wordline having a shared address determined for an IP address key received for use with the write operation, non-X values of the IP address key received for use with the write operation and a corresponding field-size value that indicates how many non-X values are within the IP address key received for use with the write operation;
• and
• wherein the memory controller logic is operative during a read operation to cause each respective random access memory device, that stores respective non-X values of a respective IP address key previously received for use with the write operation and that stores a corresponding respective field size value at a respective wordline of the respective random access memory device having a shared memory address determined for an IP address key received for use with the read operation, to output the stored respective non-X values and the stored corresponding respective field size value from the respective wordline of the respective random access memory device having the shared memory address determined for the IP address key received at the interface for use with the read operation.

A method to access an IP address key in a memory array that includes multiple memory devices that each includes a plurality of memory locations, wherein each memory location has a memory address, and wherein corresponding memory locations of different memory devices have shared memory addresses and are coupled to permit simultaneous access, the method comprising:

• receiving one or more IP address keys at an interface for use with a write operation or with a read operation;
• using modulo math to determine shared memory addresses within the memory array, based upon non-X values within the IP address keys;
• during a write operation of the memory array, storing non-x values of an IP address key received for use with the write operation in a memory device, from among the multiple memory devices, at a memory location having a shared memory address determined for the IP address key received for use in the write operation, in a format that includes a corresponding field-size value indicative of a number of non-X values within the IP address key received for use in the write operation;
• and
• during a read operation of the memory array, causing memory devices from the memory array, that store non-X values of IP address keys previously received for use with the write operation and corresponding field size values at memory locations having a shared memory address determined for an IP address key received at the interface for use with the read operation, to output the stored non-X values of IP address keys and the stored corresponding field size values from memory locations having the shared memory address determined for the IP address key received at the interface for use with the read operation.