CN103427844A - High-speed lossless data compression method based on GPU-CPU hybrid platform - Google Patents

Abstract

The invention discloses a high-speed lossless data compression method based on a mixed platform of GPU and CPU, comprising: reading the data file to be compressed by the CPU, copying the data file to be compressed from the internal memory to the global memory of the GPU, and setting the thread on the GPU Block group bk[a], the number of threads in each thread block b, set the length of the compression dictionary window as c, and set the head pointer pointing to the first compression dictionary window as p_dic_h, and set the size of the read-ahead window as d , the pointer p_pre_r pointing to the first pre-read window, the initial value of the pointer is set to p_dic_h-c, the initialization worker thread group threads[a*b], and (a*b/2)/c gMatrix matrix, its size For c*d, call (a*b/2) threads in the working thread group threads[a*b] to process q=(a*b/2)/c lengths of c+d in the data file to be compressed Data, in each of the q result matrices gMatrix, find the oblique segment with the most consecutive 1s, and determine the ternary result array locations[p] of each result matrix. The invention can greatly improve the compression rate of massive data.

Description

A high-speed lossless data compression method based on GPU and CPU mixed platform

technical field

The invention belongs to the technical field of computer data compression, and more specifically relates to a high-speed lossless data compression method based on a mixed platform of GPU and CPU.

Background technique

According to the research of International Data Corporation (IDC), in the past 10 years, the total amount of global information will double every two years. In 2011, the total amount of data created and copied globally was 1.8ZB (1800EB), and by 2015 it will reach 8ZB (8000EB), and in the next ten years, around 2020, the global data will be 50 times higher than it is now . At the same time, although network bandwidth and new storage technologies have also been rapidly developed, they are still far from meeting the performance requirements of current massive data transmission and storage. One of the key technologies to solve the challenges of mass data transmission and storage is data compression. Through data compression technology, the data capacity that needs to be transmitted and stored can be effectively reduced, thereby effectively controlling the cost of data transmission and storage, and realizing low-cost and efficient management of data.

The traditional compression theory and compression algorithm based on the CPU platform focus on how to improve the compression ratio of data. The era of massive data puts forward higher requirements on the speed of data compression. In order to improve the compression rate, data parallel compression becomes a new development direction. The premise of parallel data compression is to find data-level parallelism. It is a natural parallel idea to divide data into blocks and compress each block at the same time. Existing algorithms such as J.Gilchrist, GZIP, and S.Pradhan use multi-threading, multi-core, and cluster methods to achieve parallel data compression on the CPU platform. However, in practical applications, as the amount of data to be processed increases, due to the large amount of communication generated in the interaction, the intermediate results need to occupy a large amount of memory space, and the inherent hardware architecture of the CPU itself is not suitable for large-scale parallelism. Computing characteristics, all these factors make the parallel compression algorithm under the CPU platform not make the compression rate reach the expected goal.

Some scholars have also improved some classic lossless data compression algorithms under some CPU platforms, such as the run-length encoding algorithm, BZIP2 algorithm, etc., and transplanted them to the GPU platform. In order to solve the above-mentioned shortcomings of CPU compression, these algorithms focus on how to use the shared memory and global memory of GPU, so as to minimize the communication between different modules, reduce the memory occupation, and then improve the compression rate. However, since these algorithms are invented based on the CPU platform, they are not suitable for the different hardware structure of the GPU in essence. Therefore, in practical applications, the improvement of the compression rate still needs to be improved.

Contents of the invention

Aiming at the above defects or improvement needs of the prior art, the present invention provides a high-speed lossless data compression method based on a hybrid platform of GPU and CPU, the purpose of which is to decompose the process of data compression into two parts: parallel computing and serial computing , the parallel computing part includes dividing multiple compressed data dictionaries and pre-reading windows, organizing them into multiple matrices, and handing over the data files to be compressed to multiple thread blocks in the GPU to complete in parallel, while compressing and encoding the serial computing part The generation and output are completed by the CPU. This working mode combines the advantages and strengths of the GPU and the CPU itself, thereby greatly improving the compression rate of massive data without reducing the compression rate.

In order to achieve the above object, according to one aspect of the present invention, a kind of high-speed lossless data compression method based on GPU and CPU hybrid platform is provided, comprising the following steps:

(1) The CPU reads the data file to be compressed, and copies the data file to be compressed from the memory to the global memory of the GPU;

