Error-checking compressed streams in heterogeneous compression accelerators

Patent metadata

Field	Value
Publication number	US-9787332-B2
Application number	US-201514854647-A
Country	US
Kind code	B2
Filing date	Sep 15, 2015
Priority date	Sep 15, 2015
Publication date	Oct 10, 2017
Grant date	Oct 10, 2017

Abstract

A compression engine may be designed for more efficient error checking of a compressed stream, to include adaptation of a heterogeneous design that includes interleaved hardware and software stages of compression and decompression. An output of a string matcher may be reversed to generate a bit stream, which is then compared with an input stream to the compression engine as a first error check. A final compressed output of the compression engine may be partially decompressed to reverse entropy code encoding of an entropy code encoder. The partially decompressed output may be compared with an output of an entropy code generator to perform a second error check. Finding an error at the first error check greatly reduces the latency of generating a fault or exception, as does performing computing-intensive aspects of the compression and decompression with software instead of specialized hardware.

First claim

What is claimed is:

1. A processor comprising:
a compression engine comprising:
a hardware string matcher to string match various substrings of an input stream and to generate an intermediate token format of respective substring matches;
a processor core to execute first instructions as an entropy code generator to generate entropy codes from frequencies of tokens corresponding to respective substring matches; and
an entropy code encoder to encode, from the entropy codes, a final compressed output of the input stream; and

a decompression engine coupled to the compression engine, the decompression engine to generate a first output from the intermediate token format and a second output from a partially decompressed output of the final compressed output, wherein the first output and the second output being indicative of error checks of the input stream as the input stream is compressed.

2. The processor of claim 1 , wherein the hardware string matcher comprises an LZ77 compressor.

3. The processor of claim 1 , wherein the processor core is to execute second instructions to perform an inverse operation that generates a bit stream from the intermediate token format of respective substring matches, further comprising a comparator to compare the input stream with the bit stream and to generate a fault or exception, as the first output, in response to determination of an error in a match between the input stream and the bit stream.

4. The processor of claim 1 , wherein the decompression engine comprises:
a hardware decoder to partially decompress the final compressed output to reverse encoding of the entropy code encoder, to generate the partially decompressed output; and
a comparator to compare an output of the entropy code generator to the partially decompressed output and to generate a fault or exception, as the second output, in response to determination of an error in a match between the output of the entropy code generator to the partially decompressed output.

5. The processor of claim 1 , wherein the entropy code generator is a tree generator to generate a Huffman tree from the frequencies of the tokens.

6. The processor of claim 5 , wherein the entropy code encoder comprises a Huffman encoder to generate the final compressed output from the Huffman tree.

7. A device comprising:
a compressor to compress an input stream of data, the compressor comprising:
a hardware string matcher to string match various substrings of the input stream and to generate an intermediate token format of respective substring matches; and
a processor core to execute first instructions as an entropy code generator to generate entropy codes from frequencies of tokens corresponding to respective substring matches; and

a decompression engine coupled to the compressor, the decompression engine comprising:
the processor core to execute second instructions as an inverse string matcher to generate a bit stream from the intermediate token format of respective substring matches; and
a first comparator to compare the input stream with the bit stream and to generate a first fault or exception in response to determination of an error in a match between the input stream and the bit stream.

8. The device of claim 7 , wherein the hardware string matcher comprises an LZ77 compressor.

9. The device of claim 7 , wherein the compressor further comprises an entropy code encoder to encode, from the entropy codes, a final compressed output of the input stream.

10. The device of claim 9 , wherein the entropy code generator is a tree generator to generate a Huffman tree from the frequencies of the tokens, and wherein the entropy code encoder comprises a Huffman encoder to generate the final compressed output from the Huffman tree.

11. The device of claim 9 , wherein the decompression engine further comprises:
a decoder to partially decompress the final compressed output to reverse encoding of the entropy code encoder, to generate a partially decompressed output; and
a comparator to compare an output of the entropy code generator to the partially decompressed output and to generate a second fault or exception in response to determination of an error in a match between the output of the entropy code generator to the partially decompressed output.

12. The device of claim 11 , wherein the first fault or exception comprises a machine check architecture (MCA) fault distinguishable from the second fault or exception, and wherein the at least one processor is further to:
track, within a log, a first frequency of generation of the first fault or exception; and
track, within the log, a second frequency of generation of the second fault or exception.

13. An error-checking, data compression system, comprising:
a compression engine to compress an input stream of data, the compression engine comprising:
a hardware string matcher to string match various substrings of the input stream and to generate an intermediate token format of respective substring matches;
a processor core to execute first instructions as an entropy code generator to generate entropy codes from frequencies of tokens corresponding to respective substring matches; and
a hardware entropy code encoder to encode, from the entropy codes, a final compressed output of the input stream; and

a decompression engine coupled to the compression engine, the decompression engine to error check compression of the input stream, the decompression engine comprising:
the processor core to execute second instructions as an inverse string matcher to generate a bit stream from the intermediate token format of respective substring matches;
a first comparator to compare the input stream with the bit stream and to generate a first fault or exception in response to determination of an error in a match between the input stream and the bit stream;
a hardware decoder to partially decompress the final compressed output to reverse encoding of the entropy code encoder, to generate a partially decompressed output; and
a second comparator to compare an output of the entropy code generator to the partially decompressed output and to generate a second fault or exception in response to determination of an error in a match between the output of the entropy code generator to the partially decompressed output.

14. The system of claim 13 , wherein the first fault or exception comprises a machine check architecture (MCA) fault distinguishable from the second fault or exception, and wherein the at least one processor is further to:
track, within a log, a first frequency of generation of the first fault or exception;
track, within the log, a second frequency of generation of the second fault or exception; and
report the first frequency and the second frequency to a system administrator.

15. The system of claim 13 , wherein the hardware string matcher comprises an LZ77 compressor.

16. The system of claim 13 , wherein the entropy code generator is a tree generator to generate a Huffman tree from the frequencies of the tokens, and wherein the hardware entropy code encoder comprises a Huffman encoder to generate the final compressed output from the Huffman tree.

17. A method comprising:
compressing an input stream of data with a heterogeneous compressor, wherein the compressing comprises:
generating, with a hardware string matcher, an intermediate token format of substring matches within the input stream;
generating, with an entropy code generator, entropy codes from frequencies of tokens corresponding to respective substring matches; and
generating, with a hardware entropy co

Assignees

• Intel Corp

Inventors

• Guilford James D
• Gopal Vinodh
• Coquerel Laurent

Classifications

• H03M7/6041

  Compression optimized for errors · CPC title

• H03M13/6312 Primary

  Error control coding in combination with data compression · CPC title

• G06F11/1076

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H03M7/3086

  employing a sliding window, e.g. LZ77 · CPC title

• H03M7/4037 Primary

  Prefix coding · CPC title