Hierarchical immutable content-addressable memory processor

• US 9,520,193 B2
• Filed: 12/12/2014
• Issued: 12/13/2016
• Est. Priority Date: 01/26/2007
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Cheriton, David R.
• Primary Examiner(s): ELMORE, STEPHEN C
• Application Number:
  US14/569,007
• Publication Number:
  US 20150194213A1
• Time in Patent Office: 732 Days
• Field of Search: 711/108, 711/154, 711/156, 365/49.1
• US Class Current: 1/1
• 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 comprising a plurality of physical memory blocks, wherein each physical memory block has a fixed storage capacity and each physical memory block is associated with an indication of whether it is active at a given point in time; and

a non-duplicating write capable memory controller to;

receive a data to be written to the physical memory;

compare the data to contents of all active physical memory blocks at a time of writing; and

avoid writing the data to a physical memory block if contents of one of the active physical memory blocks contain the data.

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 into the physical memory blocks.

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 to write to the physical memory blocks only by avoiding writing data to a physical memory block considered immutable.

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

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

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

7. A method of non-duplicating write capable computer system memory management comprising:

receiving a data to be written to a physical memory;

wherein the physical memory is content-addressable;

wherein the physical memory comprises a plurality of physical memory blocks;

wherein each physical memory block has a fixed storage capacity and each physical memory block is associated with an indication of whether it is active at a given point in time;

comparing the data to contents of all active physical memory blocks at a time of writing; and

avoiding writing the data to a physical memory block if contents of one of the active memory blocks contain the data.

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 avoiding writing comprises avoiding writing multi-block data considered immutable.

9. The method of claim 7, wherein once a physical 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 physical 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 a number of active references to a physical memory block; and

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

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

13. The method of claim 12, further comprising writing 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 physical memory block if the block data is a duplicate of data in a member of a 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 a set of physical memory blocks that are compared includes all of the physical memory blocks that are indicated as being in an active state at the time of writing.