Methods and apparatus to parallelize data decompression
Methods and apparatus to parallelize data decompression are disclosed. An example method selecting initial starting positions in a compressed data bitstream; adjusting a first one of the initial starting positions to determine a first adjusted starting position by decoding the bitstream starting at a training position in the bitstream, the decoding including traversing the bitstream from the training position as though first data located at the training position is a valid token; outputting first decoded data generated by decoding a first segment of the bitstream starting from the first adjusted starting position; and merging the first decoded data with second decoded data generated by decoding a second segment of the bitstream, the decoding of the second segment starting from a second position in the bitstream and being performed in parallel with the decoding of the first segment, and the second segment preceding the first segment in the bitstream.
1. An apparatus to parallelize data decompression, the apparatus comprising:
memory; and
processor circuitry to execute machine readable instructions to at least:
divide a compressed file into a quantity of segments;
identify a starting location for respective ones of the quantity of segments;
assign separate processing unit circuits to the respective ones of the quantity of segments;
for respective ones of the separate processing unit circuits:
select a speculative token location for a respective one of the quantity of segments;
speculatively decode a first candidate token at the speculative token location;
when the first candidate token is invalid, update the speculative token location based on a first token length value from the invalid first candidate token;
speculatively decode a second candidate token at the updated speculative token location; and
when the second candidate token is valid, extract a plurality of valid token locations corresponding to the respective segment.
2. The apparatus as defined in claim 1 , wherein the separate processing unit circuits include at least one of a processor or a processor core.
3. The apparatus as defined in claim 1 , wherein the respective one of the separate processing unit circuits is to identify a subsequent valid token location based on length information corresponding to the second candidate token.
4. The apparatus as defined in claim 1 , wherein the quantity of segments is based on a quantity of available separate processing unit circuits.
5. The apparatus as defined in claim 1 , wherein respective ones of the quantity of segments include a same length.
6. The apparatus as defined in claim 1 , wherein respective ones of the quantity of segments is non-overlapping.
7. The apparatus as defined in claim 1 , wherein respective ones of the separate processing unit circuitry are to merge decoded data corresponding to the second candidate token, the decoded data corresponding to the compressed file.
8. An apparatus to parallelize data decompression, the apparatus comprising:
segment training circuitry to:
divide a compressed file into a quantity of segments; and
identify a starting location for respective ones of the quantity of segments;
parallelization circuitry to assign separate processing unit circuits to the respective ones of the quantity of segments;
for respective ones of the separate processing unit circuits;
the segment training circuitry to select a speculative token location for a respective one of the quantity of segments;
decoding circuitry to:
speculatively decode a first candidate token at the speculative token location;
when the first candidate token is invalid, the segment training circuitry to update the speculative token location based on a first token length value from the invalid first candidate token, and the decoding circuitry to speculatively decode a second candidate token at the updated speculative token location; and
when the second candidate token is valid, extract a plurality of valid token locations corresponding to the respective segment.
9. The apparatus as defined in claim 8 , wherein the separate processing unit circuits include at least one of a processor or a processor core.
10. The apparatus as defined in claim 8 , wherein the respective one of the separate processing unit circuits is to identify a subsequent valid token location based on length information corresponding to the second candidate token.
11. The apparatus as defined in claim 8 , wherein the quantity of segments is based on a quantity of available separate processing unit circuits.
12. The apparatus as defined in claim 8 , wherein respective ones of the quantity of segments include a same length.
13. The apparatus as defined in claim 8 , wherein respective ones of the quantity of segments is non-overlapping.
14. The apparatus as defined in claim 8 , further including segment merging circuitry to merge decoded data corresponding to the second candidate token for respective ones of the separate processing unit circuitry, the decoded data corresponding to the compressed file.
15. A non-transitory computer readable storage medium comprising instructions that, when executed by at least one processing circuit, cause the at least one processing circuit to at least:
divide a compressed file into a quantity of segments;
identify a starting location for respective ones of the quantity of segments;
assign separate ones of the at least one processing circuit to the respective ones of the quantity of segments;
for the separate ones of the at least one processing circuit:
select a speculative token location for a respective one of the quantity of segments;
speculatively decode a first candidate token at the speculative token location;
when the first candidate token is invalid, update the speculative token location based on a first token length value from the invalid first candidate token;
speculatively decode a second candidate token at the updated speculative token location; and
when the second candidate token is valid, extract a plurality of valid token locations corresponding to the respective segment.
16. The non-transitory computer readable storage medium as defined in claim 15 , wherein the separate ones of the at least one processing circuit includes at least one of a processor core or a processor.
17. The non-transitory computer readable storage medium as defined in claim 15 , wherein the separate ones of the at least one processing circuit are to identify a subsequent valid token location based on length information corresponding to the second candidate token.
18. The non-transitory computer readable storage medium as defined in claim 15 , wherein the quantity of segments is based on a quantity of available separate processing unit circuits.
19. The non-transitory computer readable storage medium as defined in claim 15 , wherein respective ones of the quantity of segments include a same length.
20. The non-transitory computer readable storage medium as defined in claim 15 , wherein respective ones of the quantity of segments is non-overlapping.