(2) Set the thread block group bk[a] on the GPU, the number of threads b in each thread block, where a is the total number of thread blocks;

(3) Set the length of the compressed dictionary window as c, and set the head pointer pointing to the first compressed dictionary window as p_dic_h;

(4) Set the size of the pre-read window to d, point to the pointer p_pre_r of the first pre-read window, and set the initial value of the pointer to p_dic_h-c;

(5) Initialize the worker thread group threads[a*b], and (a*b/2)/c gMatrix matrices, whose size is c*d;

(6) Call (a*b/2) threads in the working thread group threads[a*b] to process q=(a*b/2)/c data whose length is c+d in the data file to be compressed;

(7) Find the oblique segment with the most consecutive 1s in each of the q result matrices gMatrix, and determine the locations[p] of the ternary result array of each result matrix. Each element in the array stores a ternary result (x, y, length), where p is the number of slash segments in the result matrix, and is equal to c+d–1, x represents the offset of the slash segment relative to the compression dictionary corresponding to the result matrix where it is located, and y represents the relative The offset of the read-ahead window corresponding to the result matrix where it is located, and length indicates the length of the oblique segment;

(8) Find the element with the largest length value in the locations[p] array corresponding to each gMatrix: set thread T3, whose thread number is th3, and T3 is the 0th thread in the thread group threads[a*b] to the ( One of the q-1) threads, the T3 thread is responsible for finding the element with the largest length value in the ternary result array locations[p] corresponding to each gMatrix matrix, and storing its corresponding parameters x, y and length in the global The matching result array match[q], each element in the array also stores a ternary result (x, y, length);

(9) Compress the data file to be compressed according to the matching result array match[q];

(10) Determine whether the pointer p_pre_r has reached the end of the data file to be compressed, if so, the process ends; otherwise, slide the dictionary window and the pre-reading window forward, that is, set p_pre_r=p_pre_r+q*d, p_dic_h=p_dic_h+q *d, then return to step (6).

Preferably, the value of d is equal to 16*n, and the range of n is 1-8.

Preferably, in step (6), p_dic_h points to the head of the first compression dictionary window of the data file to be compressed, p_pre_r points to the head of the first read-ahead window of the data file to be compressed, and (p_dic_h-d) points to the first Two compression dictionary window headers, (p_pre_r-d) point to the second pre-read window header of the data file to be compressed, so divided, one cycle can process q pairs of compression dictionary windows and pre-read data windows.

Preferably, step (6) is specifically, for each to-be-processed compression dictionary window and the data of the corresponding pre-read data window, respectively perform the following steps:

(6-1) Set counter i=0;

(6-2) Set thread T1, whose thread number is th1, T1 is the (c*k)th thread to (c*(k+1)-1)th thread in the thread group threads[a*b/2] One of the threads, which judges whether the (th1 mod c)th byte in the kth compression dictionary window and the i*16 to (i+1)*16-1th byte in the kth pre-reading data window are Match, where 0<=k<q, when the two bytes match, return value 1, otherwise return value 0, and write the matching result back to the position in the kth gMatrix matrix of the global memory ((th1 modc) *d+i*16) into position ((th1 mod c)*d+i*16+16);

(6-3) Set i=i+1, and judge whether i<n, if yes, go to step (6-2), otherwise go to step (7).

Preferably, when the length is less than 3, it indicates that no match is found, and at this time, x and y are directly assigned a value of -1.

Preferably, step (7) specifically includes the following sub-steps:

(7-1) Set thread T2, whose thread number is th2, T2 is the (c*k)th thread to (c*(k+1)+d-1)th thread in the thread group threads[a*b] One of the threads, T2 is responsible for finding the sub-segment with the most consecutive 1s in a slash segment, and recording the parameters x, y and length corresponding to the sub-segment;

(7-2) Thread T2 stores the obtained corresponding data x, y and length in the (th2 mod p)th element of the ternary result array locations.

Preferably, step (9) specifically includes the following sub-steps:

(9-1) Transfer the matching result array match[q] from the GPU to the main memory in the CPU;

(9-2) The CPU converts the data stored in the matching result array match[q] into the longest matching offset and length of the substring in the pre-reading window in the compression dictionary window, and outputs the compressed code triplet compress [q], each element in the compressed encoding ternary array stores a ternary result (flag, offset, length). Among them, flag is a flag byte, indicating whether the output is compressed data, and offset and length represent the read-ahead window respectively. The offset and length of the longest match of the substring in the corresponding compression dictionary window;

