Low power, hash-content addressable memory architecture

• US 8,949,574 B2
• Filed: 07/14/2014
• Issued: 02/03/2015
• 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): LANE, JOHN A
• Application Number:
  US14/330,327
• Publication Number:
  US 20140325139A1
• Time in Patent Office: 204 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 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 system, comprising:

routing logic configured to determine routing of a data packet based on a comparison of a comparand word of the data packet with a stored comparand word, and wherein the routing logic comprises;

content addressable memory configured to store a plurality of comparand words, each of the plurality of comparand words associated with a destination; and

enable logic configured to enable a portion of the content addressable memory responsive to a hash signal, wherein the hash signal is based on a hash of a prefix of the comparand word;

wherein the comparand word is compared with the plurality of comparand words stored in the enabled portion of the content addressable memory.

2. The system of claim 1, wherein the routing logic is included in an internet protocol packet router and the data packet is an internet protocol packet that includes an internet protocol routing address.

3. The system of claim 1, wherein the routing logic is configured to receive the data packet at a first port and provide the data packet to a second port based on the comparison of the comparand word included in the data packet with the stored comparand word.

4. The system of claim 3, the routing logic further comprising a port memory configured to store a port designation associated with the plurality of comparand words and further configured to provide the designation for the second port based on the comparison of the comparand word included in the data packet with the stored comparand word.

5. The system of claim 1, the routing logic further comprising a plurality of hash circuits configured to perform a hash on the prefix of the comparand word and provide the hash signal to the enable logic, and wherein each of the plurality of hash circuits is responsive to a different prefix length.

6. The system of claim 1, wherein the routing logic is included in a router and is coupled to a plurality of other routers through a plurality of ports, and wherein the routing logic receives the data packet on a first port and provides the data packet to a second port to be routed to one of the plurality of other routers.

7. The system of claim 1, wherein the routing logic updates a routing table based on routing information received from a router coupled to the routing logic, and wherein the routing information includes comparand words to store in the content addressable memory and further includes an associated port destination to store in a port memory included in the routing logic.

8. A device, comprising:

a router including a plurality of ports and configured to receive a data packet on a first port and route the data packet to a second port based on a routing table, wherein the router is further configured to determine the second port based on a comparison of a comparand word of the received data packet with a plurality of comparand words stored in a hash-enabled content addressable memory, and wherein the stored comparand word designates a port in the routing table; and

wherein the router comprises;

a plurality of hash circuits each configured to produce a respective hash signal responsive to a prefix of the comparand word and wherein each of the plurality of has circuits is responsive to a different large prefix length;

a memory configured to produce a hash signal responsive to the prefix of the comparand word for small prefix lengths, and

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

9. The device of claim 8, wherein the routing table is updated in response to the router receiving routing information from a plurality of routing devices.

10. The device of claim 8, wherein the router includes a processor configured to update the plurality of comparand words stored in the content addressable memory based on updates to the routing table.

11. The device of claim 10, wherein the processor is further configured to map the plurality of comparand words to the plurality of ports.

12. The device of claim 11, wherein more than one comparand word may be mapped to a single one of the plurality of ports.

13. The device of claim 8, further comprising an output memory coupled to the content addressable memory and configured to store port information based on the routing table.

14. A device, comprising:

a router configured to receive a data packet at a first port and provide the data packet to a second port based on a comparison of a comparand word of the data packet and a stored comparand word, wherein the comparand word is indicative of routing information of the data packet, and wherein the router comprises;

a content addressable memory configured to store a plurality of comparand words with each comparand word associated with a port;

a plurality of hash circuits each configured to produce a respective hash signal responsive to a prefix of a comparand word, and wherein each of the plurality of hash circuits are responsive to different prefix lengths; and

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

15. The device of claim 14, wherein a match of the comparand word with a comparand word stored in the content addressable memory indicates the second port.

16. The device of claim 14, wherein the router further comprises a plurality of ports and wherein each port of the plurality of ports is configured to both receive and transmit a data packet.

17. The device of claim 16, wherein the router is coupled to a plurality of other routers by the plurality of ports and the plurality of other ports provide respective routing information for updating a routing table of the router.

18. The device of claim 14, wherein a hash signal identifies a portion of the content addressable memory and the enable logic enables the portion identified by the hash signal.

19. The device of claim 14, wherein the data packet comprises an internet protocol packet that includes a routing address, and the router is configured to perform internet protocol packet routing.