The Research On Speculation Parallelization Method Of Variable-Length Decompression Based On OpenMP

The variable length coding compression algorithm maximizes the compression of data according to the encoding principle to facilitate data storage and communication.Its application domains include image and video processing,audio processing,network and data backup,and so on.Although the variable-length encoding compression algorithm is easy to divide data into data blocks for parallel compression,the variable-length encoding decompression algorithm is difficult to extract such coarse-grain parallelism,because the internal structure of data would have dependency after compression.As for this issue,this paper proposes the parallel execution of thread-level speculation based on OpenMP for variable-length decompression algorithms.The specific work of this paper is as follows:(1)Through the analysis of the variable-length encoding compression principle and the internal structure of the compressed data,a split function for compressed data is proposed,and the output can be speculatively decompressed independently.Three correctness verification methods are designed for the partition:Header verification Method,reconstructing Huffman tree verification method and detecting length verification method.(2)Based on the internal compilation process of GOMP,OpenMP is extended to support TLS(thread-level speculative parallel).The implementation of this part includes four steps:adding an OpenMP clause,adding TLS runtime functions,converting for loop structure.By extending OpenMP to form a framework that supports TLS technology,programmers can perform speculative parallel execution of programs with data has internal dependencies,overcoming the difficulty of parallel execution of programs caused by data dependencies,and greatly improving the operating efficiency of programs.(3)Based on the GOMP framework supporting TLS technology,thread-level speculation parallel execution of variable-length decompression algorithms is performed.Parallel execution of the variable-length decompression algorithm only follow the OpenMP programming model,and the new clauses are used to identify the speculate variables involved in the variable-length decompression algorithm.GOMP that supports TLS technology will execute the TLS operation process according to the corresponding identification during the compilation stage,so the variable-length decompression algorithm can be speculatively parallel executed.In summary,this paper solves three problems:traditional variable-length decompression algorithm is difficult to parallelize,the OpenMP framework is difficult to ensure the correct execution of programs which has dependency data,and it is difficult to write a speculative parallel program.It provides a new idea for irregular parallel algorithm.