# US 10,769,065 B2 · Systems and methods for performing memory compression

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

- Number: US 10,769,065 B2
- Document ID: US10769065B2
- Status: Granted
- Kind: B2
- Application number: 16/436,635
- Filed: 2019-06-10
- Published: 2019-09-26
- Granted: 2020-09-08
- Earliest claimed: 2017-07-28
- Assignees: Apple Inc.
- Applicants: Apple Inc.
- Inventors: Ali Sazegari; Charles E. Tucker; Jeffry E. Gonion; Gerard R. Williams, III; Chris Cheng-Chieh Lee
- Web page: https://patentgrep.com/patent/US10769065B2

## CPC

- G06F 12/08: in hierarchically structured memory systems, e.g. virtual memory systems
- H03M 7/42: using table look-up for the coding or decoding process, e.g. using read-only memory {(H03M7/4006 takes precedence)}
- G06F 12/0886: Variable-length word access
- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M 7/3088: {employing the use of a dictionary, e.g. LZ78}
- H03M 7/6023: {Parallelization}
- G06F 12/00: Accessing, addressing or allocating within memory systems or architectures (digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06)
- G06F 13/00: Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units (interface circuits for specific input/output devices G06F3/00 {; multiprogram control therefor G06F9/46}; multiprocessor systems G06F15/16 )
- G06F 2212/1016: Performance improvement
- G06F 2212/401: Compressed data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

Systems, apparatuses, and methods for efficiently moving data for storage and processing a compression unit within a processor includes multiple hardware lanes, selects two or more input words to compress, and for assigns them to two or more of the multiple hardware lanes. As each assigned input word is processed, each word is compared to an entry of a plurality of entries of a table. If it is determined that each of the assigned input words indexes the same entry of the table, the hardware lane with the oldest input word generates a single read request for the table entry and the hardware lane with the youngest input word generates a single write request for updating the table entry upon completing compression. Each hardware lane generates a compressed packet based on its assigned input word.

## Claims

### Claim 1

An apparatus comprising:
a table comprising a plurality of entries; and
compression circuitry comprising a plurality of hardware lanes, wherein in response to receiving an indication of a compression instruction, the compression circuitry is configured to:
assign a first group of two or more input words to the plurality of hardware lanes;
responsive to determining at least a first input word and a second input word of the first group of two or more input words correspond to a same entry of the table, generate for the first input word and the second input word:
a single read request for the table; and
a single write request for the table; and
generate a compression packet for each of the first input word and the second input word.

### Claim 2 (depends on 1)

The apparatus as recited in claim 1, wherein the compression circuitry is further configured generate an index for each word assigned to a lane of the plurality of lanes.

### Claim 3 (depends on 2)

The apparatus as recited in claim 2, wherein to determine the first input word and the second input word of the first group of the two or more input words correspond to the same entry of the table, the circuitry is configured determine the first input word and the second input word have a same index.

### Claim 4 (depends on 1)

The apparatus as recited in claim 1, wherein the compression circuitry is configured to generate an index corresponding to a given input word based at least in part on a hash of the given input word.

### Claim 5 (depends on 1)

The apparatus as recited in claim 1, wherein the compression circuitry is configured to determine whether to update the table with any of the input words of the first group prior to determining dependencies between input words of the first group.

### Claim 6 (depends on 5)

The apparatus as recited in claim 5, wherein the compression circuitry is configured to:
assign a second group of input words from the plurality of input words to the plurality of hardware lanes, wherein the second group is different from the first group;
wherein for each table entry to be accessed, the compression circuitry is further configured to:
determine a youngest input word of the first group; and
forward the youngest word to the second group prior to determining dependencies between input words of the first group.

### Claim 7 (depends on 6)

The apparatus as recited in claim 6, wherein for each table entry to be accessed, the compression circuitry is further configured to:
determine an oldest input word of the first group; and
send a read request for an input word in the table from a lane of the plurality of hardware lanes assigned to the oldest input word.

### Claim 8

A method comprising:
storing input words in a table comprising a plurality of entries; and
in response to receiving an indication of a compression instruction:
assigning a first group of two or more input words to a plurality of hardware lanes;
responsive to determining at least a first input word and a second input word of the first group of two or more input words correspond to a same entry of the table, generating for the first input word and the second input word:
a single read request for the table; and
a single write request for the table; and
generating a compression packet for each of the first input word and the second input word.

### Claim 9 (depends on 8)

The method as recited in claim 8, further comprising generating an index for each word assigned to a lane of the plurality of lanes.

### Claim 10 (depends on 9)

The method as recited in claim 9, wherein to determine the first input word and the second input word of the first group of the two or more input words correspond to the same entry of the table, the method comprises determining the first input word and the second input word have a same index.

### Claim 11 (depends on 8)

The method as recited in claim 8, further comprising generating an index corresponding to a given input word based at least in part on a hash of the given input word.

### Claim 12 (depends on 8)

The method as recited in claim 8, further comprising determining whether to update the table with any of the input words of the first group prior to determining dependencies between input words of the first group.

### Claim 13 (depends on 12)

The method as recited in claim 12, further comprising:
assigning a second group of input words from the plurality of input words to the plurality of hardware lanes, wherein the second group is different from the first group; and
for each table entry to be accessed:
determining a youngest input word of the first group; and
forwarding the youngest word to the second group prior to determining dependencies between input words of the first group.

### Claim 14 (depends on 13)

The method as recited in claim 13, wherein for each table entry to be accessed, the further comprising:
determining an oldest input word of the first group; and
sending a read request for an input word in the table from a lane of the plurality of hardware lanes assigned to the oldest input word.

### Claim 15

A system comprising:
a memory;
a cache coupled to the memory; and
a processor coupled to the memory and the cache, wherein the processor is configured to:
assign a first group of two or more input words to a plurality of hardware lanes;
responsive to determining at least a first input word and a second input word of the first group of two or more input words correspond to a same entry of a table, generate for the first input word and the second input word:
a single read request for the table; and
a single write request for the table; and
generate a compression packet for each of the first input word and the second input word.

### Claim 16 (depends on 15)

The system as recited in claim 15, wherein the processor is further configured generate an index for each word assigned to a lane of the plurality of lanes.

### Claim 17 (depends on 16)

The system as recited in claim 16, wherein to determine the first input word and the second input word of the first group of the two or more input words correspond to the same entry of the table, the processor is configured to determine the first input word and the second input word have a same index.

### Claim 18 (depends on 15)

The system as recited in claim 15, wherein the processor is configured to generate an index corresponding to a given input word based at least in part on a hash of the given input word.

### Claim 19 (depends on 15)

The system as recited in claim 15, wherein the processor is configured to determine whether to update the table with any of the input words of the first group prior to determining dependencies between input words of the first group.

### Claim 20 (depends on 19)

The system as recited in claim 19, wherein the processor is configured to:
assign a second group of input words from the plurality of input words to the first plurality of hardware lanes, wherein the second group is different from the first group;
wherein for each table entry to be accessed, the processor is further configured to:
determine a youngest input word of the first group; and
forward the youngest word to the second group prior to determining dependencies between input words of the first group.