(9-3) Perform data compression on the data file to be compressed according to the flag byte.

Preferably, in step (9-3), the obtained flag byte type includes original flag byte and mixed flag byte, the first bit of the original flag byte is 0, and the last 7 bits indicate the original data length of the output, and the following is at most It can output 128 consecutive original data bytes. The first bit of the mixed flag byte is 1, and the last 7 bits indicate 7 original and compressed mixed data. When the corresponding bit is 0, it means that the original data is output, and when it is 1, it means output What is used is compression coding, whereby the data is compressed, and if no match is found, the data is output as it is.

According to another aspect of the present invention, a kind of high-speed lossless data compression system based on GPU and CPU hybrid platform is provided, comprising:

The first module is used to read the data file to be compressed, and copy the data file to be compressed from the memory to the global memory of the GPU;

The second module is used to set the thread block group bk[a] on the GPU, the number of threads b in each thread block, where a is the total number of thread blocks;

The third module is used to set the length of the compressed dictionary window as c, and set the head pointer pointing to the first compressed dictionary window as p_dic_h;

The fourth module is used to set the size of the pre-reading window as d, pointing to the pointer p_pre_r of the first pre-reading window, and the initial value of the pointer is set to p_dic_h-c;

The fifth module is used to initialize the worker thread group threads[a*b], and (a*b/2)/c gMatrix matrices, whose size is c*d;

The sixth module is used to call (a*b/2) threads in the working thread group threads[a*b] to process q=(a*b/2)/c in the data file to be compressed, the length of which is c+d The data;

The seventh module is used to find the oblique segment with the most consecutive 1s in each of the q result matrices gMatrix, and determine the locations[p] of the ternary result array of each result matrix, and each element in the array stores a ternary result (x, y, length), where p is the number of slash segments in the result matrix, and is equal to c+d–1, x represents the offset of the slash segment relative to the compression dictionary corresponding to the result matrix where it is located, and y represents the The offset of the slash segment relative to the read-ahead window corresponding to the result matrix where it is located, length indicates the length of the slash segment;

The eighth module is used to find the element with the maximum length value in the locations[p] array corresponding to each gMatrix: set thread T3, whose thread number is th3, and T3 is the 0th thread in the thread group threads[a*b] To one of the (q-1)th threads, the T3 thread is responsible for finding the element with the largest length value in the ternary result array locations[p] corresponding to each gMatrix matrix, and its corresponding parameters x, y and length Stored in the global matching result array match[q], each element in the array also stores a ternary result (x, y, length);

The ninth module is used to compress the data file to be compressed according to the matching result array match[q];

The tenth module is used to judge whether the pointer p_pre_r has reached the end of the data file to be compressed, if so, the process ends; otherwise, slide the dictionary window and the pre-reading window forward, that is, set p_pre_r=p_pre_r+q*d, p_dic_h= p_dic_h+q*d, then return to the sixth module.

Generally speaking, compared with the prior art, the above technical solutions conceived by the present invention can achieve the following beneficial effects:

(1) The present invention speeds up the matching speed of data through matrix parallel matching: the working mode of matrix parallel matching proposed by the present invention processes q matrix matching of c*q in parallel in one cycle, so that the step size of cyclic matching is by The d byte is increased to q*d byte, thus speeding up the matching speed;

(2) The present invention realizes asynchronous processing and overlaps the time of redundant data discovery and compression coding output, so that the operations in CPU and GPU can be executed in a form similar to pipeline, thereby reducing the overall data compression time to a certain extent. time, increasing the rate of compression.

Description of drawings

Fig. 1 is a flow chart of the high-speed lossless data compression method based on the hybrid platform of GPU and CPU in the present invention.

Fig. 2 is a schematic diagram of the division of the compression dictionary window of the data file to be compressed and the corresponding pre-reading window.

3 to 6 are schematic diagrams of application examples of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention. In addition, the technical features involved in the various embodiments of the present invention described below can be combined with each other as long as they do not constitute a conflict with each other.

As shown in Figure 1, the high-speed lossless data compression method based on GPU and CPU mixed platform of the present invention comprises the following steps:

