Parallel processing of data having data dependencies for accelerating the launch and performance of operating systems and other computing applications

Patent metadata

Field	Value
Publication number	US-10083209-B2
Application number	US-201715493510-A
Country	US
Kind code	B2
Filing date	Apr 21, 2017
Priority date	Jun 26, 2014
Publication date	Sep 25, 2018
Grant date	Sep 25, 2018

Abstract

Representative embodiments are disclosed for a rapid and highly parallel decompression of compressed executable and other files, such as executable files for operating systems and applications, having compressed blocks including run length encoded (“RLE”) data having data-dependent references. An exemplary embodiment includes a plurality of processors or processor cores to identify a start or end of each compressed block; to partially decompress, in parallel, a selected compressed block into independent data, dependent (RLE) data, and linked dependent (RLE) data; to sequence the independent data, dependent (RLE) data, and linked dependent (RLE) data from a plurality of partial decompressions of a plurality of compressed blocks, to obtain data specified by the dependent (RLE) data and linked dependent (RLE) data, and to insert the obtained data into a corresponding location in an uncompressed file. The representative embodiments are also applicable to other types of data processing for applications having data dependencies.

First claim

It is claimed:

1. An apparatus for parallel decompression of a compressed file, the compressed file comprising a plurality of compressed blocks having independent data and dependent, run length encoded (“RLE”) data having data-dependent references spanning multiple compressed blocks of the plurality of compressed blocks, the apparatus comprising:
a memory circuit;
one or more processors or processor cores, of a plurality of processors or processor cores, adapted to partially decompress a selected compressed block, of the plurality of compressed blocks, into the independent data, the dependent RLE data, and any linked dependent RLE data; and
the one or more processors or processor cores further adapted to sequence the independent data, dependent RLE data, and linked dependent RLE data from a plurality of partial decompressions of the plurality of compressed blocks, to obtain data specified by the dependent RLE data and linked dependent RLE data, and to insert the obtained data into an uncompressed data file.

2. The apparatus of claim 1 , wherein the one or more processors or processor cores are further adapted to partially decompress multiple compressed blocks, of the plurality of compressed blocks, in parallel, into the independent data, the dependent RLE data, and the linked dependent RLE data.

3. The apparatus of claim 1 , wherein at least one first processor or processor core of the plurality of processors or processor cores is further adapted to identify a start or end of each compressed block of the plurality of compressed blocks and to transfer a single or individuated compressed block to a second processor or processor core of the plurality of processors or processor cores.

4. The apparatus of claim 3 , wherein the at least one first processor or processor core is further adapted to identify the start or end of a selected compressed block, of the plurality of compressed blocks, by performing a partial decompression of the selected compressed block.

5. The apparatus of claim 3 , wherein the plurality of processors or processor cores are operative in a plurality of pipelined stages.

6. The apparatus of claim 1 , wherein the one or more processors or processor cores are further adapted to identify the start or end of one or more compressed blocks of the plurality of compressed blocks, in parallel.

7. The apparatus of claim 6 , wherein the one or more processors or processor cores are further adapted to identify the start or end of a selected compressed block of the plurality of compressed blocks by performing a partial decompression of the selected compressed block, each processor or processor core of the one or more processors or processor cores commencing the partial decompression at a starting point in the selected compressed block having a predetermined or variable offset from partial decompression starting points of other processors or processor cores of the one or more processors or processor cores.

8. The apparatus of claim 1 , wherein at least one of the processors or processor cores is further adapted to create and store, in the memory circuit, metadata indicating a start or end of each compressed block of the plurality of compressed blocks.

9. The apparatus of claim 8 , wherein the one or more processors or processor cores are further adapted to utilize the stored metadata to identify the start or end of the selected compressed block of the plurality of compressed blocks.

10. The apparatus of claim 1 , wherein the one or more processors or processor cores are further adapted to perform a cyclic redundancy check of the uncompressed data file.

11. The apparatus of claim 1 , wherein at least one of the processors or processor cores, of the plurality of processors or processor cores is further adapted to compress and store the uncompressed data file in the memory circuit as a second compressed file having a plurality of second compressed blocks which have data dependencies solely within individual second compressed blocks of the plurality of second compressed blocks.

12. The apparatus of claim 1 , wherein at least one of the processors or processor cores, of the plurality of processors or processor cores, is further adapted to tag or identify the linked dependent RLE data; and wherein at least one processor or processor core, of the plurality of processors or processor cores, is further adapted to use the tag or identification of the linked dependent RLE data to sequence the obtaining of the data specified by the linked dependent RLE data subsequent to the obtaining of the data specified by the dependent RLE data.

13. A processor-implemented method for parallel decompression of a compressed file, the compressed file comprising a plurality of compressed blocks having independent data and dependent, run length encoded (“RLE”) data having data-dependent references spanning multiple compressed blocks of the plurality of compressed blocks, the method comprising:
using one or more processors or processor cores, partially decompressing a selected compressed block, of the plurality of compressed blocks, into the independent data, the dependent RLE data, and any linked dependent RLE data;
using one or more processors or processor cores, sequencing the independent data, dependent RLE data, and linked dependent RLE data from a plurality of partial decompressions of the plurality of compressed blocks, obtaining data specified by the dependent RLE data and linked dependent RLE data, and inserting the obtained data into an uncompressed data file; and
storing the uncompressed data file in a memory circuit.

14. The processor-implemented method of claim 13 , further comprising:
using a plurality of processors or processor cores, partially decompressing a corresponding selected compressed block of the plurality of compressed blocks, in parallel, into the independent data, the dependent RLE data, and the linked dependent RLE data.

15. The processor-implemented method of claim 13 , further comprising:
using one or more processors or processor cores, identifying a start or end of each compressed block of the plurality of compressed blocks by performing a partial decompression of each compressed block of the plurality of compressed blocks.

16. The processor-implemented method of claim 13 , further comprising:
using a plurality of processors or processor cores, identifying the start or end of one or more compressed blocks of the plurality of compressed blocks, in parallel, by performing a partial decompression of the one or more compressed blocks, selected compressed block, commencing at a plurality of different starting points in each compressed block of the one or more compressed blocks.

17. The processor-implemented method of claim 13 , further comprising:
using one or more processors or processor cores, creating and storing, in the memory circuit, metadata indicating a start or end of each compressed block of the plurality of compressed blocks.

18. The processor-implemented method of claim 17 , further comprising:
using one or more processors or processor cores, utilizing the stored metadata to identify the start or end of the selected compressed block of the plurality of compressed blocks.

19. The processor-implemented method of claim 13 , further comprising:
using one or more processors or processor cores, performing a cyclic redundancy check of the uncompressed data file.

20. The processor-implemented method of claim 13 , further comprising:
using one or more processors or processor cores, compressing and storing the

Assignees

• Cornami Inc

Inventors

• Master Paul L
• Furtek Frederick Curtis
• Knuttila Kim
• Mcgann L Brian

Classifications

• G06F16/24561 Primary

  Intermediate data storage techniques for performance improvement · CPC title

• H03M7/4093

  Variable length to variable length coding · CPC title

• G06F17/30501 Primary

  Physics · mapped topic

• H03M7/42

  using table look-up for the coding or decoding process, e.g. using read-only memory {(H03M7/4006 takes precedence)} · CPC title

• H03M7/40

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