BYTE SELECT CACHE COMPRESSION

• US 20200133866A1
• Filed: 10/31/2018
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Das, Shomit N., Tomei, Matthew, Wood, David A.
• Granted Patent: US 10,860,489 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: 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
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/6064 Selection of Compressor

Abstract

The disclosure herein provides techniques for designing cache compression algorithms that control how data in caches are compressed. The techniques generate a custom “byte select algorithm” by applying repeated transforms applied to an initial compression algorithm until a set of suitability criteria is met. The suitability criteria include that the “cost” is below a threshold and that a metadata constraint is met. The “cost” is the number of blocks that can be compressed by an algorithm as compared with the “ideal” algorithm. The metadata constraint is the number of bits required for metadata.

Claims

1. A method for designing a data compression unit, the method comprising:

identifying an initial compression algorithm for evaluation;

performing a transform on the initial compression algorithm to generate a modified compression algorithm;

evaluating the modified compression algorithm for suitability based on a set of suitability criteria; and

repeating the performing and evaluating steps to adjust the modified compression algorithm until the modified compression algorithm is deemed to meet suitability criteria,

wherein the compression algorithm and the modified compression algorithm comprise byte-select algorithms.

2. The method of claim 1, wherein the byte select algorithms include metadata that determines how decompression occurs by identifying where bytes of a dictionary in a compressed block are to be located in an uncompressed output block.

3. The method of claim 1, wherein the transform comprises one of edge removal and edge coalescence.

4. The method of claim 3, wherein edge removal reduces the possibilities available for storage by metadata of the byte-select algorithms by removing the possibility that the metadata is able to indicate that a specific byte in an input block has an identical value to a specific byte in an output block.

5. The method of claim 3, wherein edge coalescence reduces the possibilities available for storage by metadata of the byte-select algorithms by removing the possibility that the metadata is able to independently indicate that a first byte of an input block has the same value as a first byte of an output block and that a second byte of the input block has the same value as a second byte of the output block.

6. The method of claim 1, wherein the suitability criteria comprises:

the modified compression algorithm having a cost that is lower than a threshold.

7. The method of claim 6, wherein the cost indicates a number of additional data blocks that cannot be compressed as compared with the initial compression algorithm.

8. The method of claim 1, wherein the suitability criteria comprises:

the modified compression algorithm meeting a metadata constraint.

9. The method of claim 1, wherein repeating the performing and evaluating steps comprises performing a depth-first search through a graph of graphs representing different compression algorithms.

10. A method for operating a memory unit implementing compression, the method comprising:

receiving a request to store a block of data in the cache;

compressing the block of data according to a byte-select algorithm to form a compressed block;

storing the compressed block in the cache;

receiving a request to read the block of data from the cache; and

decompressing the compressed block according to the byte-select algorithm.

11. The method of claim 10, wherein the byte select algorithms includes metadata that determines how decompression occurs by identifying where bytes of a dictionary in a compressed block are to be located in an uncompressed output block.

12. The method of claim 10, wherein the byte-select algorithm is tailored to a set of data associated with a type of the cache.

13. The method of claim 10, wherein:

the byte-select algorithm comprises a compression algorithm that differs from an ideal byte-select algorithm by one or more transforms.

14. The method of claim 13, wherein the one or more transforms comprises:

one or more edge removal transforms; and

one or more edge coalescence transforms.

15. The method of claim 14, wherein edge removal reduces the possibilities available for storage by metadata of the byte-select algorithms by removing the possibility that the metadata is able to indicate that a specific byte in an input block has an identical value to a specific byte in an output block.

16. The method of claim 14, wherein edge coalescence reduces the possibilities available for storage by metadata of the byte-select algorithms by removing the possibility that the metadata is able to independently indicate that a first byte of an input block has the same value as a first byte of an output block and that a second byte of the input block has the same value as a second byte of the output block.

17. A design tool for designing a memory unit implementing compression, the design tool comprising:

a memory storing instructions; and

a processor configured to execute the instructions to;

identify an initial compression algorithm for evaluation;

perform a transform on the initial compression algorithm to generate a modified compression algorithm;

evaluate the modified compression algorithm for suitability based on a set of suitability criteria; and

repeat the performing and evaluating steps to adjust the modified compression algorithm until the modified compression algorithm is deemed to meet suitability criteria,

wherein the compression algorithm and the modified compression algorithm comprise byte-select algorithms.

18. The design tool of claim 17, wherein the byte select algorithms include metadata that determines how decompression occurs by identifying where bytes of a dictionary in a compressed block are to be located in an uncompressed output block.

19. The design tool of claim 17, wherein the transform comprises one of edge removal and edge coalescence.

20. The design tool of claim 19, wherein:

edge removal reduces the possibilities available for storage by metadata of the byte-select algorithms by removing the possibility that the matadata is able to indicate that a specific byte in an input block has an identical value to a specific byte in an output block; and

edge coalescence reduces the possibilities available for storage by metadata of the byte-select algorithms by removing the possibility that the metadata is able to independently indicate that a first byte of an input block has the same value as a first byte of an output block and that a second byte of the input block has the same value as a second byte of the output block.