(1) The CPU reads the data file to be compressed, and copies the data file to be compressed from the memory to the global memory of the GPU;

(2) Set the thread block group bk[a] on the GPU, the number of threads in each thread block b, where a is the total number of thread blocks, which is a positive integer, and the value range of b is 256 to 1024;

(3) Set the length of the compression dictionary window to c, and set the head pointer pointing to the first compression dictionary window to p_dic_h; specifically, the value range of c is 2KB-8KB, and the preferred value is 4KB, p_dic_h is initially The value points to the beginning of the compressed data file;

(4) Set the size of the pre-reading window to d, point to the pointer p_pre_r of the first pre-reading window, the initial value of the pointer is set to p_dic_h-c, the value of d is equal to 16*n, and the value range of n is 1-8, The preferred value is 4, that is, the preferred value of each pre-read window is 64B;

(5) Initialize the worker thread group threads[a*b], and (a*b/2)/c gMatrix matrices, whose size is c*d;

(6) Call (a*b/2) threads in the working thread group threads[a*b] to process q=(a*b/2)/c data whose length is c+d in the data file to be compressed; The division of the compression dictionary window of the data file to be compressed and the corresponding read-ahead window is shown in Figure 2, p_dic_h points to the head of the first compression dictionary window of the data file to be compressed, and p_pre_r points to the first read-ahead of the data file to be compressed The window header; and (p_dic_h-d) points to the second compression dictionary window header of the compressed data file, (p_pre_r-d) points to the second pre-read window header of the data file to be compressed, so divided, one cycle, can process q pairs of compression Dictionary window and read-ahead data window. Specifically, for each to-be-processed compression dictionary window and the data of the corresponding pre-read data window, the following steps are performed respectively:

(6-1) Set counter i=0;

(6-2) Set thread T1, whose thread number is th1, T1 is the (c*k)th thread to (c*(k+1)-1)th thread in the thread group threads[a*b/2] One of the threads, which judges whether the (th1 mod c)th byte in the kth compression dictionary window and the i*16 to (i+1)*16-1th byte in the kth pre-reading data window are Match (that is, whether the two are equal), where 0<=k<q, when the two bytes match (that is, equal), return a value of 1, otherwise return a value of 0, and write the matching result back to the kth of the global memory Position ((th1 mod c)*d+i*16) in a gMatrix matrix to position ((th1 mod c)*d+i*16+16);

(6-3) Set i=i+1, and judge whether there is i<n, if yes, go to step (6-2), otherwise go to step (7);

(7) Find the oblique segment with the most consecutive 1s in each of the q result matrices gMatrix, and determine the locations[p] of the ternary result array of each result matrix. Each element in the array stores a ternary result (x, y, length), where p is the number of slash segments in the result matrix, and is equal to c+d–1, x represents the offset of the slash segment relative to the compression dictionary corresponding to the result matrix where it is located, and y represents the relative The offset of the read-ahead window corresponding to the result matrix where it is located, length indicates the length of the slash segment (that is, the number including "1"), when the length is less than 3, it indicates that no match is found (this is because if a match When the length of the substring is less than two bytes, the compressed code is longer than the uncompressed one, which is meaningless), at this time, x and y have no meaning, and can be directly assigned to -1;

This step specifically includes the following sub-steps:

(7-1) Set thread T2, whose thread number is th2, T2 is the (c*k)th thread to (c*(k+1)+d-1)th thread in the thread group threads[a*b] One of the threads, T2 is responsible for finding the sub-segment with the most consecutive 1s in a slash segment, and recording the parameters x, y and length corresponding to the sub-segment;

(7-2) Thread T2 stores the corresponding data x, y and length obtained by it in the (th2 mod p)th element of the ternary result array locations;

(8) Find the element with the largest length value in the locations[p] array corresponding to each gMatrix: set thread T3, whose thread number is th3, and T3 is the 0th thread in the thread group threads[a*b] to the ( One of the q-1) threads, the T3 thread is responsible for finding the element with the largest length value in the ternary result array locations[p] corresponding to each gMatrix matrix, and storing its corresponding parameters x, y and length in the global The matching result array match[q], each element in the array also stores a ternary result (x, y, length);

(9) Compress the data file to be compressed according to the matching result array match[q], specifically including the following sub-steps;

(9-1) Transfer the matching result array match[q] from the GPU to the main memory in the CPU;

