Method and apparatus for accelerating canonical huffman encoding

Patent metadata

Field	Value
Publication number	US-10135463-B1
Application number	US-201715721343-A
Country	US
Kind code	B1
Filing date	Sep 29, 2017
Priority date	Sep 29, 2017
Publication date	Nov 20, 2018
Grant date	Nov 20, 2018

Abstract

In one embodiment, an apparatus comprises a memory; and a compression engine comprising circuitry, the compression engine to assign weights to a plurality of first symbols of a data set, a weight representing a frequency of a corresponding first symbol in the data set; perform a partial sort of the first symbols based on the assigned weights; generate at least a portion of a Huffman tree based on the partial sort; and create a plurality of Huffman codes for the plurality of first symbols based on the Huffman tree.

First claim

What is claimed is:

1. An apparatus comprising:
a memory; and
a compression engine comprising circuitry, the compression engine to:
assign weights to a plurality of first symbols of a data set, a weight representing a frequency of a corresponding first symbol in the data set;
perform a partial sort of the first symbols based on the assigned weights;
generate at least a portion of a Huffman tree based on the partial sort, wherein the generation of at least a portion of the Huffman tree is performed concurrently with further sorting of at least some of the first symbols; and
create a plurality of Huffman codes for the plurality of first symbols based on the Huffman tree.

2. The apparatus of claim 1 , wherein the compression engine is to store the assigned weights among a plurality of banks of the memory.

3. The apparatus of claim 1 , wherein performing the partial sort comprises performing an intra-bank weight sort operation wherein the assigned weights of a bank of a plurality of banks are sorted within the bank.

4. The apparatus of claim 1 , wherein the compression engine comprises an address generator to generate bank addresses to be supplied to each bank of a plurality of banks during an intra-bank weight sort operation.

5. The apparatus of claim 1 , wherein the compression engine comprises an address generator to generate bank addresses to be supplied to each bank of a plurality of banks during an intra-bank weight sort operation and wherein the bank addresses are generated such that an entry of a bank is not accessed in two consecutive cycles.

6. The apparatus of claim 1 , wherein the compression engine is to perform an inter-bank weight sort operation wherein the inter-bank weight sort operation is to output a lowest weighted first symbol based on a comparison of a second plurality of first symbols, the second plurality of first symbols including a first symbol from each bank of a plurality of banks.

7. The apparatus of claim 1 , wherein the compression engine comprises a plurality of comparators to perform an intra-bank weight sort for a plurality of banks of the memory and wherein at least a subset of the plurality of comparators are reused to perform an inter-bank weight sort for the plurality of banks.

8. The apparatus of claim 1 , wherein the compression engine is to store the weights assigned to the first symbols in the memory and weights assigned to a plurality of second symbols of the Huffman tree in a second memory.

9. The apparatus of claim 1 , wherein the compression engine is to:
store the weights assigned to the first symbols in the memory;
store weights assigned to a plurality of second symbols of the Huffman tree in a second memory;
calculate a depth of a first symbol based on an access to the second memory; and
overwrite an assigned weight in the memory with the calculated depth.

10. The apparatus of claim 1 , wherein the compression engine is to:
identify two lowest weighted first symbols and two lowest weighted second symbols;
select two lowest weighted symbols from the identified two lowest weighted first symbols and two lowest weighted second symbols; and
form a second symbol of the Huffman tree based on the selected two lowest weighted symbols.

11. The apparatus of claim 1 , wherein the compression engine is to:
sort zero-weighted symbols together in a bank of a plurality of banks; and
during the creation of the plurality of Huffman codes, stop processing symbols of the bank when a zero-weighted symbol is encountered.

12. The apparatus of claim 1 , further comprising a battery communicatively coupled to a processor, a display communicatively coupled to the processor, or a network interface communicatively coupled to the processor.

13. A method comprising:
assigning weights to a plurality of first symbols of a data set, a weight representing a frequency of a corresponding first symbol in the data set;
performing a partial sort of the first symbols based on the assigned weights;
generating, by a compression engine comprising circuitry, at least a portion of a Huffman tree based on the partial sort, wherein the generation of at least a portion of the Huffman tree is performed concurrently with further sorting of at least some of the first symbols; and
creating a plurality of Huffman codes for the plurality of first symbols based on the Huffman tree.

14. The method of claim 13 , wherein performing the partial sort comprises performing an intra-bank weight sort operation wherein the assigned weights of a bank of a plurality of banks are sorted within the bank.

15. The method of claim 13 , further comprising generating, by an address generator, bank addresses to be supplied to each bank of a plurality of banks during an intra-bank weight sort operation.

16. The method of claim 13 , further comprising performing an inter-bank weight sort operation wherein the inter-bank weight sort operation is to output a lowest weighted first symbol based on a comparison of a second plurality of first symbols, the second plurality of first symbols including a first symbol from each bank of a plurality of banks.

17. At least one non-transitory machine readable storage medium having instructions stored thereon, the instructions when executed by a machine to cause the machine to:
assign weights to a plurality of first symbols of a data set, a weight representing a frequency of a corresponding first symbol in the data set;
perform a partial sort of the first symbols based on the assigned weights;
generate at least a portion of a Huffman tree based on the partial sort, wherein the generation of at least a portion of the Huffman tree is performed concurrently with further sorting of at least some of the first symbols; and
create a plurality of Huffman codes for the plurality of first symbols based on the Huffman tree.

18. The at least one medium of claim 17 , wherein performing the partial sort comprises performing an intra-bank weight sort operation wherein the assigned weights of a bank of a plurality of banks are sorted within the bank.

19. The at least one medium of claim 17 , the instructions when executed to cause the machine to generate, by an address generator, bank addresses to be supplied to each bank of a plurality of banks during an intra-bank weight sort operation.

20. The at least one medium of claim 17 , the instructions when executed to cause the machine to perform an inter-bank weight sort operation wherein the inter-bank weight sort operation is to output a lowest weighted first symbol based on a comparison of a second plurality of first symbols, the second plurality of first symbols including a first symbol from each bank of a plurality of banks.

21. A system comprising:
a memory;
a processor to request compression of a data set; and
a compression engine comprising circuitry, the compression engine to:
assign weights to a plurality of first symbols of the data set, a weight representing a frequency of a corresponding first symbol in the data set;
perform a partial sort of the first symbols based on the assigned weights;
generate at least a portion of a Huffman tree based on the partial sort, wherein the generation of at least a portion of the Huffman tree is performed concurrently with further sorting of at least some of the first symbols; and
create a plurality of Huffman codes for the plurality of first symbols based on the Huffman tree.

22. The system of claim 21 , the compression engine further to compress the data s

Assignees

• Intel Corp

Inventors

• Satpathy Sudhir K
• Guilford James D
• Gopal Vinodh
• Yap Kirk S

Classifications

• H03M7/40

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title

• H03M7/6017 Primary

  Methods or arrangements to increase the throughput · CPC title

• H03M7/6023

  Parallelization · CPC title

• H03M7/4043

  Adaptive prefix coding · CPC title

• H03M7/3084

  using adaptive string matching, e.g. the Lempel-Ziv method · CPC title