Low power, hash-content addressable memory architecture

• US 8,788,791 B2
• Filed: 01/06/2012
• Issued: 07/22/2014
• Est. Priority Date: 11/01/2001
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Slavin, Keith R.
• Primary Examiner(s): Elmore, Reba I
• Application Number:
  US13/345,530
• Publication Number:
  US 20120117319A1
• Time in Patent Office: 928 Days
• Field of Search: 711/108, 711/216, 711/221
• US Class Current: 711/216
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 3/0628 making use of a particular technique
• 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
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00

Abstract

A comparand word is input to a plurality of hash circuits with each hash circuit responding to a different portion of the comparand word. The hash circuit outputs a hash signal which enables or pre-charges portions of a content addressable memory (CAM). The comparand word is also input to the CAM. The CAM compares the comparand word in the pre-charged portions of the CAM and outputs information responsive to the comparison. When Internet addresses are processed, the output information may be port information or an index for locating.

Claims

1. An apparatus, comprising:

a content addressable memory;

a plurality of hash circuits each configured to produce a respective hash signal responsive to a prefix of a comparand word for prefix lengths greater than n-bits;

a memory configured to produce a hash signal responsive to the prefix of the comparand word for prefix lengths n-bits or less; and

enable logic configured to receive the hash signals from the plurality of hash circuits and the memory and further configured to enable portions of the content addressable memory based on the hash signals, the enabled portions of the content addressable memory to be compared with the comparand word.

2. The apparatus of claim 1 wherein each of the hash circuit comprises:

hash logic configured to generate a hash output signal responsive to the prefix of the comparand word; and

a hash memory coupled to the hash logic and responsive to the hash output signal.

3. The apparatus of claim 2 wherein the hash output signal identifies a portion of the content addressable memory and the enable logic enables the portion identified by the hash output signal.

4. The apparatus of claim 1 wherein each of the plurality of hash circuits is responsive to a different prefix length.

5. The apparatus of claim 1, further including a processor configured to initialize and load information to the content addressable memory, the plurality of hash circuits and the memory.

6. The apparatus of claim 1, further comprising an output memory coupled to the content addressable memory and configured to store port information.

7. The apparatus of claim 1, further comprising a delay circuit configured to input comparand words to the content addressable memory.

8. A method, comprising:

providing an input word to a plurality of hash circuits, each hash circuit configured for a different respective prefix length;

outputting a hash signal from each hash circuit;

enabling portions of a CAM in response to the hash signals;

providing the input word to the CAM;

comparing the input word to the enabled portions of the CAM; and

outputting information responsive to the comparing.

9. The method of claim 8, further comprising an input memory device configured to handle a first number of prefixes of the input word, and wherein the hash circuits are configured to handle the remaining prefixes of the input word.

10. The method of claim 8 wherein enabling portions of the CAM comprises precharging the portions of the CAM.

11. The method of claim 8 wherein the enabling step comprises

selecting from a plurality of stored signals based on the hash signals, and enabling portions of the CAM based on the selected stored signals.

12. The method of claim 11 wherein the selected stored signals comprises a starting index and a run length.

13. The method of claim 11 wherein the selected stored signals comprises a starting index and an ending index.

14. The method of claim 8 wherein outputting information responsive to comparing comprises outputting a port value responsive to comparing.

15. A method, comprising:

mapping destinations to ports;

hashing network addresses;

loading hash values and address prefixes into a hash table;

linking routing addresses and port information to said hash values;

loading information from the hash table into a CAM; and

writing hole values in the CAM.

16. The method of claim 15, further comprising overwriting a hole value in the CAM with information from the hash table.

17. The method of claim 15 wherein writing hole values in the CAM comprises writing a hole value to delete information loaded in the CAM.

18. The method of claim 15 wherein the hole values are an illegal network address.

19. The method of claim 15 additionally comprising the step of confirming that all network addresses for each prefix are unique.

20. The method of claim 15 wherein loading information from the hash table into the CAM comprises transferring network addresses to the CAM based on an index to the hash table.

21. The method of claim 15, further comprising transferring port numbers to an output memory device responsive to the CAM.