(9-2) The CPU converts the data stored in the matching result array match[q] into the longest matching offset and length of the substring in the pre-reading window in the compression dictionary window, and outputs the compressed code triplet compress [q], each element in the compressed encoding ternary array stores a ternary result (flag, offset, length). Among them, flag is a flag byte, indicating whether the output is compressed data, and offset and length represent the read-ahead window respectively. The offset and length of the longest match of the substring in the corresponding compression dictionary window;

(9-3) Perform data compression on the data file to be compressed according to the flag bytes; specifically, there are two types of flag bytes obtained, one is the original flag byte, the other is the mixed flag byte, and the original flag byte The first bit of the section is 0, and the last 7 bits indicate the length of the original data output, and a maximum of 128 consecutive original data bytes can be output at the end; while the first bit of the mixed flag byte is 1, and the last 7 bits indicate 7 original and compressed bytes. For mixed data, when the corresponding bit is 0, it means that the output is the original data, and when it is 1, it means that the output is compression coding, thereby realizing data compression; if no match is found, the data is output as it is;

(10) Determine whether the pointer p_pre_r has reached the end of the data file to be compressed, if so, the process ends; otherwise, slide the dictionary window and the pre-reading window forward, that is, set p_pre_r=p_pre_r+q*d, p_dic_h=p_dic_h+q *d, then return to step (6).

The present invention is based on the high-speed lossless data compression system of GPU and CPU hybrid platform, is characterized in that, comprises:

The first module is used to read the data file to be compressed, and copy the data file to be compressed from the memory to the global memory of the GPU;

The second module is used to set the thread block group bk[a] on the GPU, the number of threads b in each thread block, where a is the total number of thread blocks;

The third module is used to set the length of the compressed dictionary window as c, and set the head pointer pointing to the first compressed dictionary window as p_dic_h;

The fourth module is used to set the size of the pre-reading window as d, pointing to the pointer p_pre_r of the first pre-reading window, and the initial value of the pointer is set to p_dic_h-c;

The fifth module is used to initialize the worker thread group threads[a*b], and (a*b/2)/c gMatrix matrices, whose size is c*d;

The sixth module is used to call (a*b/2) threads in the working thread group threads[a*b] to process q=(a*b/2)/c in the data file to be compressed, the length of which is c+d The data;

The seventh module is used to find the oblique segment with the most consecutive 1s in each of the q result matrices gMatrix, and determine the locations[p] of the ternary result array of each result matrix, and each element in the array stores a ternary result (x, y, length), where p is the number of slash segments in the result matrix, and is equal to c+d–1, x represents the offset of the slash segment relative to the compression dictionary corresponding to the result matrix where it is located, and y represents the The offset of the slash segment relative to the read-ahead window corresponding to the result matrix where it is located, length indicates the length of the slash segment;

The eighth module is used to find the element with the maximum length value in the locations[p] array corresponding to each gMatrix: set thread T3, whose thread number is th3, and T3 is the 0th thread in the thread group threads[a*b] To one of the (q-1)th threads, the T3 thread is responsible for finding the element with the largest length value in the ternary result array locations[p] corresponding to each gMatrix matrix, and its corresponding parameters x, y and length Stored in the global matching result array match[q], each element in the array also stores a ternary result (x, y, length);

The ninth module is used to compress the data file to be compressed according to the matching result array match[q];

The tenth module is used to judge whether the pointer p_pre_r has reached the end of the data file to be compressed, if so, the process ends; otherwise, slide the dictionary window and the pre-reading window forward, that is, set p_pre_r=p_pre_r+q*d, p_dic_h= p_dic_h+q*d, then return to the sixth module.

example

In order to clearly illustrate the principles of the present invention, the implementation process of the present invention is illustrated below with examples.

(1) The CPU reads the data file to be compressed, and copies the compressed data file from the memory to the global memory of the GPU;

(2) Set the thread block group bk[1024] on the GPU, and the number of threads in each thread block is 512;

(3) Set the length of the compression dictionary window to 4096 bytes, and the head pointer pointing to the first compression dictionary window is p_dic_h=0;

(4) Set the length of the pre-read window to 64 bytes, and the pointer to the first pre-read window is p_pre_r=4096;

(5) Initialize the worker thread group threads[1024*512], and 64 gMatrix matrices, the size of which is 4096*64;

