Hierarchical immutable content-addressable memory processor

• US 8,065,476 B2
• Filed: 12/17/2009
• Issued: 11/22/2011
• Est. Priority Date: 01/26/2007
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Hicamp Systems Incorporated
• Inventors: Cheriton, David R.
• Primary Examiner(s): Elmore; Stephen
• Application Number:
  US12/653,889
• Publication Number:
  US 20100100673A1
• Time in Patent Office: 705 Days
• Field of Search: 711/108, 711/154, 711/156, 365/49.1
• US Class Current: 711/108
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/109 for multiple virtual address spaces, e.g. segmentation G06F12/1036 takes precedence
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0673 Single storage device
• 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: G11C 15/04 using semiconductor elements

Abstract

Improved memory management is provided according to a Hierarchical Immutable Content Addressable Memory Processor (HICAMP) architecture. In HICAMP, physical memory is organized as two or more physical memory blocks, each physical memory block having a fixed storage capacity. An indication of which of the physical memory blocks is active at any point in time is provided. A memory controller provides a non-duplicating write capability, where data to be written to the physical memory is compared to contents of all active physical memory blocks at the time of writing, to ensure that no two active memory blocks have the same data after completion of the non-duplicating write.

Claims

1. A computer system comprising:

a content-addressable physical memory including two or more physical memory blocks, each of said physical memory blocks having a fixed storage capacity, wherein some of said memory blocks are indicated as being in an active state and some of said memory blocks are indicated as being in an inactive state; and

a memory controller providing a non-duplicating write capability, wherein data to be written to said physical memory is compared to contents of a set of said memory blocks that are indicated as being in an active state at the time of writing to avoid storage of identical data after completion of the non-duplicating write.

2. The system of claim 1, wherein said memory controller provides a multi-block non-duplicating write capability that includes a multi-block data convention specifying a representation for data items requiring two or more of said physical memory blocks to store whereby said non-duplicating write capability is extended to avoid duplicates of multi-block data in said active physical memory blocks.

3. The system of claim 1, wherein each of said physical memory blocks has the same storage capacity.

4. The system of claim 1, further comprising a processor in communication with said memory controller wherein said processor is capable of writing to said physical memory only by way of said non-duplicating write capability.

5. The system of claim 1, wherein said physical memory is volatile.

6. The system of claim 1, wherein the set of memory blocks that are compared includes all of said memory blocks that are indicated as being in an active state at the time of writing.

7. A method of computer system memory management comprising:

in a content-addressable physical memory having two or more physical memory blocks, each of said physical memory blocks having a fixed storage capacity, indicating that some of said memory blocks are in an active state and some of said memory blocks are in an inactive state; and

using a memory controller to compare data to be written to said physical memory to contents of a set of said memory blocks that are indicated as being in an active state at the time of writing to avoid storage of identical data after completion of the non-duplicating write.

8. The method of claim 7, further comprising:

specifying a representation for data items requiring two or more of said physical memory blocks to store according to a multi-block data convention whereby said non-duplicating write capability is extended to avoid duplicates of multi-block data in said active physical memory blocks.

9. The method of claim 7, wherein indicating that some of said memory blocks are in an active state and some of said memory blocks are in an inactive state comprises:

regarding a physical memory block as active if it has been initialized or allocated.

10. The method of claim 7, wherein indicating that some of said memory blocks are in an active state and some of said memory blocks are in an inactive state comprises:

maintaining a flag for each of said physical memory blocks indicating whether or not said physical memory block is active.

11. The method of claim 7, wherein indicating that some of said memory blocks are in an active state and some of said memory blocks are in an inactive state comprises:

maintaining a reference count for each of said physical memory blocks indicating the number of active references to each said physical memory block; and

identifying physical memory blocks having a corresponding reference count >

0 as active physical memory blocks.

12. The method of claim 7, further comprising mapping virtual block IDs to physical block IDs for some or all of said active physical memory blocks.

13. The method of claim 12, wherein said non-duplicating write capability is implemented using a block fetch by content (BFBC) instruction having block data as an input and a block address as an output,

wherein said block address is an address of an active physical memory block if said block data is a duplicate of data in a member of said set prior to executing said BFBC instruction, and

wherein said block address is an address of a newly-allocated physical memory block if said block data is not a duplicate of data in a member of said set prior to executing said BFBC instruction.

14. The method of claim 13, wherein said block address is either a physical block ID or a corresponding virtual block ID.

15. The method of claim 7, wherein said active physical memory blocks are organized as a plurality of directed acyclic graphs (DAGs).

16. The method of claim 15, wherein said plurality of DAGs is constrained to include no multi-DAG cyclic reference loop.

17. The method of claim 7, wherein a sequential read and compare capability for some or all contents of said physical memory provides content-addressability.

18. The method of claim 7 wherein a parallel read and compare capability for some or all contents of said physical memory provides content-addressability.

19. The method of claim 7, further comprising:

partitioning said physical memory into N banks, where N is an integer >

1; and

hashing block data to provide a hash value for said block data according to a hashing function having N possible outputs.

20. The method of claim 7, wherein the set of memory blocks that are compared includes all of said memory blocks that are indicated as being in an active state at the time of writing.