Content addressable memory in which keys are embedded in comparators

• US 9,405,860 B1
• Filed: 03/11/2014
• Issued: 08/02/2016
• Est. Priority Date: 03/11/2014
• Status: Active Grant

• Current Assignee: L3 Technologies, Inc. (L3Harris Technologies, Inc.)
• Original Assignee: L-3 Communications Corporation (L3Harris Technologies, Inc.)
• Inventors: Trout, Larry R.
• Primary Examiner(s): Cardwell, Eric S
• Application Number:
  US14/204,684
• Time in Patent Office: 875 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories

Abstract

A content addressable memory (CAM) system can include a comparator core in which all of the keys of the CAM are embedded in comparator blocks. A search key can be provided to each of the comparator blocks, which can compare the search key to its embedded key and determine whether the search key matches the embedded key. The comparator blocks can be organized into paged sets in the comparator core such that only one of the comparator blocks in each paged set is selected and compares its embedded key to the search key at any given time. The comparator block selected in each paged set can be incremented until the search key has been compared to the keys embedded in all of the comparator blocks of the comparator core.

Claims

1. A content addressable memory (CAM) system comprising:

a search key input configured to receive an N-bit search key;

a comparator core configured to embed W N-bit embedded keys in W comparator blocks each configured to compare its embedded key to the N-bit search key, wherein each comparator block comprises M look up tables (LUTs) each programmed to embed an L-bit subset of the embedded key in the comparator block and having an L-bit input for an L-bit subset of the search key where M is greater than one and L is less than N, and wherein each comparator block outputs a match indication only if each L-bit subset of the search key matches each corresponding L-bit subset of the embedded key in the comparator block subject to any masked bits; and

a location decoder connected to outputs of the comparator blocks and configured to identify a location in the comparator core of one of the embedded keys that matches the search key.

2. The CAM system of claim 1, wherein programming embeds the embedded keys in the comparator blocks.

3. The CAM system of claim 1, wherein data inputs to each comparator block consist essentially only of N bits for the search key.

4. The CAM system of claim 1, wherein data inputs to each LUT consist solely of said L bits.

5. The CAM system of claim 1, wherein each LUT is an independently programmable logic block of a programmable semiconductor device.

6. The CAM system of claim 1, wherein the comparator core is configured to compare the search key to all of the W embedded keys substantially simultaneously.

7. The CAM system of claim 1, wherein data inputs to the comparator core consist essentially only of W*N bits for W copies of the search key.

8. The CAM system of claim 1, wherein the identified location in the comparator core of the matched embedded key comprises an identification of the comparator block in which the matched embedded key is embedded.

9. A content addressable memory (CAM) system comprising:

a search key input configured to receive an N-bit search key;

a page module configured to provide a B-bit page code for uniquely identifying P pages;

a comparator core configured to embed W N-bit embedded keys in W/P paged comparator blocks, wherein each paged comparator block comprises P sets of M look up tables (LUTs) with each of the P sets embedding one of the embedded keys such that each paged comparator block embeds P embedded keys, and wherein each of the M LUTs embeds an S-bit subset of the corresponding embedded key, each of the P sets also being associated with a different B-bit page code;

wherein each paged comparator block is configured to compare the search key to one of its P embedded keys that corresponds to a particular value of the page code provided by the page module, and wherein each paged comparator block comprises programmable logic programmed to output a match indication only if;

the search key matches one of the P embedded keys embedded in the paged comparator block subject to any masked bits, and

the particular value of the page code matches the page code associated with the set of LUTs where the matched key is embedded; and

a location decoder connected to outputs of the paged comparator blocks and configured to identify a location in the comparator core of the matched key.

10. The CAM system of claim 9, wherein:

data inputs to each paged comparator block consist essentially only of N bits for the search key and M*B bits for M copies of the page code, and

M is an integer that is greater than or equal to one.

11. The CAM system of claim 10, wherein each LUT has an L-bit input for an S-bit subset of the search key and the B-bit page code received at the page input,

M is greater than one,

S is less than N, and

S+B=L.

12. The CAM system of claim 11, wherein data inputs to each LUT consist solely of the L bits.

13. The CAM system of claim 11, wherein each LUT is an independently programmable logic block of a programmable semiconductor device.

14. The CAM system of claim 11, wherein data inputs to the comparator core consist essentially only of (W/P)*N bits for W/P copies of the search key and (M*B)*(W/P) bits for M*(W/P) copies of the page code.

15. The CAM system of claim 9, wherein the comparator core is configured to compare the search key to W/P of the embedded keys substantially simultaneously.

16. The CAM system of claim 15, wherein the W/P of the embedded keys comprise one of the embedded keys embedded in each of the paged comparator blocks.

17. The CAM system of claim 9, wherein the identified location in the comparator core of the matched key comprises an identification of the paged comparator block in which the matched key is embedded and the associated page code.

18. A process of operating a content addressable memory (CAM), comprising:

receiving an N-bit search key at a search key input to the CAM;

simultaneously comparing the search key to W N-bit embedded keys embedded in W comparator blocks of a comparator core of the CAM, wherein each comparator block comprises M look up tables (LUTs) each programmed to embed an L-bit subset of the embedded key in the comparator block and having an L-bit input for an L-bit subset of the search key where M is greater than one and L is less than N, and wherein each comparator block outputs a match indication only if each L-bit subset of the search key matches each corresponding L-bit subset of the embedded key in the comparator block subject to any masked bits, and

outputting from the CAM a location in the comparator core of one of the W embedded keys that matches the search key.

19. The process of claim 18, wherein providing a subset of the search key to each LUT comprises providing each bit of the subset of the search key as a single bit input to the LUT.

20. A process of operating a content addressable memory (CAM) comprising a comparator core in which are embedded W N-bit embedded keys, wherein the comparator core comprises W/P paged comparator blocks each embedding P of the embedded keys, wherein each paged comparator block comprises P sets of M look up tables (LUTs) with each of the P sets embedding one of the embedded keys, and wherein each of the M LUTs embeds an S-bit subset of the corresponding embedded key, each of the P sets also being associated with a different one of P pages, the processing comprising:

receiving an N-bit search key at a search key input to the CAM;

simultaneously comparing in the W/P paged comparator blocks the search key to W/P of the embedded keys associated with a p^th one of the pages of the paged comparator blocks; and

at least until identifying a location in the comparator core of one of the embedded keys that matches the search key or cycling through all of the pages, changing the page code and repeating the comparing step and the changing step.

21. The process of claim 20 further comprising outputting from the CAM a location in the comparator core of one of the W embedded keys that matches the search key.

22. The process of claim 20, wherein the comparing further comprises:

providing a different S-bit subset of the search key to each LUT of the paged comparator block,

providing a B-bit page code to each LUT of the paged comparator block, and

each LUT outputting a match indication only if its subset of the search key matches its embedded subset of the embedded key and associated page.

23. The process of claim 22, wherein:

each LUT consists solely of an L-bit input,

S is less than N,

B is sufficient to uniquely define the P pages, and

L is greater than or equal to S+B.

24. The process of claim 23, wherein the comparing further comprises providing to each LUT only the S-bit subset of the search key and the B-bit page code.