Method and apparatus for accelerating canonical huffman encoding

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 set based on the plurality of Huffman codes.

23. The system of claim 22 , further comprising a network interface to transmit the compressed data set onto a network.