Methods, Devices and Systems for Hybrid Data Compression and Decompression

• US 20180138921A1
• Filed: 05/20/2016
• Published: 05/17/2018
• Est. Priority Date: 05/21/2015
• Status: Active Grant

• Current Assignee: ZeroPoint Technologies AB
• Original Assignee: ZeroPoint Technologies AB
• Inventors: Arelakis, Angelos, Stenstrm, Per
• Granted Patent: US 10,476,520 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: H03M 5/00 Conversion of the form of the representation of individual digits
• CPC Class Codes: H03M 7/00 Conversion of a code where information is represented by a given sequence or number of digits to a code where the same , similar or subset of information is represented by a different sequence or number of digits
• 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/3071 Prediction
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence
• CPC Class Codes: H03M 7/48 alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present
• CPC Class Codes: H03M 7/6088 according to the data type

Abstract

Methods, devices and systems enhance compression and decompression of data blocks of data values by selecting the best suited compression method and device among two or a plurality of compression methods and devices, which are combined together and which said compression methods and devices compress effectively data values of particular data types; said best suited compression method and device is selected using as main selection criterion the dominating data type in a data block by predicting the data types within said data block.

Claims

1. A hybrid data compression device for compressing an uncompressed data block into a compressed data block, the uncompressed data block comprising one or a plurality of data values of one or a plurality of data types, the hybrid data compression device comprising:

a plurality of data compressors, each compressor being configured for a respective data compression scheme; and

a predictor mechanism configured for predicting data types of data values of the uncompressed data block and for selecting an estimated best suited data compressor among said plurality of data compressors using as main criterion a dominating data type among the predicted data types,

wherein the hybrid data compression device is configured to generate the compressed data block by causing the selected estimated best suited data compressor to compress the whole of the uncompressed data block.

2. The hybrid data compression device as defined in claim 1, wherein the hybrid data compression device is configured to generate metadata associated with the compressed data block and serving to identify the data compression scheme of the selected estimated best suited data compressor.

3. The hybrid data compression device as defined in claim 2, wherein the hybrid data compression device is configured to store the generated metadata in a data storage together with the compressed data block, the data storage being accessible to a data decompression device, or transmit the generated metadata over a link together with the compressed data block to a data decompression device.

5. The hybrid data compression device as defined in claim 1, wherein the plurality of data compressors includes:

a first data compressor configured for a first data compression scheme; and

a second data compressor configured for a second data compression scheme, different from the first data compression scheme,

wherein each of the first and second data compression schemes is a lossless compression scheme or a lossy compression scheme,

wherein the first data compression scheme is designed to exploit data locality between data values of a first data type, the data locality being temporal, spatial or a combination thereof, and

wherein the second data compression scheme is designed to exploit data locality between data values of a second data type, the data locality being temporal, spatial or a combination thereof.

8. The hybrid data compression device as defined in claim 1, wherein the data block is one of the following:

a cache line, cache set, cache block or cache sector for storage in a cache in a computer system,

a memory row, a memory page or memory sector for storage in a memory or transfer within a computer system,

a packet, flit, payload or header for transfer over a transmission link in a data communication system, and

wherein the data types of the data values are any of the following;

integers, pointers, floating-point numbers, characters, strings, boolean values, code instructions, or data types defined by a specific format or standard.

10. The hybrid data compression device as defined in claim 1, wherein the predictor mechanism is configured to:

divide the uncompressed data block into segments;

for all segments, inspect an inspection bit portion of each segment to classify the segment as a predicted data type among a plurality of candidate data types; and

compare occurrences of the predicted data types of all segments to determine the dominating data type of the uncompressed data block.

11. The hybrid data compression device as defined in claim 10, wherein the candidate data types are two or more of:

integers, pointers, floating-point numbers, characters, strings, boolean values, common data value block, data code instructions, or data types defined by a specific format or standard.

12. The hybrid data compression device as defined in claim 10, wherein the inspection bit portions are different for different candidate data types.

13. The hybrid data compression device as defined in claim 10, wherein:

one of the candidate data types is integer,

the size of the data block is m bytes,

the size of the segment is n bytes,

m/n is a multiple of 2,

the inspection bit portion is the p most significant bytes of the segment,

n/p is 2; and

