Hierarchical immutable content-addressable memory processor

• US 7,650,460 B2
• Filed: 01/25/2008
• Issued: 01/19/2010
• Est. Priority Date: 01/26/2007
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Hicamp Systems Incorporated
• Inventors: Cheriton, David R.
• Primary Examiner(s): Elmore; Stephen C
• Application Number:
  US12/011,311
• Publication Number:
  US 20080183958A1
• Time in Patent Office: 725 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 an indication of which of said physical memory blocks are active physical memory blocks is provided; and

a memory controller providing a non-duplicating write capability, wherein data to be written to said physical memory is compared to contents of all active physical memory blocks at the time of writing to ensure that no two of said active physical memory blocks have the same 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 comprising:

providing a multi-block data convention specifying a unique representation for any data item requiring two or more of said physical memory blocks to store;

supporting said multi-block data convention when said data item is written to said physical memory, whereby said non-duplicating write capability can be extended to ensure that no duplicates of any instance of multi-block data exist 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 one or more processors in communication with said memory controller and 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. A method of computer system memory management comprising:

providing a content-addressable physical memory including two or more physical memory blocks, each of said physical memory blocks having a fixed storage capacity;

providing an indication of which of said physical memory blocks are active physical memory blocks; and

providing a non-duplicating write capability, wherein data to be written to said physical memory is compared to contents of all active physical memory blocks at the time of writing to ensure that no two of said active physical memory blocks have the same data after completion of the non-duplicating write.

7. The method of claim 6, further comprising:

providing a multi-block data convention specifying a unique representation for any data item requiring two or more of said physical memory blocks to store;

supporting said multi-block data convention when said data item is written to said physical memory, whereby said non-duplicating write capability can be extended to ensure that no duplicates of any instance of multi-block data exist in said active physical memory blocks.

8. The method of claim 6, wherein said providing an indication of which of said physical memory blocks are active physical memory blocks comprises:

regarding a physical memory block as active if it has been initialized or allocated according to said non-duplicating write capability.

9. The method of claim 6, wherein said providing an indication of which of said physical memory blocks are active physical memory blocks comprises:

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

10. The method of claim 6, wherein said providing an indication of which of said physical memory blocks are active physical memory blocks 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.

11. The method of claim 6, further comprising providing a mapping of virtual block IDs to physical block IDs for some or all of said active physical memory blocks.

12. The method of claim 11, wherein said non-duplicating write capability is implemented by providing a block fetch by content (BFBC) instruction having block data as an input and providing 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 one of said active physical memory blocks 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 one of said active physical memory blocks prior to executing said BFBC instruction.

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

14. The method of claim 6, wherein said active physical memory blocks is organized as a plurality of directed acyclic graphs (DAGs).

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

16. The method of claim 6, further comprising providing a sequential read and compare capability for some or all contents of said physical memory to provide content-addressability.

17. The method of claim 6, further comprising providing a parallel read and compare capability for some or all contents of said physical memory to provide content-addressability.

18. The method of claim 6, further comprising:

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

1;

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

providing a read and compare capability of said block data to contents of said bank of said physical memory corresponding to said hash value;

whereby content addressability is provided.