# US 2021/0173778 A1 · Memory architecture for efficient spatial-temporal data storage and access

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

- Number: US 2021/0173778 A1
- Document ID: US20210173778A1
- Status: Published application
- Kind: A1
- Application number: 16/709,217
- Filed: 2019-12-10
- Published: 2021-06-10
- Earliest claimed: 2019-12-10
- Assignees: Pony AI Inc.
- Applicants: Pony AI Inc.
- Inventors: Yubo Zhang; Pingfan Meng
- Web page: https://patentgrep.com/patent/US20210173778A1

## CPC

- G06F 12/0207: {with multidimensional access, e.g. row/column, matrix}
- G06F 12/0811: with multilevel cache hierarchies
- G06F 12/0223: {User address space allocation, e.g. contiguous or non contiguous base addressing}
- G06F 12/0292: {using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10)}
- G06F 12/0835: {for main memory peripheral accesses (e.g. I/O or DMA)}
- G06F 12/0851: {Cache with interleaved addressing}
- G06F 12/0862: with prefetch
- G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
- G06F 12/1045: associated with a data cache
- G06T 1/60: Memory management
- G06F 2212/1024: Latency reduction
- G06F 2212/454: Vector or matrix data
- G06F 2212/455: Image or video data
- G06F 2212/465: Structured object, e.g. database record
- G06F 2212/502: using adaptive policy
- G06F 2212/6024: History based prefetching
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

Described herein are systems, methods, and non-transitory computer readable media for memory address encoding of multi-dimensional data in a manner that optimizes the storage and access of such data in linear data storage. The multi-dimensional data may be spatial-temporal data that includes two or more spatial dimensions and a time dimension. An improved memory architecture is provided that includes an address encoder that takes a multi-dimensional coordinate as input and produces a linear physical memory address. The address encoder encodes the multi-dimensional data such that two multi-dimensional coordinates close to one another in multi-dimensional space are likely to be stored in close proximity to one another in linear data storage. In this manner, the number of main memory accesses, and thus, overall memory access latency is reduced, particularly in connection with real-world applications in which the respective probabilities of moving along any given dimension are very close.

## Claims

### Claim 1

A computer-implemented method for memory address encoding of multi-dimensional data that includes first multi-dimensional data and second multi-dimensional data, the method comprising:
applying an address encoding to the first multi-dimensional data to obtain a first memory address for the first multi-dimensional data;
applying the address encoding to the second multi-dimensional data to obtain a second memory address for the second multi-dimensional data, wherein the second multi-dimensional data is obtained from the first multi-dimensional data by incrementing by one unit respective data of the first multi-dimensional data that corresponds to a particular dimension;
storing the first multi-dimensional data in a memory at the first memory address; and
storing the second multi-dimensional data in the memory at the second memory address,
wherein the address encoding ensures that a linear difference between the second memory address and the first memory address is bounded independently of a size of any dimension of the multi-dimensional data.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the first multi-dimensional data comprises first data corresponding to a first dimension and second data corresponding to a second dimension, and wherein applying the address encoding to the first multi-dimensional data to obtain the first memory address comprises:
identifying a first bit representation of the first data;
identifying a second bit representation of the second data; and
interleaving the first bit representation and the second bit representation to obtain the first memory address.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein interleaving the first bit representation and the second bit representation comprises:
grouping together a first set of bits including a least significant bit of the first bit representation and a least significant bit of the second bit representation; and
appending one or more additional sets of bits to the first set of bits in successively more significant bit positions to obtain the first memory address, wherein each additional set of bits includes a respective bit at a same bit position from each of the first data and the second data.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein the memory is a main memory, the method further comprising:
receiving a first memory access request to access the first multi-dimensional data;
applying the address encoding to the first multi-dimensional data to obtain the first memory address;
determining, based at least in part on at least a portion of the first memory address, that the first multi-dimensional data is not stored in a cache memory;
retrieving, from the main memory, a data block comprising the first multi-dimensional data; and
storing the data block in the cache memory.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4, further comprising:
receiving a second memory access request to access the second multi-dimensional data;
applying the address encoding to the second multi-dimensional data to obtain the second memory address;
determining, based at least in part on at least a portion of the second memory address, that the second multi-dimensional data is stored in the cache memory; and
retrieving the second multi-dimensional data from the cache memory,
wherein the data block previously stored in the cache memory further comprises the second multi-dimensional data.

### Claim 6 (depends on 4)

The computer-implemented method of claim 4, wherein the data block corresponds in size to a smallest cache line of the cache memory, and wherein, based at least in part on the address encoding, a probability that the data block also includes the second multi-dimensional data is greater than fifty percent.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein the address encoding ensures that the linear difference between the first memory address and the second memory address is within 2(4k-1) with a probability of 2(−k) for k≥1.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1, wherein the first multi-dimensional data and the second multi-dimensional data represent spatial-temporal data.

### Claim 9

A system for memory address encoding of multi-dimensional data that includes first multi-dimensional data and second multi-dimensional data, the system comprising:
at least one processor; and
at least one memory storing computer-executable instructions, wherein the at least one processor is configured to access the at least one processor and execute the computer-executable instructions to:
apply an address encoding to the first multi-dimensional data to obtain a first memory address for the first multi-dimensional data;
apply the address encoding to the second multi-dimensional data to obtain a second memory address for the second multi-dimensional data, wherein the second multi-dimensional data is obtained from the first multi-dimensional data by incrementing by one unit respective data of the first multi-dimensional data that corresponds to a particular dimension;
store the first multi-dimensional data in a memory at the first memory address; and
store the second multi-dimensional data in the memory at the second memory address,
wherein the address encoding ensures that a linear difference between the second memory address and the first memory address is bounded independently of a size of any dimension of the multi-dimensional data.