wherein the predictor mechanism is configured to classify the segment as integer if the inspection bit portion is equal to any of a number of predefined p-byte values.

15. The hybrid data compression device as defined in claim 10, wherein:

one of the candidate data types is pointer,

the size of the data block is m bytes,

the size of the segment is n bytes,

m/n is a multiple of 2,

the inspection bit portion is the p most significant bytes of the segment,

n/p is 2, and

wherein the predictor mechanism is configured to classify the segment as pointer if the two most significant bytes but not the two least significant bytes of the inspection bit portion are equal to a predefined p/2-byte value.

17. The hybrid data compression device as defined in claim 10, wherein:

one of the candidate data types is floating-point numbers,

the size of the data block is m bytes,

the size of the segment is n bytes,

m/n is a multiple of 2, and

the inspection bit portion is the q most significant bits next to the most significant bit of the segment, and

wherein the predictor mechanism is configured to classify the segment as floating-point number by matching the inspection bit portion of the segment with inspection bit portions of neighboring segments in the data block, indicative of same or clustered floating-point exponents.

19. The hybrid data compression device as defined in claim 10, wherein:

one of the candidate data types is common data value,

the size of the data block is m bytes,

the size of the segment is n bytes,

m/n is a multiple of 2,

the inspection bit portion is the whole segment, and

wherein the predictor mechanism is configured to classify the segment as common data value when all its data values have a same common data value.

22. The hybrid data compression device as defined in claim 10, wherein the hybrid data compression device is configured to select, as the estimated best suited data compressor, a data compressor having common-block-value compression as its data compression scheme when all segments of the uncompressed data block have been classified as common data value.

23. The hybrid data compression device as defined in claim 10, wherein the predictor mechanism is configured, when two different predicted data types of the segments have the same occurrence, to prioritize one over the other when determining the dominating data type of the uncompressed data block.

25. The hybrid data compression device as defined in claim 10, wherein the predictor mechanism is configured, when there are no occurrences of predicted data types of the segments, either to select a default data compressor as the estimated best suited data compressor;

or to select no compression instead of an estimated best suited data compressor, hence refraining from compressing the uncompressed data block.

27. The hybrid data compression device as defined in claim 1, further configured to:

during a plurality of compression cycles, monitor the respective selected estimated best suited data compressors with respect to ideal selections of data compressors for the respective dominating data types;

detect that another data compressor would have been more efficient in terms of compressibility of a particular dominating data type;

for future compression cycles, change the best suited data compressor to said another data compressor for the particular dominating data type; and

wherein the ideal selections of data compressors for the respective dominating data types are provided by an oracle selector which compresses the uncompressed data blocks using the data compression schemes of all of the plurality of data compressors and chooses, as the respective ideal selection, the compressor having the data compression scheme which yields best compressibility of the respective uncompressed data block.

29. The hybrid data compression device as defined in claim 1, wherein the plurality of data compressors includes:

a first data compressor configured for a first data compression scheme being a common-block-value compression scheme; and

a second data compressor configured for a second data compression scheme, different from the first data compression scheme and being one of statistical (variable-length) encoding, dictionary-based compression, delta encoding, pattern-based compression, and significance-based compression,

wherein the hybrid data compression device is configured to generate the compressed data block by causing the first data compressor to compress the whole of the uncompressed data block into a compressed common-value data block if a common data value is found by the predictor mechanism to dominate the uncompressed data block, and otherwise generate the compressed data block by causing the second data compressor to compress the whole of the uncompressed data block according to the second data compression scheme.

30. The hybrid data compression device as defined in claim 29, wherein the compressed common-value data block contains a single bit.

31. The hybrid data compression device as defined in claim 29, wherein the predictor mechanism is integrated with the first data compressor.

32. The hybrid data compression device as defined in claim 29, wherein the predictor mechanism is configured to find that the common data value dominates the uncompressed data block when all its data values have the common data value.

94. A system comprising one or more memories, a data compression device according to claim 1 and a data decompression device according to claim 66.

95. The system as defined in claim 94, wherein the system is a computer system and wherein said one or more memories are from the group consisting of:

cache memories,

random access memories, and

secondary storages.

96. The system as defined in claim 94, wherein the system is a data communication system and wherein said one or more memories are data buffers.

4. (canceled)

