# US 12,001,237 B2 · Pattern-based cache block compression

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

- Number: US 12,001,237 B2
- Document ID: US12001237B2
- Status: Granted
- Kind: B2
- Application number: 17/029,158
- Filed: 2020-09-23
- Published: 2021-05-27
- Granted: 2024-06-04
- Earliest claimed: 2019-11-25
- Assignees: Advanced Micro Devices, Inc.
- Applicants: Advanced Micro Devices, Inc.
- Inventors: Matthew Tomei; Shomit N. Das; David A. Wood
- Web page: https://patentgrep.com/patent/US12001237B2

## CPC

- G06F 3/0608: {Saving storage space on storage systems}
- G06F 12/0888: using selective caching, e.g. bypass
- G06F 3/0655: {Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices}
- G06F 3/0676: {Magnetic disk device}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 12/0802: Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F 12/0886: Variable-length word access
- G06F 2212/1016: Performance improvement
- G06F 2212/1041: Resource optimization
- G06F 2212/401: Compressed data
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

Systems, methods, and devices for performing pattern-based cache block compression and decompression. An uncompressed cache block is input to the compressor. Byte values are identified within the uncompressed cache block. A cache block pattern is searched for in a set of cache block patterns based on the byte values. A compressed cache block is output based on the byte values and the cache block pattern. A compressed cache block is input to the decompressor. A cache block pattern is identified based on metadata of the cache block. The cache block pattern is applied to a byte dictionary of the cache block. An uncompressed cache block is output based on the cache block pattern and the byte dictionary. A subset of cache block patterns is determined from a training cache trace based on a set of compressed sizes and a target number of patterns for each size.

## Claims

### Claim 1

A method implemented in a compressor for performing pattern-based cache block compression, the method comprising:
inputting an uncompressed cache block;
identifying byte values within the uncompressed cache block;
searching for an index to a cache block pattern in a set of cache block patterns based on the byte values; and
outputting a compressed cache block based on the byte values and the cache block pattern.

### Claim 2 (depends on 1)

The method of claim 1, further comprising converting the byte values to symbols and expressing the uncompressed cache block in terms of the symbols, each symbol representing a particular cache block.

### Claim 3 (depends on 2)

The method of claim 2, further comprising searching for the index to the cache block pattern in the set of cache block patterns based on the byte values by searching the set of cache block patterns based on the symbols.

### Claim 4 (depends on 1)

The method of claim 1, wherein the compressed cache block comprises the byte values and the index to the set of cache block patterns.

### Claim 5 (depends on 1)

The method of claim 1, wherein the compressed cache block comprises a byte dictionary and metadata.

### Claim 6 (depends on 5)

The method of claim 5, wherein the metadata comprises the index to the cache block pattern.

### Claim 7 (depends on 5)

The method of claim 5, wherein the byte dictionary comprises each of the byte values, and for each of the byte values the byte dictionary includes only one copy.

### Claim 8

A method implemented in a decompressor for performing pattern-based cache block decompression, the method comprising:
inputting a compressed cache block;
identifying an index to a cache block pattern based on metadata of the compressed cache block;
applying the index to the cache block pattern to a byte dictionary of the compressed cache block; and
outputting an uncompressed cache block based on the cache block pattern and the byte dictionary.

### Claim 9 (depends on 8)

The method of claim 8, wherein the compressed cache block comprises byte values and the index to a set of cache block patterns.

### Claim 10 (depends on 8)

The method of claim 8, wherein the byte dictionary comprises byte values of the uncompressed cache block.

### Claim 11 (depends on 10)

The method of claim 10, wherein the byte dictionary comprises each of the byte values, and for each of the byte values, the byte dictionary includes only one copy.

### Claim 12 (depends on 8)

The method of claim 8, wherein the metadata comprises the index to the cache block pattern.

### Claim 13 (depends on 8)

The method of claim 8, wherein identifying the cache block pattern based on the metadata of the compressed cache block comprises searching for the cache block pattern in a set of cache block patterns based on the metadata.

### Claim 14 (depends on 8)

The method of claim 8, wherein the cache block pattern comprises at least one symbol corresponding to at least one byte of the byte dictionary.

### Claim 15 (depends on 8)

The method of claim 8, wherein the compressed cache block comprises byte values.

### Claim 16 (depends on 8)

The method of claim 8, wherein the byte dictionary of the compressed cache block comprises particular byte values of the uncompressed cache block.

### Claim 17

A method for generating hardware configured for pattern-based cache block compression, the method comprising:
inputting a cache trace;
determining a set of cache block patterns based on the cache trace;
determining a subset of cache block patterns from the set of cache block patterns, wherein the subset of cache block patterns is determined based on a set of compressed sizes and a target number of patterns for each size; and
outputting a description based on the determined subset of cache block patterns.

### Claim 18 (depends on 17)

The method of claim 17, wherein determining the subset of cache block patterns further comprises:
ranking the set of cache block patterns based on frequency of occurrence in the cache trace to generate a set of ranked cache block patterns.

### Claim 19 (depends on 18)

The method of claim 18, wherein determining the subset of cache block patterns further comprises:
reducing the set of ranked cache block patterns by removing patterns occurring in the cache trace below a threshold frequency to generate a set of thresholded cache block patterns; and
removing cache block patterns that are not maximally inclusive from the set of thresholded cache block patterns to generate a set of locally maximal cache block patterns.

### Claim 20 (depends on 19)

The method of claim 19, wherein determining the subset of cache block patterns further comprises:
combining relatively maximal patterns of the set of locally maximal cache block patterns to generate a set of absolutely maximal cache block patterns; and iteratively sorting subsets of the set of absolutely maximal cache block patterns based on which of the set of absolutely maximal cache block patterns describe more cache blocks to determine the subset of cache block patterns.