### Claim 10 (depends on 9)

The system of claim 9, wherein the first multi-dimensional data comprises first data corresponding to a first dimension and second data corresponding to a second dimension, and wherein the at least one processor is configured to apply the address encoding to the first multi-dimensional data to obtain the first memory address by executing the computer-executable instructions to:
identify a first bit representation of the first data;
identify a second bit representation of the second data; and
interleave the first bit representation and the second bit representation to obtain the first memory address.

### Claim 11 (depends on 10)

The system of claim 10, wherein at least one processor is configured to interleave the first bit representation and the second bit representation by executing the computer-executable instructions to:
group together a first set of bits including a least significant bit of the first bit representation and a least significant bit of the second bit representation; and
append one or more additional sets of bits to the first set of bits in successively more significant bit positions to obtain the first memory address, wherein each additional set of bits includes a respective bit at a same bit position from each of the first data and the second data.

### Claim 12 (depends on 9)

The system of claim 9, wherein the memory is a main memory, and wherein the at least one processor is further configured to execute the computer-executable instructions to:
receive a first memory access request to access the first multi-dimensional data;
apply the address encoding to the first multi-dimensional data to obtain the first memory address;
determine, based at least in part on at least a portion of the first memory address, that the first multi-dimensional data is not stored in a cache memory;
retrieve, from the main memory, a data block comprising the first multi-dimensional data; and
store the data block in the cache memory.

### Claim 13 (depends on 12)

The system of claim 12, wherein the at least one processor is further configured to execute the computer-executable instructions to:
receive a second memory access request to access the second multi-dimensional data;
apply the address encoding to the second multi-dimensional data to obtain the second memory address;
determine, based at least in part on at least a portion of the second memory address, that the second multi-dimensional data is stored in the cache memory; and
retrieve the second multi-dimensional data from the cache memory,
wherein the data block previously stored in the cache memory further comprises the second multi-dimensional data.

### Claim 14 (depends on 12)

The system of claim 12, wherein the data block corresponds in size to a smallest cache line of the cache memory, and wherein, based at least in part on the address encoding, a probability that the data block also includes the second multi-dimensional data is greater than fifty percent.

### Claim 15 (depends on 9)

The system of claim 9, wherein the address encoding ensures that the linear difference between the first memory address and the second memory address is within 2(4k-1) with a probability of 2(−k) for k≥1.

### Claim 16

A computer program product for memory address encoding of multi-dimensional data that includes first multi-dimensional data and second multi-dimensional data, the computer program product comprising a non-transitory computer-readable medium readable by a processing circuit, the non-transitory computer-readable medium storing instructions executable by the processing circuit to cause a method to be performed, the method comprising:
applying an address encoding to the first multi-dimensional data to obtain a first memory address for the first multi-dimensional data;
applying the address encoding to the second multi-dimensional data to obtain a second memory address for the second multi-dimensional data, wherein the second multi-dimensional data is obtained from the first multi-dimensional data by incrementing by one unit respective data of the first multi-dimensional data that corresponds to a particular dimension;
storing the first multi-dimensional data in a memory at the first memory address; and
storing the second multi-dimensional data in the memory at the second memory address,
wherein the address encoding ensures that a linear difference between the second memory address and the first memory address is bounded independently of a size of any dimension of the multi-dimensional data.

### Claim 17 (depends on 16)

The computer program product of claim 16, wherein the first multi-dimensional data comprises first data corresponding to a first dimension and second data corresponding to a second dimension, and wherein applying the address encoding to the first multi-dimensional data to obtain the first memory address comprises:
identifying a first bit representation of the first data;
identifying a second bit representation of the second data; and
interleaving the first bit representation and the second bit representation to obtain the first memory address.

### Claim 18 (depends on 17)

The computer program product of claim 17, wherein interleaving the first bit representation and the second bit representation comprises:
grouping together a first set of bits including a least significant bit of the first bit representation and a least significant bit of the second bit representation; and
appending one or more additional sets of bits to the first set of bits in successively more significant bit positions to obtain the first memory address, wherein each additional set of bits includes a respective bit at a same bit position from each of the first data and the second data.

### Claim 19 (depends on 16)

The computer program product of claim 16, wherein the memory is a main memory, the method further comprising:
receiving a first memory access request to access the first multi-dimensional data;
applying the address encoding to the first multi-dimensional data to obtain the first memory address;
determining, based at least in part on at least a portion of the first memory address, that the first multi-dimensional data is not stored in a cache memory;
retrieving, from the main memory, a data block comprising the first multi-dimensional data; and
storing the data block in the cache memory.

### Claim 20 (depends on 19)

The computer program product of claim 19, the method further comprising:
receiving a second memory access request to access the second multi-dimensional data;
applying the address encoding to the second multi-dimensional data to obtain the second memory address;
determining, based at least in part on at least a portion of the second memory address, that the second multi-dimensional data is stored in the cache memory; and
retrieving the second multi-dimensional data from the cache memory,
wherein the data block previously stored in the cache memory further comprises the second multi-dimensional data.