6-7. -7. (canceled)

9. (canceled)

14. (canceled)

16. (canceled)

18. (canceled)

20-21. -21. (canceled)

24. (canceled)

26. (canceled)

28. (canceled)

33. (canceled)

34. A hybrid data compression method for compressing an uncompressed data block into a compressed data block, the uncompressed data block comprising one or a plurality of data values of one or a plurality of data types, the hybrid data compression method comprising:

predicting data types of data values of the uncompressed data block;

selecting an estimated best suited data compression scheme among a plurality of data compression schemes using as main criterion a dominating data type among the predicted data types, and

compressing the whole of the uncompressed data block by the selected estimated best suited data compression scheme to generate the compressed data block.

90. A computer program product comprising code instructions which, when loaded and executed by a processing device, cause performance of the method according to claim 34.

91. A device comprising logic circuitry configured to perform the method according to claim 34.

35-65. -65. (canceled)

66. A hybrid data decompression device for decompressing a compressed data block into a decompressed data block comprising one or a plurality of data values of one or a plurality of data types, the hybrid data decompression device comprising:

a plurality of data decompressors, each decompressor being configured for a respective data decompression scheme,

wherein the hybrid data decompression device is configured to generate the decompressed data block by causing a selected estimated best suited data decompressor among said plurality of data decompressors to decompress the whole of the compressed data block.

67. The hybrid data decompression device as defined in claim 66, wherein the hybrid data decompression device is configured to retrieve metadata associated with the compressed data block and select the estimated best suited data decompressor based on the metadata.

68. The hybrid data decompression device as defined in claim 67, wherein the hybrid data decompression device is configured to retrieve the metadata from a data storage together with the compressed data block, the data storage being accessible to a data compression device, or to receive the metadata over a link together with the compressed data block from a data compression device.

70. The hybrid data decompression device as defined in claim 67, wherein the plurality of data decompressors includes:

a first data decompressor configured for a first data decompression scheme; and

a second data decompressor configured for a second data decompression scheme, different from the first data decompression scheme, and

wherein each of the first and second data decompression schemes is a lossless decompression scheme or a lossy decompression scheme.

72. The hybrid data decompression device as defined in claim 70, wherein the data block is one of the following:

a cache line, cache set, cache block or cache sector for storage in a cache in a computer system,

a memory row, a memory page or memory sector for storage in a memory or transfer within a computer system,

a packet, flit, payload or header for transfer over a transmission link in a data communication system, and

wherein the data types of the data values are any of the following;

integers, pointers, floating-point numbers, characters, strings, boolean values, code instructions, or data types defined by a specific format or standard.

74. The hybrid data decompression device as defined in claim 66, wherein the plurality of data decompressors includes:

a first data decompressor configured for a first data decompression scheme being a common-block-value decompression scheme; and

a second data decompressor configured for a second data decompression scheme, different from the first data decompression scheme and being one of statistical (variable-length) decoding, dictionary-based decompression, delta decoding, pattern-based decompression, and significance-based decompression,

wherein the hybrid data decompression device is configured to check if the compressed data block is a compressed common-value data block and if so generate the decompressed data block by causing the first data decompressor to decompress the whole of the compressed data block into a decompressed common-value data block, and otherwise generate the decompressed data block by causing the second data decompressor to decompress the compressed data block according to the second data decompression scheme.

75. The hybrid data decompression device as defined in claim 74, wherein the compressed common-value data block contains a single bit.

76. The hybrid data decompression device as defined in claim 74, wherein the first data decompressor is configured to decompress the whole of the compressed data block into the decompressed common-value data block by filling the decompressed common-value data block with a common value.

69. (canceled)

71. (canceled)

73. (canceled)

77. (canceled)

78. A hybrid data decompression method for decompressing a compressed data block into a decompressed data block comprising one or a plurality of data values of one or a plurality of data types, the hybrid data decompression method comprising:

selecting an estimated best suited data decompression scheme among said plurality of data decompression schemes; and

decompressing the whole of the compressed data block by the selected estimated best suited data compression scheme to generate the decompressed data block.

92. A computer program product comprising code instructions which, when loaded and executed by a processing device, cause performance of the method according to claim 78.

93. A device comprising logic circuitry configured to perform the method according to claim 78.

79-89. -89. (canceled)