# US 9,520,193 B2 · Hierarchical immutable content-addressable memory processor

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,520,193 B2
- Document ID: US9520193B2
- Status: Granted
- Kind: B2
- Application number: 14/569,007
- Filed: 2014-12-12
- Published: 2015-07-09
- Granted: 2016-12-13
- Earliest claimed: 2007-01-26
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: David R. Cheriton
- Web page: https://patentgrep.com/patent/US9520193B2

## CPC

- G06F 3/064: {Management of blocks}
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/0631: {by allocating resources to storage systems}
- G06F 3/0673: {Single storage device}
- G06F 12/0223: {User address space allocation, e.g. contiguous or non contiguous base addressing}
- G06F 12/023: {Free address space management}
- G06F 12/0815: Cache consistency protocols
- G06F 12/10: Address translation
- G06F 12/109: for multiple virtual address spaces, e.g. segmentation (G06F12/1036 takes precedence)
- 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
- G11C 15/04: using semiconductor elements
- G06F 12/0261: {using reference counting}
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/621: Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11C: STATIC STORES (semiconductor memory devices H10B)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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

### Claim 6 (depends on 1)

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.

### Claim 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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 7)

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

### Claim 10 (depends on 7)

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.

### Claim 11 (depends on 7)

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.

### Claim 12 (depends on 11)

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

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 13)

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

### Claim 15 (depends on 11)

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

### Claim 16 (depends on 15)

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

### Claim 17 (depends on 7)

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

### Claim 18 (depends on 7)

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

### Claim 19 (depends on 7)

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.

### Claim 20 (depends on 7)

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.