Hierarchical immutable content-addressable memory processor

• US 8,938,580 B2
• Filed: 10/24/2013
• Issued: 01/20/2015
• 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 C
• Application Number:
  US14/062,301
• Publication Number:
  US 20140149656A1
• Time in Patent Office: 453 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 physical memory including a plurality of physical memory blocks, wherein once any memory block is initialized with specified data, its contents are considered immutable; and

a memory controller configured to;

receive a data to be written to the physical memory; and

avoid writing the data to a memory block with contents considered immutable.

2. The system of claim 1, wherein the memory controller provides a multi-block data convention specifying a representation for data items requiring two or more of the physical memory blocks to store wherein the memory controller avoids writing multi-block data considered immutable.

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

4. The system of claim 1, further comprising a processor in communication with the memory controller wherein the processor is capable of writing to the physical memory only by avoiding writing data to a memory block considered immutable.

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

6. The system of claim 1, wherein the memory controller is further configured to:

compare the data to be written with contents of the memory block using a block fetch by content (BFBC) instruction.

7. A method of computer system memory management comprising:

in a physical memory including a plurality of physical memory blocks, initializing any memory block with specified data so that its contents are considered immutable;

receiving a data to be written to the physical memory; and

avoiding writing the data to a memory block with contents considered immutable.

8. The method of claim 7, further comprising:

specifying a representation for data items requiring two or more of the physical memory blocks to store according to a multi-block data convention wherein the memory controller avoids writing multi-block data considered immutable.

9. The method of claim 7, wherein once any memory block is allocated, its contents are considered immutable.

10. The method of claim 7, further comprising maintaining a flag for each of the plurality of physical memory blocks, indicating whether or not contents of a memory block are considered immutable.

11. The method of claim 7, further comprising:

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

identifying memory blocks having a corresponding reference count greater than zero as active memory blocks.

12. The method of claim 11, further comprising mapping virtual block IDs to physical block IDs for an active memory block.

13. The method of claim 12, wherein the memory controller writes data using a block fetch by content (BFBC) instruction having block data as an input and a block address as an output,

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

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

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

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

16. The method of claim 15, wherein the 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 the physical memory provides addressability.

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

19. The method of claim 7, further comprising:

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

1; and

hashing block data to provide a hash value for the 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 the memory blocks that are indicated as being in an active state at the time of writing.