(6) Call 1024*256 threads in the working thread group threads[1024*512] to process 64 pieces of data whose length is (4096+64) B in the data file to be compressed; the compression dictionary window of the data file to be compressed and its corresponding The division of the read-ahead window is shown in Figure 3:

p_dic_h points to the header of the first compressed dictionary window of the data file to be compressed, p_pre_r points to the header of the first pre-read window of the data file to be compressed; and (p_dic_h-64) points to the header of the second compressed dictionary window of the compressed data file, (p_pre_r -64) points to the header of the second read-ahead window of the data file to be compressed, so divided, one cycle can process 64 pairs of compression dictionary windows and read-ahead data windows. Specifically, for each pending compression dictionary window and the data of the corresponding pre-reading data window, the following steps are respectively performed (here, we choose to process the first pair of compression dictionary windows and pre-reading data windows) illustrate):

In order to describe the compression process simply and clearly, we choose the data in the first compression dictionary in the data file to be compressed as "hellothisaeybc...isa" with a length of 4096 bytes; and the first 16B data of the data in the first read-ahead window is "thisisaexampletosh". There are 4096 threads from T0 to T4095 in the thread group, and their thread numbers are 0 to 4095 respectively. Tm1 (m1∈[0,4095]) is any one of the threads, and m1 is its thread number. This thread is responsible for judging the compression dictionary window. Whether the m1-th byte matches the 0-15th byte in the pre-read data window (that is, whether the two are equal), when the two bytes match (that is, are equal), return a value of 1, otherwise return a value of 0, and Write the matching result back into the corresponding gMatrix matrix in the global memory from position m1*64 to position m1*64+16. Since only 16B of data is selected for compression, we only execute a loop when i=0; obtain a result of 1/4 of the result matrix gMatrix with a size of 4096*64, that is, the size of the result obtained this time is 4096* 16, as shown in Figure 4:

(7) The following only describes how to find the slash segment with the most consecutive 1s in the first gMatrix of the 64 result matrices gMatrix.

(7-1) There are (4096+15) threads from T0 to T4110 in the thread group, and their thread numbers are 0 to 4110 respectively, Tm2(m2∈[0,4110]) is any one of the threads, and m2 is its thread number , Tm2 is responsible for finding the sub-segment with the most consecutive 1s in a slash segment, as shown in Figure 5:

(7-2) The thread Tm2 obtains the parameters x, y and length, and stores them in the m2th element of the ternary result array locations;

In this example, thread T5 and thread T10 have found multiple consecutive sub-line segments of 1, which assign values to the elements in the corresponding locations array: locations(5)={5, 0, 6}, locations(10)={10 , 2, 3}, the values of other elements of the locations array are {-1, -1, 0}, as shown in Figure 6:

(8) Find the element with the largest length value in the locations[p] array corresponding to each gMatrix: there are 64 threads from T0 to T63 in the thread group, and their thread numbers are 0 to 63, Tm3(m3∈[0,63 ]) is any one of the threads, m3 is its thread number, and Tm3 is responsible for finding the element with the largest length value in the locations array corresponding to each gMatrix matrix, and storing its corresponding parameters x, y and length into the global matching result Array match[64], each element in this array also stores a ternary result (x, y, length). In this example, we use thread T0 to find the locations element with the largest length value in the corresponding 0th result matrix gMatrix as the 5th element, and write its related parameters into the 0th element in the array match, that is, match( 0) = {5, 0, 6};

(9) Compress the data file to be compressed according to the matching result array match[64], specifically including the following sub-steps;

(9-1) Transfer the matching result array match[64] from the GPU to the main memory in the CPU;

(9-2) The CPU converts the data stored in the matching result array match[64] into the longest matching offset and length of the substring in the pre-reading window in the compression dictionary window, and outputs the compressed code triplet compress [64], in this example, the data of match(0) is converted to the offset and length of the longest match in the 0th pre-reading window in the 0th compression dictionary window are 5 and 6 respectively, and the Output a mixed flag byte, that is, the flag value is 224 (11100000), compress(0)={224, 5, 6}; at this time, the first (4096+16) bytes of the data file to be compressed are compressed and output as : hellothisaeybc...isa22456amplet3osh. At this time, the 4096B data in the first compression dictionary window cannot be compressed, and it is output as it is, followed by 22456, indicating that a 6-byte long substring in the pre-read data window is compressed, and its original text is the compression dictionary The window starts at offset 5, with a length of 6 bytes, and then outputs a string of uncompressed original data samplet, with a length of 6 bytes; then outputs an original flag byte, whose value is 3 (00000011), and finally , followed by the output of 3 bytes of uncompressed raw data osh.

