Content addressable memory architecture

• US 20070011436A1
• Filed: 06/01/2005
• Published: 01/11/2007
• Est. Priority Date: 06/01/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bittner, Ray
• Granted Patent: US 7,793,040 B2
• Time in Patent Office: Days
• US Class Current: 712/27
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array

Abstract

A content addressable memory (CAM) architecture comprises two components, a small, fast on-chip cache memory that stores data that is likely needed in the immediate future, and an off-chip main memory in normal RAM. The CAM allows data to be stored with an associated tag that is of any size and identifies the data. Via tags, waves of data are launched into a machine'"'"'s computational hardware and re-associated with related tags upon return. Tags may be generated so that related data values have adjacent storage locations, facilitating fast retrieval. Typically, the CAM emits only complete operand sets. By using tags to identify unique operand sets, computations can be allowed to proceed out of order, and be recollected later for further processing. This allows greater computational speed via multiple parallel processing units that compute large sets of operand sets, or by opportunistically fetching and executing operand sets as they become available.

Claims

1. A system comprising:

computational hardware containing at least one element configured to act as an operator; and

a content addressable memory mechanism, the content addressable memory mechanism comprising, a tag mechanism that determines from a set of at least one input tag whether an operand set of data is complete, and emits each operand set to the computational hardware when complete to receive a computational result from the computational hardware, and the tag mechanism associating another tag with the computational result.

2. The system of queued claim 1 wherein the content addressable memory mechanism comprises a cache closely coupled to the computational hardware and an external memory.

3. The system of claim 2 wherein the cache is physically contained on a chip containing the computational hardware, and the cache is coupled to the computational hardware via an interconnect network.

4. The system of claim 3 wherein the interconnect network comprises a crossbar network.

5. The system of claim 2 wherein the external memory comprises random access memory, and wherein a tag contains an index into a jump table that points to an index table set of at least one index table, the index table set referencing a page table having at least one reference to target data and status bits corresponding to the target data.

6. The system of claim 1 wherein the tag mechanism includes means for locating a set of individual tags based on a partially specified tag.

7. The system of claim 1 wherein the tag mechanism matches the set of individual tags in the content addressable memory and retrieves the set as a range of individual tags in succession.

8. The system of claim 1 wherein the tag mechanism includes means for sorting by using a key value as part of a tag and allowing tag ranges to be retrieved in sorted order.

9. The system of claim 1 wherein the other tag associated with the computational result has a fixed relationship to an input tag corresponding to an operand.

10. The system of claim 1 wherein a tag includes a set of first set of bits that specify a tag space to which the tag belongs, a second set of bits that specify a particular operand set to which the tag belongs, and a third set of bits that indicate which operand within that operand set with which corresponding data is associated.

11. The system of claim 1 wherein the other tag associated with the computational result has a functional relationship to an input tag corresponding to an operand.

12. The system of claim 1 wherein the content addressable memory contains elements with corresponding element indices adjacent to one another to form complete and partial operand sets, and wherein the content addressable memory emits completed operand sets for mathematical combination and does not emit incomplete operand sets to avoid unnecessary processing.

13. In a computing environment, a method comprising:

maintaining operand data that corresponds to an operand set;

emitting the operand set to computational hardware;

receiving a computational result from the computational hardware; and

maintaining the computational result in association with an output tag that corresponds to the operand set.

14. The method of claim 13 wherein the operand data is maintained in association with an input tag, and further comprising, generating the output tag based on the input tag.

15. The method of claim 13 further comprising, identifying the operand set based on a partial input tag, and wherein the operand set is emitted to the computational hardware when the operand set is complete.

16. At least one computer-readable medium having computer-executable instructions, which when executed perform the method of claim 13.

17. In a computing environment, a system comprising, a content addressable memory including a mechanism that maintains operands in association with tags;

computational hardware that is at least in part arranged as configurations that perform operations, each configuration comprising the operations of part of a dataflow graph; and

an execution mechanism that controls loading of a current configuration of the configurations, the content addressable memory emitting operands to the current configuration, and the content addressable memory and/or computational hardware providing information to the execution mechanism to establish which one of the configurations is to become a next current configuration.

18. The system of claim 17 wherein the configurations are configured in reconfigurable hardware.

19. The system of claim 17 wherein the content addressable memory mechanism comprises a cache closely coupled to the computational hardware and an external memory.

20. The system of claim 17 wherein at least some of the operands are maintained in the content addressable memory and/or flow through the configurations in a digit serial arithmetic scheme.