Low power, hash-content addressable memory architecture

• US 20030093616A1
• Filed: 11/01/2001
• Published: 05/15/2003
• Est. Priority Date: 11/01/2001
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Slavin, Keith R.
• Granted Patent: US 8,112,578 B2
• Time in Patent Office: Days
• US Class Current: 711/108
• 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 method is comprised of inputting a comparand word to a plurality of hash circuits, each hash circuit being responsive to a different portion of the comparand word. The hash circuits output a hash signal which is used to enable or precharge portions of a CAM. The comparand word is also input to the CAM. The CAM compares the comparand word in the precharged portions of the CAM and outputs information responsive to the comparing step. When used to process Internet addresses, the information output may be port information or an index from which port information may be located. A circuit is also disclosed as is a method of initializing the circuit.

Claims

1. A method, comprising:

inputting an input word to a plurality of hash circuits, each hash circuit being responsive to a different portion of said input word;

outputting a hash signal from each hash circuit;

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

inputting said input word to said CAM;

comparing said input word in the enabled portions of said CAM; and

outputting information responsive to said comparing step.

2. The method of claim 1 additionally comprising the step of assigning a mask to each hash circuit such that each hash circuit is responsive to a different n-bit portion of said input word.

3. The method of claim 1 additionally comprising the step of inputting the least significant n bits of said input word to a memory, and wherein said outputting step includes the step of selecting between information responsive to a match being found in said memory and information responsive to a match being found in said CAM.

4. The method of claim 1 additionally comprising the step of delaying the inputting of said input word to said CAM until said enabling step is completed.

5. The method of claim 1 wherein said enabling step includes the step of using said hash signals to select from a plurality of stored signals, and using the selected stored signals to enable a portion of said CAM.

6. The method of claim 5 wherein said step of using the selected stored signals includes using a starting index and a run length.

7. The method of claim 5 wherein said step of using the selected stored signals includes using a starting index and an ending index.

8. A method of operating a CAM, comprising:

hashing a comparand word;

precharging certain portions of a CAM in response to said hashing step; and

inputting said comparand word to said CAM.

9. The method of claim 8 wherein said hashing step includes the steps of hashing different n-bit portions of said comparand word.

10. The method of claim 8 additionally comprising the steps of inputting the least significant n bits of said comparand word to a memory, and outputting information responsive to one of a match being found in said memory and a match being found in said CAM.

11. The method of claim 8 additionally comprising the step of delaying the inputting of said comparand word to said CAM until said precharging step is completed.

12. The method of claim 8 wherein said precharging step includes the steps of using said hash signals to select from a plurality of stored signals, and using the selected stored signals to precharge portions of said CAM.

13. The method of claim 12 wherein said step of using the selected stored signals includes using a starting index and a run length.

14. The method of claim 12 wherein said step of using the selected stored signals includes using a starting index and an ending index.

15. A method of operating a CAM for processing address information, comprising:

inputting an Internet address to a plurality of hash circuits, each hash circuit being responsive to a different portion of said address;

outputting a hash signal from each hash circuit;

using said hash signals to identify portions of a CAM;

inputting said address to said CAM;

comparing said address in only the identified portions of said CAM; and

outputting port information in response to a match being found in said CAM.

16. The method of claim 15 additionally comprising the step of assigning a mask to each bash circuit such that each hash circuit is responsive to a different n-bit portion of said address.

17. The method of claim 15 additionally comprising the step of inputting the least significant n bits of said address to a memory, and wherein said outputting step includes the step of selecting between port information associated with a match in said memory and port information associated with a match in said CAM.

18. The method of claim 15 additionally comprising the step of delaying the inputting of said address to said CAM until portions of said CAM have been precharged in response to said hash signals.

19. The method of claim 15 wherein said step of using said hash signals includes the steps of using said hash signals to select from a plurality of stored signals, and using the selected stored signals to precharge portions of said CAM.

20. The method of claim 19 wherein said step of using the selected stored signals includes using a starting index and a run length.

21. The method of claim 19 wherein said step of using the selected stored signals includes using a starting index and an ending index.

22. A method of operating a CAM for processing address information, comprising:

hashing different prefixes within an Internet address;

precharging certain portions of a CAM in response to said hashing step;

comparing said Internet address in said precharged portions of the CAM; and

outputting information in response to a match being found in the CAM.

23. The method of claim 22 additionally comprising the step of inputting the least significant n bits of said address to a memory, and wherein said step of outputting information includes the step of selecting between information associated with a match in said memory and information associated with a match in said CAM.

24. The method of claim 22 additionally comprising the step of delaying said comparing step until said precharging step is completed.

25. The method of claim 22 wherein said precharging step includes the steps of using said hash signals to select from a plurality of stored signals, and using the selected stored signals to precharge portions of the CAM.

26. The method of claim 25 wherein said step of using the selected stored signals includes using a starting index and a run length.

27. The method of claim 25 wherein said step of using the selected stored signals includes using a starting index and an ending index.

28. A circuit, comprising:

a CAM for receiving a comparand word;

a plurality of hash circuits connected in parallel, each for producing a hash signal in response to a portion of the comparand word; and

a circuit, responsive to said hash signals, for precharging portions of said CAM.

29. The circuit of claim 28 wherein said circuit responsive to said hash signals includes a plurality of memory devices responsive to said hash signals and enable logic responsive to said plurality of memories.

30. The circuit of claim 29 wherein said plurality of memory devices includes a plurality of SRAMs.

31. The circuit of claim 28 additionally comprising an output memory device responsive to said CAM for outputting information in response to a match in said CAM.

32. The circuit of claim 31 additionally comprising an input memory device responsive to a portion of the comparand word, and a switch responsive to said input memory device and said output memory device.

33. The circuit of claim 28 additionally comprising a processor, said CAM, said plurality of hash circuits, and said circuit responsive to said hash circuits receiving information from said processor.

34. A circuit, comprising:

a CAM;

a plurality of hash circuits each for producing a hash signal in response to a portion of a comparand word;

a plurality of memory devices responsive to said hash circuits;

enable logic, responsive to said plurality of memory devices, for enabling portions of said CAM; and

a delay circuit for inputting the comparand word to said CAM.

35. The circuit of claim 34 wherein said plurality of memory devices includes a plurality of SRAMs.

36. The circuit of claim 34 additionally comprising an output memory device responsive to said CAM for outputting information in response to a match in said CAM.

37. The circuit of claim 36 additionally comprising an input memory device responsive to a portion of the comparand word, and a switch responsive to said input memory device and said output memory device.

38. The circuit of claim 34 additionally comprising a processor for initializing said hash circuits, said plurality of memory devices and said CAM.

39. A method, comprising:

receiving routing information;

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; and

loading information from the hash table into a CAM.

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

41. A method of initializing hardware, comprising:

transferring network addresses to a CAM based on an index to a hash table;

transferring port numbers to an output memory device responsive to the CAM;

modifying bit prefix values to obtain a ternary representation;

calculating bank run length information; and

loading starting address and bank run length information into a plurality of memory devices.

42. The method of claim 41 additionally comprising periodically transferring invalid network addresses to the CAM.

43. The method of claim 41 additionally comprising transferring port information to an SRAM for prefixes below a certain length.

44. The method of claim 41 wherein said bank run length information includes one of an end address and an address span.