(10) Determine whether the pointer p_pre_r has reached the end of the data file to be compressed. If it points to the end of the file, the process ends; otherwise, slide the dictionary window and the pre-reading window forward, that is, set p_pre_r=p_pre_r+64*64, p_dic_h= p_dic_h+64*64, then return to step (6).

It is easy for those skilled in the art to understand that the above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention, All should be included within the protection scope of the present invention.

Claims (9)

1. A high-speed lossless data compression method based on GPU and CPU mixed platform, is characterized in that, comprises the following steps: (1) The CPU reads the data file to be compressed, and copies the data file to be compressed from the memory to the global memory of the GPU; (2) Set the thread block group bk[a] on the GPU, the number of threads b in each thread block, where a is the total number of thread blocks; (3) Set the length of the compressed dictionary window as c, and set the head pointer pointing to the first compressed dictionary window as p_dic_h; (4) Set the size of the pre-read window to d, point to the pointer p_pre_r of the first pre-read window, and set the initial value of the pointer to p_dic_h-c; (5) Initialize the worker thread group threads[a*b], and (a*b/2)/c gMatrix matrices, whose size is c*d; (6) Call (a*b/2) threads in the working thread group threads[a*b] to process q=(a*b/2)/c data whose length is c+d in the data file to be compressed; (7) Find the oblique segment with the most consecutive 1s in each of the q result matrices gMatrix, and determine the locations[p] of the ternary result array of each result matrix. Each element in the array stores a ternary result (x, y, length), where p is the number of slash segments in the result matrix, and is equal to c+d–1, x represents the offset of the slash segment relative to the compression dictionary corresponding to the result matrix where it is located, and y represents the relative The offset of the read-ahead window corresponding to the result matrix where it is located, and length indicates the length of the oblique segment; (8) Find the element with the largest length value in the locations[p] array corresponding to each gMatrix: set thread T3, whose thread number is th3, and T3 is the 0th thread in the thread group threads[a*b] to the ( One of the q-1) threads, the T3 thread is responsible for finding the element with the largest length value in the ternary result array locations[p] corresponding to each gMatrix matrix, and storing its corresponding parameters x, y and length in the global The matching result array match[q], each element in the array also stores a ternary result (x, y, length); (9) Compress the data file to be compressed according to the matching result array match[q]; (10) Determine whether the pointer p_pre_r has reached the end of the data file to be compressed, if so, the process ends; otherwise, slide the dictionary window and the pre-reading window forward, that is, set p_pre_r=p_pre_r+q*d, p_dic_h=p_dic_h+q *d, then return to step (6). 2. The high-speed lossless data compression method according to claim 1, wherein the value of d is equal to 16*n, and the value range of n is 1-8. 3. The high-speed lossless data compression method according to claim 1, characterized in that in step (6), p_dic_h points to the head of the first compression dictionary window of the data file to be compressed, and p_pre_r points to the first The header of the pre-read window, and (p_dic_h-d) points to the header of the second compressed dictionary window of the compressed data file, and (p_pre_r-d) points to the header of the second pre-read window of the data file to be compressed. In this way, one cycle can process q For compressed dictionary windows and read-ahead data windows. 4. The high-speed lossless data compression method according to claim 1, characterized in that the step (6) is specifically, for each data of the compression dictionary window to be processed and the corresponding pre-reading data window, respectively perform the following steps : (6-1) Set counter i=0; (6-2) Set thread T1, whose thread number is th1, T1 is the (c*k)th thread to (c*(k+1)-1)th thread in the thread group threads[a*b/2] One of the threads, which judges whether the (th1 mod c)th byte in the kth compression dictionary window and the i*16 to (i+1)*16-1th byte in the kth pre-reading data window are Match, where 0<=k<q, when the two bytes match, return value 1, otherwise return value 0, and write the matching result back to the position in the kth gMatrix matrix of the global memory ((th1 modc) *d+i*16) into position ((th1 mod c)*d+i*16+16); (6-3) Set i=i+1, and judge whether i<n, if yes, go to step (6-2), otherwise go to step (7). 5. The high-speed lossless data compression method according to claim 1, wherein when the length is less than 3, it indicates that no match is found, and at this time, x and y are directly assigned a value of -1. 6. The high-speed lossless data compression method according to claim 1, wherein step (7) specifically includes the following sub-steps: (7-1) Set thread T2, whose thread number is th2, T2 is the (c*k)th thread to (c*(k+1)+d-1)th thread in the thread group threads[a*b] One of the threads, T2 is responsible for finding the sub-segment with the most consecutive 1s in a slash segment, and recording the parameters x, y and length corresponding to the sub-segment; (7-2) Thread T2 stores the obtained corresponding data x, y and length in the (th2 mod p)th element of the ternary result array locations. 7. The high-speed lossless data compression method according to claim 1, wherein step (9) specifically includes the following sub-steps: (9-1) Transfer the matching result array match[q] from the GPU to the main memory in the CPU; (9-2) The CPU converts the data stored in the matching result array match[q] into the longest matching offset and length of the substring in the pre-reading window in the compression dictionary window, and outputs the compressed code triplet compress [q], each element in the compressed encoding ternary array stores a ternary result (flag, offset, length). Among them, flag is a flag byte, indicating whether the output is compressed data, and offset and length represent the read-ahead window respectively. The offset and length of the longest match of the substring in the corresponding compression dictionary window; (9-3) Perform data compression on the data file to be compressed according to the flag byte. 8. The high-speed lossless data compression method according to claim 7, characterized in that, in step (9-3), the obtained flag byte type includes original flag byte and mixed flag byte, and the original flag byte is first The bit is 0, the last 7 bits indicate the length of the original data output, and a maximum of 128 consecutive original data bytes can be output later, the first bit of the mixed flag byte is 1, and the last 7 bits indicate 7 original and compressed mixed data, corresponding to When the bit is 0, it means that the original data is output, and when it is 1, it means that the output is compression coding, thereby realizing data compression. If no match is found, the data is output as it is. 9. A high-speed lossless data compression system based on a GPU and CPU hybrid platform, characterized in that it comprises: The first module is used to read the data file to be compressed, and copy the data file to be compressed from the memory to the global memory of the GPU; The second module is used to set the thread block group bk[a] on the GPU, the number of threads b in each thread block, where a is the total number of thread blocks; The third module is used to set the length of the compressed dictionary window as c, and set the head pointer pointing to the first compressed dictionary window as p_dic_h; The fourth module is used to set the size of the pre-reading window as d, pointing to the pointer p_pre_r of the first pre-reading window, and the initial value of the pointer is set to p_dic_h-c; The fifth module is used to initialize the worker thread group threads[a*b], and (a*b/2)/c gMatrix matrices, whose size is c*d; The sixth module is used to call (a*b/2) threads in the working thread group threads[a*b] to process q=(a*b/2)/c in the data file to be compressed, the length of which is c+d The data; The seventh module is used to find the oblique segment with the most consecutive 1s in each of the q result matrices gMatrix, and determine the locations[p] of the ternary result array of each result matrix, and each element in the array stores a ternary result (x, y, length), where p is the number of slash segments in the result matrix, and is equal to c+d–1, x represents the offset of the slash segment relative to the compression dictionary corresponding to the result matrix where it is located, and y represents the The offset of the slash segment relative to the read-ahead window corresponding to the result matrix where it is located, length indicates the length of the slash segment; The eighth module is used to find the element with the maximum length value in the locations[p] array corresponding to each gMatrix: set thread T3, whose thread number is th3, and T3 is the 0th thread in the thread group threads[a*b] To one of the (q-1)th threads, the T3 thread is responsible for finding the element with the largest length value in the ternary result array locations[p] corresponding to each gMatrix matrix, and its corresponding parameters x, y and length Stored in the global matching result array match[q], each element in the array also stores a ternary result (x, y, length); The ninth module is used to compress the data file to be compressed according to the matching result array match[q]; The tenth module is used to judge whether the pointer p_pre_r has reached the end of the data file to be compressed, if so, the process ends; otherwise, slide the dictionary window and the pre-reading window forward, that is, set p_pre_r=p_pre_r+q*d, p_dic_h= p_dic_h+q*d, then return to the sixth module.

Images