CN103559020A - Method for realizing parallel compression and parallel decompression on FASTQ file containing DNA (deoxyribonucleic acid) sequence read data - Google Patents

Abstract

A method for parallel compression and parallel decompression of DNA reading sequence data FASTQ files, aiming at the compression and decompression of DNA reading sequence data FASTQ files, using circular double buffer queues, circular double memory mapping and memory mapping combined with data block processing, multiple Thread pipeline parallel compression and decompression processing, reading and writing sequence two-dimensional array and other technologies realize parallel compression and parallel decompression processing between multiple processes of FASTQ files and multiple threads within a process. It can be implemented based on MPI and OpenMP, or based on MPI and Pthread. The invention makes full use of the powerful computing capabilities of each computing node and the multi-core CPU in the node, and can solve the limitation of processor, memory and other resources that the serial compression and decompression program is subjected to.

Description

A parallel compression and decompression method for FASTQ files of DNA read sequence data

technical field

The invention relates to the fields of biological information, data compression and high-performance computing, in particular to a method for parallel compression and parallel decompression of DNA reading sequence data FASTQ files.

Background technique

One of the main tasks of bioinformatics is to collect and analyze large amounts of genetic data. These data are critical for genetic research, helping to identify genetic components that prevent or cause disease and develop targeted therapies. High-throughput sequencing methods and equipment generate massive amounts of short-read sequence data. The common way to store, manage and transmit DNA read sequence data is to use the FASTQ file format, which mainly contains DNA read sequence data and annotation information corresponding to each DNA base, such as Quality, which represents the uncertainty of the sequencing labeling process. Scores information. Read sequence markers and other descriptions such as device names are also included in the FASTQ files. Compared with other DNA data storage formats (such as FASTA), the FASTQ format can store more information, but it also causes a sharp increase in file size and storage space. At present, the algorithm research of effective lossless compression and decompression for base reading data and its annotation description information is a research hotspot.

For the compression of FASTQ file data, the G_SQZ algorithm (Tembe, W. et al. G-SQZ: compact encoding of genomic sequence and quality data. Bioinformatics2010; 26, 2192–2194.), and the DSRC algorithm studied by Deorowicz Sebastian et al. (Deorowicz S, Grabowski S. Compression of DNA sequence reads in FASTQ format. Bioinformatics2011;27:860-862.). Both algorithms use an indexing system that allows access at regular intervals (blocks for short), without the required information having to be decoded from scratch. The G_SQZ algorithm mainly uses Huffman encoding <base, Quality score> pairs, while the DSRC algorithm uses Huffman encoding alone for base data rows and Quality Score rows and supplemented by other fine compression processing (such as run-length processing, etc.). The advantage of this type of method is that it can randomly decode part of the data for access while retaining the relative sequence information of the data, and the lossless compression efficiency is high. This represents a class of FASTQ file compression methods, and for the convenience of description, hereinafter referred to as the block index serial algorithm.

Currently, the data required for genome sequence analysis has reached the order of terabytes. Large-scale sequencing centers are planning or have installed petabyte-scale storage devices. For these massive data, in order to reduce storage space and transmission time and facilitate real-time analysis of a large amount of genome sequence data, real-time data compression and decompression must be performed, which requires the powerful computing power of a high-performance computing platform. With the rapid development of high-performance computing platforms, make full use of the powerful computing power of multi-core CPUs on each computing node to compress and decompress massive FASTQ files in real time, which can solve the processing of serial compression and decompression programs. resource constraints such as processor processing power and memory.

The above-mentioned G-SQZ algorithm and DSRC algorithm are both serial algorithms, and there are no research articles and patents related to this type of algorithm based on multi-node multi-core CPU parallel algorithms.

Contents of the invention

In view of the fact that there are no researches and patents on parallel algorithms related to the above-mentioned G-SQZ and DSRC block index serial algorithms, the purpose of the present invention is to provide a serial compression of this type of FASTQ file block index The parallel compression and decompression method corresponding to the decompression algorithm, using multi-computing nodes and multi-core CPUs, can be implemented based on MPI+OpenMP, or based on MPI+Pthread; it can make full use of the powerful computing capabilities of high-performance computing platforms and greatly improve The speed of real-time analysis and processing of massive genome sequences provides an important technical basis for the wider application of genetic data.

The technical scheme of the present invention is as follows.

A method for parallel compression of the FASTQ file of DNA reading sequence data, comprising the following steps:

1. Parallel compression process task division

Determine the data to be processed in each process according to the size of the FASTQ file, the number of parallel compression processes, and the data characteristics of each read segment in the FASTQ file (including base information and other corresponding annotation information, which is marked as a record for the convenience of description below). start and end positions. Each process runs the process task division module, and distributes the raw data to be compressed approximately evenly to each process, so as to realize data parallelism. In this way, each process does not consume communication time with each other during processing, which improves the processing efficiency of data parallelism. Each process gets a separate compressed file, and the order of the compressed data is consistent with the process number.

2. Multi-thread pipeline parallel compression in parallel compression process

The process processing module includes a raw data reading thread, a compressed data writing thread and multiple compression working threads. The specific number of working threads can be set according to the number of hardware CPU cores and process settings.

The data processed by each process is divided into multiple blocks by the original data reading thread, and each block contains a specific fixed number of record data (the last block may be less than this fixed number).

Each worker thread has two circular double buffer queues, one is the original data circular double buffer queue, and the other is the compressed data circular double buffer queue. The original data circular double-buffer queue and the compressed data circular double-buffer queue have a similar structure, and the structure of the buffer is slightly different according to the stored data. The structure of each buffer will be introduced in detail in the specific implementation mode later. Each raw data circular double buffer queue contains two queues: one is an empty block buffer queue, and the other is a raw data block queue. Each compressed data circular double buffer queue also includes two queues: one is an empty block buffer queue, and the other is a compressed data block queue. The two circular double-buffered queues are handled the same way.

The following takes the original data circular double buffer queue as an example to describe its processing method in detail:

(1) Raw data circular double buffer queue initialization processing: instantiate the empty block buffer queue with a specific number of empty block buffers, and the original data block queue is empty.

(2) The raw data reading thread reads a raw data block.

(3) Obtain an empty block buffer at the head of the empty block buffer queue.

(4) Fill this acquired empty block buffer with raw data blocks.

(5) Put this padded raw data block at the end of the raw data block queue.

(6) The compression worker thread obtains the block data in an original data block buffer from the head of the original data block queue for compression processing.

(7) Clear the original data block buffer and put it into the empty block buffer queue.

In each process, the parallel compression pipeline processing of the data in the unit of the original data block is carried out. The specific pipeline parallel processing flow is as follows:

(1) The original data reading thread continuously parses and reads the original data block according to the characteristics of the recorded data, loops to find the empty block buffer in the original data circular double buffer queue of each compression worker thread in turn, and puts the original data block in the input, and then release this block buffer to the end of the raw data block queue in this circular double buffer queue.

(2) Each compression worker thread continuously obtains the original data block from the head of the original data block queue in the original data circular double buffer queue of this thread, and then performs compression processing.

(3) Each compression worker thread continuously fills the compressed block data into the empty block buffer in the obtained compressed data circular double buffer queue of this thread, and releases this buffer to the compression of this circular double buffer queue The tail of the data block queue.

(4) The compressed data writing thread continuously searches for the thread number of the block data that has been compressed and processed in sequence according to the block number from small to large, and obtains the compressed data block queue head in the compressed data circular double buffer queue in this thread This block in compressed data is written to the final compressed file.

For the specific algorithms and end conditions of the above-mentioned threads, refer to the specific implementation mode for details.

In the original data reading thread, memory mapping technology combined with FASTQ data block technology is used to improve the reading speed of large data files. Combined with the block information of the DNA reading sequence, according to the size of the memory page and the size of the mapped space, calculate the position of the data of each block in the memory mapped space, and when to release and remap the memory mapped space. An obvious benefit of using memory mapping is that the process can directly read and write the memory, basically without any additional data copying. For file I/O like fread/fwrite, it needs to be stored between the kernel space and the user space. Four data copies are performed in between, while memory mapping only needs two copies: one is copied from the input file to the memory-mapped area, and the other is copied from the memory-mapped area to the output file. In fact, processes can operate on ordinary files like accessing memory. A detailed description of this technique is provided in the specific implementation section.

In the compressed data writing thread, the order in which each block is compressed and written to the final compressed file needs to be the same as the reading order of the original data blocks in the original data reading thread. Here, a two-dimensional array of read and write order is used. The first dimension of the two-dimensional array represents the block number; the size of the second dimension is 2, which records the thread number assigned to each block and the compression processing completion flag information respectively.

The compressed file obtained by each process starts with a file header, which contains setting information, such as the number of records contained in the block. Immediately following is the compressed data of each block in the order of the original data block. At the end of the file is the file tail data, which contains the position index information of the compressed data of each block in the file, the number of blocks, and the position information of the file tail in the entire file. This information is used for parallel decoding and for random access to specific blocks to decode only part of the data without decoding the entire file.

A method for parallel decompression of DNA reading sequence data FASTQ files, comprising the following steps:

1. Determine the compressed file processed by the process according to the process number

The FASTQ file to be compressed will obtain a corresponding number of compressed files according to the number of parallel compression processes set. In decompression, the number of parallel decompression processes is set according to the number of compressed files, and the sequence of decompressed files obtained by each decompression process is determined by the sequence of compressed files. Each decompression process does not consume communication time with each other during processing, which improves the parallel processing efficiency of data.

2. Read the end of the compressed file to obtain information such as block settings, block index and block number

The difference from the parallel compression method is that the parallel decompression method initially obtains the setting of the number of records contained in the block, the position of each block in the compressed file, the number of blocks and other information from the end of the compressed file at the beginning of each process. The information distinguishes the parallel decompression method from the parallel compression method.

3. Parallel decompression in-process multi-thread pipeline parallel decompression

Similar to the parallel compression method, the decompression process processing module of the parallel decompression method includes a compressed data read thread, a decompressed data write thread and a plurality of decompression worker threads. The specific number of worker threads can be determined according to the hardware CPU. Set the number of cores and process settings.

Each decompression worker thread has two circular double buffer queues, one is the compressed data circular double buffer queue, and the other is the decompressed data circular double buffer queue. The compressed data circular double-buffer queue and the decompressed data circular double-buffer queue have similar structures, and the structure of the buffer is slightly different according to the stored data. The structure of each buffer will be described in detail later in the specific implementation section. Each compressed data circular double buffer queue contains two queues: one is an empty block buffer queue, and the other is a compressed data block queue. Each decompressed data circular double buffer queue also includes two queues: one is an empty block buffer queue, and the other is a decompressed data block queue. The processing methods of the two circular double buffer queues are the same as the original data circular double buffer queue processing methods in the aforementioned parallel compression method, and will not be repeated here.

In each process, the parallel decompression pipeline processing of the data in units of read sequence data compression blocks is performed. The specific parallel pipeline processing flow is as follows:

(1) The compressed data reading thread continuously reads the compressed blocks with known compression sizes according to the position index information of the compressed blocks obtained at the end of the file, in order of block numbers from small to large, and searches for each decompression worker thread in turn in a loop The empty block buffer at the head of the compressed data circular double buffer queue, put the compressed block data into it after finding it, and release this buffer to the end of the compressed data block queue in this circular double buffer queue.

(2) Each decompression worker thread continuously obtains the compressed data block from the head of the compressed data block queue in the compressed data circular double buffer queue of this thread, and then performs decompression processing.

(3) Each decompression worker thread continuously fills the decompressed block data into the empty block buffer in the obtained thread's decompressed data circular double buffer queue, and releases this buffer to this circular double buffer The decompressed block queue tail of the queue.

(4) The decompressed data writing thread continuously searches for the thread number of the block data that has been compressed and processed in sequence according to the block number from small to large, and obtains the decompressed data in this thread and the decompressed data in the circular double buffer queue This block at the head of the block queue decompresses the data, writing the final compressed file.

For the specific algorithms and end conditions of the above-mentioned threads, refer to the specific implementation mode for details.

The compressed data reading thread uses circular dual memory mapping technology combined with data block technology to improve the reading speed of large data files. The key technology is the circular dual memory mapping technology, which enables the decompression worker thread to read the compressed data for decompression and the memory mapping of the compressed data reading thread to execute in parallel. That is to say, there are two memory maps——memory map 1 and memory map 2, which are circularly put into these two memory maps in the order of compressed blocks. According to the compressed block data location index information at the end of the compressed file, and the size of the two memory-mapped spaces, the memory-mapped buffer where each compressed block data is located and the memory-mapped buffer in which each compressed block data is located are calculated sequentially in the order of the block numbers from small to large location information. The decompression worker thread directly uses this circular double memory-mapped area in the compressed data circular double buffer queue to reduce the number of data copies. For the memory mapping in use, it is necessary to wait for the previous mapping data of this memory mapping to be used by all decompression worker threads before performing memory mapping again. A detailed description of this technique is found in the Detailed Description section.

In the decompressed data writing thread, the order in which each block is decompressed and written to the final decompressed file needs to be the same as the reading order of the compressed blocks in the compressed data reading thread. Same as the parallel compression method, a two-dimensional array with the same reading and writing sequence is also used here to record the thread number assigned to each block and the decompression completion flag information.

In order to improve the I/O speed, the decompressed data writing thread also uses memory mapping combined with data block technology to create a memory-mapped file of a specific size according to the number of blocks to be decompressed, and decompresses the data in order of block numbers from small to large. Blocks are put into the memory mapping space in turn, and remapping needs to be performed according to the location of the written data, the size of the memory mapping space, and the remapping threshold, and the remapping threshold should be adjusted. See the specific implementation section for details.

For the compression and decompression of FASTQ files of DNA reading sequence data, the block index serial algorithms such as G_SQZ and DSRC have made important progress in recent years. At present, there are no research articles and patents on parallel algorithms related to this type of algorithm. As the data of genome sequence analysis reaches terabytes or even petabytes, in order to facilitate real-time analysis of a large amount of genome sequence data, it is necessary to perform real-time data compression and decompression, which requires the powerful computing power of high-performance computing platforms. Therefore, it is of great significance to study the parallel compression and decompression methods of the block index serial algorithms such as G_SQZ and DSRC mentioned above.

The present invention proposes for the first time the parallel compression and parallel decompression methods corresponding to the block index serial compression decompression algorithms such as G_SQZ and DSRC. Using circular double buffer queue, circular double memory mapping and memory mapping combined with data block processing, multi-thread pipeline parallel compression and decompression processing, two-dimensional array of read and write sequences, etc., to realize multiple processes of FASTQ files and multiple processes within a process Parallel compression and parallel decompression processing between threads.

The advantages of the present invention are:

(1) The present invention makes full use of the powerful computing capabilities of each computing node and the multi-core CPU in the node, and can solve the limitations of resources such as processors and memory for serial compression and decompression programs. The parallel compression and parallel decompression method can be implemented flexibly, and can be implemented based on MPI and OpenMP, and can also be implemented based on MPI and Pthread.

(2) Since the present invention is applicable to compression and decompression algorithms in any data block, the parallel compression and parallel decompression method is not limited to the parallelization of the two serial algorithms G_SQZ and DSRC, as long as the serial compression and decompression The compression algorithm has two characteristics of block and index, and the parallel compression and parallel decompression method is suitable for the parallelization of such block index serial algorithm.

(3) The present invention makes full use of the powerful computing power of the high-performance computing platform, can greatly increase the speed of real-time analysis and processing of massive genome sequences, and provides an important technical basis for the wider application of genetic data.

Description of drawings

Fig. 1 is a parallel compression diagram of multi-thread pipeline in process in the parallel compression method of the present invention;

Fig. 2 is original data circular double buffer queue figure among the present invention;

Fig. 3 is compressed data block buffer in parallel compression method of the present invention;

Fig. 4 is the in-process multi-thread pipeline parallel decompression diagram in the parallel decompression method of the present invention;

Fig. 5 is a diagram of the relationship between cyclic double memory mapping and compressed data block buffer in the parallel decompression method of the present invention;

Fig. 6 is the cooperation between the reading thread and the decompression worker thread in the circular dual memory mapping in the parallel decompression method of the present invention;

In the figure 1. Memory mapping 1, 2. Memory mapping 2, 3. Time axis, 4. Memory mapping area pointer, 5. Block starting point in memory mapping area, 6. Compressed data block length, 7. Compressed data block number.

Detailed ways

The present invention provides a method for parallel compression and decompression of FASTQ files of DNA reading sequence data. In order to make the purpose, technical solution and effect of the present invention clearer and clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

The raw data reading thread in the parallel compression method of the FASTQ file is explained in detail below, and its specific implementation steps are as follows:

(1) Open the FASTQ compressed file of the raw DNA read sequence data to be compressed.

(2) Obtain the memory paging size of the file system of the currently running machine.

(3) Set the memory mapping space size according to the memory paging size.

(4) According to the range of raw data that the current process needs to process allocated by the process task segmentation module, set the starting point of the memory mapping (the starting point needs to be aligned with the boundary of the memory page according to the size of the memory page) and the size of the mapped data, and carry out memory mapping.

(5) Record the starting position of the memory map of the first original data compression block in the process.

(6) Circularly search the original data circular double buffer queues of each compression worker thread in turn, and search for empty block buffers.

(7) If there is an empty fast buffer, go to (8), otherwise go to (6).

(8) From the memory mapping area, with the record as the granularity, read a certain number of record data in a cyclic order to form an original data block, fill the empty block buffer, add 1 to the block number, and store the number of records in the block. Or go to (9) when reaching the end of the map.

(9) Release this buffer to the end of the original data block queue of this circular double buffer queue.

(10) Set the thread allocation number of this block in the read-write sequence two-dimensional array.

(11) If the data end of the process assignment task is currently reached, go to (15), otherwise, go to (12).

(12) Calculate the length of the read original data block according to the end position of the currently read memory map, and set the start position of the next block to be read in the memory map area.

(13) If (the length of the current memory map reading position and the end position of this mapping is less than 1.5 times the length of the block just read) && (the end position of the file is not reached), go to (14), otherwise ( 8).

(14) Release the previous memory mapping, calculate the starting point and mapping size of the next memory mapping according to the current file reading position (the starting point of the next block to be read), and perform memory mapping again. turn (8).

(15) Release the memory map and set the read thread end flag.

(16) The original data reading thread ends.

The original data block buffer in the original data circular double buffer queue used in the above steps is shown in FIG. 3 . This buffer is implemented using a structure, which contains three fields - block data pointer, block number and the number of records in the block. The block data pointer points to a record array, and each array element points to a record object. This record object contains FASTQ four All data of partial information (title part, DNA sequence part, "+" part, Quality Score part) are: title part - title data pointer, title data length, title reserved space length, where the title data pointer points to title Data buffer; DNA sequence part - sequence data pointer, sequence data length, sequence reserved space length, where the sequence data pointer points to the sequence data buffer; "+" part - plus data pointer, plus data length, plus reserved space Space length, where the plus data pointer points to the plus data buffer; the Quality Score part—Quality data pointer, Quality data length, and Quality reserved space length, where the Quality data pointer points to the Quality data buffer; DNA sequence data truncation information—— sequence truncation information vector and quality truncation information vector

The following explains in detail the compression worker threads in the parallel compression method of FASTQ files, and its specific implementation steps are as follows:

(1) Compress the preparatory work of the working thread, including the creation and initialization of objects in the thread.

(2) Obtain the head of the queue from the original data block queue of the original data circular double buffer queue.

(3) If the obtained queue head is empty, go to (2), otherwise go to (4).

(4) Compress the original data block in the queue head buffer, store the compressed data in the temporary buffer in the thread, and record the compressed block data size.

(5) Release this buffer to the empty block buffer queue in this circular double buffer queue.

(6) Obtain the head of the queue from the empty block buffer queue of the compressed data circular double buffer queue.

(7) If the obtained queue head is empty, go to (6), otherwise go to (8).

(8) Store the compressed block data cached in the temporary buffer in the thread into the empty block buffer in the queue head, and record the compressed data size and block number.

(9) Release this buffer to the end of the compressed data block queue in this circular double buffer queue.

(10) Set the compression processing completion flag of this block in the read-write sequence two-dimensional array.

(11) If the original data reading thread ends and all blocks are processed, go to (13), otherwise go to (2).

(12) If the compressed data writing thread ends, go to (13), otherwise go to (2).

(13) Set the end flag of this compression worker thread.

(14) This compression worker thread ends.

It should be noted that, the buffer data of each original data block in the above step (4) can be compressed by using DSRC algorithm, G_SQZ algorithm and other block indexing algorithms according to requirements.

The compressed data block buffer in the compressed data circular double buffer queue used in the above steps is implemented using a structure, which contains four fields - compressed data block pointer, compressed data block length, compressed data block number and number of records in the block , where the compressed data block pointer points to a data buffer.

The compressed data writing thread in the parallel compression method of the FASTQ file is explained in detail below, and its specific implementation steps are as follows:

(1) Compressed data writing thread preparation work, including the setting information of the number of records contained in the block data written in the header of the compressed file.

(2) Set the block number block_no=0.

(3) Find the block compression processing flag of the two-dimensional array block_no in the read-write sequence.

(4) If block_no is compressed, go to (5), otherwise go to (3).

(5) Obtain the head of the queue from the compressed data block queue of the compressed data circular double buffer queue.

(6) If the queue head is empty, go to (5), otherwise go to (7).

(7) Write the compressed data block at the head of the queue into the final compressed file.

(8) Release this buffer to the end of the empty block buffer queue in this circular double buffer queue.

(9) block_no plus 1

(10) If the original data reading thread ends and all blocks have been written into the final compressed file, go to (11), otherwise go to (3).

(11) At the end of the compressed file, write the position index of the compressed bit stream of each block in the compressed file, the total number of blocks, the starting position of the end of the file, and other compressed file tail information.

(12) Set the compressed data write thread end flag.

(13) The compressed data write thread ends.

The compressed data reading thread in the parallel decompression method of the FASTQ file is explained in detail below, and its specific implementation steps are as follows:

(1) Open the compressed file allocated by the process to be decompressed, and obtain file descriptor 1, namely fd1.

(2) Open the compressed file to be decompressed allocated by the process again, and obtain file descriptor 2, namely fd2.

(3) Obtain the memory page size of the file system of the currently running machine.

(4) Set the memory mapping space size according to the memory paging size.

(5) According to the position index information of the compressed bit stream of each block at the end of the compressed file, the start position and end position of all the blocks to be decompressed in the process in the compressed bit stream are obtained.

(6) According to the above starting position, set the starting point of the memory mapping (the starting point needs to be aligned with the boundary of the memory page according to the size of the memory page), the size of the mapped data, and the end point of the memory mapping, and map the memory mapping of fd1 to obtain the memory mapping Memory address lpBuf1 of area 1. The current mapping start point and end point are calculated relative to the entire compressed file.

(7) Set the current memory mapping area number current_buffer_symbol to 1.

(8) Initialize the variable reverse_num of memory mapping area conversion times to 0; initialize the start block number variable and end block number variable of the current memory map area current_lpbuffer to 0, initialize the start block number variable and end block number variable of the previous memory map area last_lpbuffer The block number variables are all 0.

(9) Set the block number of the current block to be decompressed = 0.

(10) Retrieve the position index information of the compressed bit stream, and obtain the start position and end position of the current block to be decompressed in the compressed file.

(11) If the start position and end position of the current block to be decompressed are within the range of the current mapping area, go to (20); otherwise, go to (12).

(12) Variable reverse_num+1 for memory mapping area conversion times.

(13) Assign the starting block number value of the current memory mapping area to the starting block number variable of the previous memory mapping area, and assign the current block number value to the starting block number variable of the current memory mapping area, (current block number value - 1) Assign a value to the termination block number variable of the previous memory mapping area.

(14) According to the starting position of the current block to be decompressed in the compressed file, set the starting point of the memory map (the starting point needs to be aligned with the boundary of the memory page according to the size of the memory page), the size of the mapped data, and the end point of the memory map. The current mapping start point and end point are calculated relative to the entire compressed file.

(15) Change the current memory mapping area number, that is, two mapping rotations: if current_buffer_symbol is 1, change to 2; if current_buffer_symbol is 2, change to 1.

(16) If reverse_num>=2, then go to (17), otherwise go to (19)

(17) According to the start block number and end block number recorded in the previous memory mapping area, continuously query the decompression processing end flag of the corresponding block in the read-write sequence two-dimensional array until all blocks in the range are decompressed Finish. turn (18).

(18) If current_buffer_symbol=1, release memory mapping 1; otherwise, release memory mapping 2.

(19) If current_buffer_symbol=1, perform memory mapping 1 on fd1 again to obtain memory mapping address lpbuf1, otherwise perform memory mapping 2 on fd2 to obtain memory mapping address lpbuf2. The memory mapping parameters re-performed above are all parameters calculated in (14).

(20) Circularly search the compressed data circular double buffer queues of each decompression worker thread in turn, and search for empty block buffers.

(21) If the empty block buffer exists, go to (22), otherwise go to (20).

(22) According to the current_buffer_symbol, the mapping start point of the current memory mapping area, the start position and the end position of the current block to be decompressed, set the four fields in the empty block buffer structure in the currently obtained compressed data circular double buffer queue: block A compressed data block buffer is formed at the starting point of the memory mapping area, the pointer of the memory mapping area, the length of the compressed data block, and the number of the compressed data block.

(23) Release this buffer to the end of the compressed data block queue of this circular double buffer queue.

(24) Set the thread allocation number of this block in the read-write sequence two-dimensional array.

(25) Add one to the block number of the current block to be decompressed, if the block number of the current block to be decompressed > the maximum block number to be decompressed by the process, go to (26), otherwise go to (10).

(26) Wait for the writing thread to end, if not, keep waiting; if the writing thread ends, release memory mapping 1 and memory mapping 2, and close fd1 and fd2.

(27) Set the compressed data reading thread end flag.

(28) The compressed data reading thread ends.

The compressed data block buffer in the compressed data circular double-buffer queue used in the above steps is implemented using a structure, which contains four fields—the memory mapping area pointer (4), the starting point of the block in the memory mapping area (5), Compressed data block length (6) and compressed data block number (7). In order to save space and time for multiple data copies, pointers are directly used to point to the memory mapping area where the compressed data block is located and the starting point of the block in the memory mapping area.

Fig. 5 shows the relationship diagram of the circular dual memory mapping and the compressed data block buffer in the parallel decompression method. Taking block 1 as an example in the figure, it shows the relationship between each field of the buffer and the dual memory-mapped areas—memory map (1) and memory map (2). It can be seen that the decompression worker thread directly uses the circular double memory mapping area in the compressed data circular double buffer queue, which reduces the number of data copies. It should be noted that the starting point and ending point of each memory mapping may not be at the beginning and ending position of the block. This is because the starting point needs to align the boundary of the memory page according to the size of the memory page. The space size of the memory mapping is except for the last Except for the mapping size affected by the end of the file, the rest of the mapping size is a fixed value. Some blocks contain only part of the data in one memory map. Such blocks need to remap the entire block of data in another memory map.

The decompression worker thread in the parallel decompression method of the FASTQ file is explained in detail below, and its specific implementation steps are as follows:

(1) Preparatory work for the decompression working thread, including the setting information of the number of block records obtained by processing the header and tail of the compressed file at the beginning of the thread acquisition process, the number of compressed blocks contained in the compressed file, and the position index of each block in the compressed file and other information, as well as the creation and initialization of some objects in this thread.

(2) Obtain the queue head from the compressed data block queue of the compressed data circular double buffer queue.

(3) If the obtained queue head is empty, go to (2), otherwise go to (4).

(4) Read the data of the four fields in the queue head buffer structure - the starting point of the block in the memory mapping area, the pointer of the memory mapping area, the length of the compressed data block, the number of the compressed data block, and decompress the compression bit of this block Stream, store the decompressed data in a specific block record structure object in the thread.

(5) Release this buffer to the empty block buffer queue in this circular double buffer queue.

(6) Obtain the head of the queue from the empty block buffer queue of the decompressed data circular double buffer queue.

(7) If the obtained queue head is empty, go to (6), otherwise go to (8).

(8) The decompressed block data cached in the block record structure object in the thread is stored in the empty block buffer in the queue head, and the length and block number of the decompressed data block are recorded.

(9) Release this buffer to the tail of the decompressed data block queue in this circular double buffer queue.

(10) Set the decompression processing completion flag of this block in the read-write sequence two-dimensional array.

(11) Retrieve the two-dimensional array of read-write sequence, if all blocks are decompressed and processed, go to (13), otherwise go to (2).

(12) If the decompressed data writing thread ends, go to (13), otherwise go to (2).

(13) Set the decompression worker thread end flag.

(14) This decompression worker thread ends.

It should be noted that the buffer data of each compressed block in the above step (4) can be decompressed according to the compression algorithm, using such block index algorithms as DSRC algorithm and G_SQZ algorithm.

The decompressed data block buffer in the decompressed data circular double buffer queue used in the above steps is implemented using a structure, which contains three fields - decompressed data block pointer, decompressed data block length and decompressed data block number, Wherein the decompressed data block pointer points to a buffer.

Fig. 6 shows the synergy between the read thread and the decompression worker thread in the parallel decompression method of cyclic dual memory mapping - memory mapping 1 (1) and memory mapping 2 (2), the time axis is (3), the block setting Same as Figure 5. It can be seen from the figure that when memory map 1 (1) is used for remapping for the second time, it is necessary to wait for all decompression worker threads to finish processing all block data in the original memory map 1 (1), that is, to wait for block 0 to block After i is processed, the last mapping can be released, and the data from block j+1 to block k can be remapped. The same situation also occurs when memory mapping 2 (2) is used for the second time to re-memory-map a new compressed block, and it is necessary to wait for all decompression threads to finish processing block i+1 to block j+1.

The decompressed data writing thread in the parallel decompression method of the FASTQ file is explained in detail below, and its specific implementation steps are as follows:

(1) Decompression data writing thread preparation work, including determination of decompression file name.

(2) Obtain the memory paging size of the file system of the currently running machine.

(3) Set the size of the memory-mapped file qwFileSize according to the number of blocks to be decompressed. According to the size of memory paging, set the size of each memory mapping area and the threshold for re-mapping memory.

(4) Create the decompressed file, get the file descriptor fd, and set the space occupied by the file to the size of qwFileSize.

(5) Calculate the size of this memory mapping, perform memory mapping on fd, and obtain the memory space address lpBuf of the memory mapping.

(6) Set block number block_no=0.

(7) Find the decompression processing flag of block_no number in the two-dimensional array of read-write sequence.

(8) If block_no is decompressed, go to (9), otherwise go to (7).

(9) Obtain the queue head from the decompressed data block queue of the decompressed data circular double buffer queue.

(10) If the queue head is empty, go to (9), otherwise go to (11).

(11) Write the decompressed data block at the head of the queue into the memory-mapped area, and the data offset of the memory-mapped area and the offset of the file data will increase accordingly according to the size of the written data.

(12) Release this buffer to the end of the empty block buffer queue in this circular double buffer queue.

(13) If the data written in the current memory mapping area reaches the threshold, release the memory mapping. And according to the offset and file size of the current file data, calculate the starting point of the memory map, the map size, the data offset of the memory map area, and the new threshold, and re-map the memory.

(14) block_no plus 1.

(15) If all blocks have been written into the memory mapping area, go to (16), otherwise go to (7).

(16) Release the memory map, write the decompressed data into the final decompressed file, and close the file descriptor.

(17) Set the decompressed data write thread end flag.

(18) The decompressed data write thread ends.

Claims (6)

1. a DNA reading sequence data FASTQ file parallel compression method is characterized in that comprising parallel compression process task segmentation part and compression process processing part, specifically as follows: (1) Parallel compression process task division part According to the size of the FASTQ file, the number of parallel compression processes, each reading segment in the FASTQ file - the data characteristics of each record, determine the start and end positions of the data to be processed in each compression process; each process will compress the original The data is approximately evenly distributed to each process to achieve data parallelism, so that each process does not consume communication time with each other during processing, which improves the processing efficiency of data parallelism; each process obtains a separate compressed file, compressed data The sequence is consistent with the process number; (2) The compression process processing part is responsible for multi-thread pipeline parallel compression in the process Each compression process processing part includes a raw data reading thread, a compressed data writing thread and multiple compression working threads; the specific number of working threads can be set according to the number of hardware CPU cores and process settings; The data to be compressed processed by each process is divided into multiple blocks by the original data reading thread, each block contains a specific fixed number of records, and the last block is less than the fixed number; Each worker thread has two circular double buffer queues, one is the original data circular double buffer queue, and the other is the compressed data circular double buffer queue; each original data circular double buffer queue contains two queues: one is the empty block buffer Area queue, one is the original data block queue; each compressed data circular double buffer queue also contains two queues: one is the empty block buffer queue, and the other is the compressed data block queue; In each process, the parallel compression pipeline processing of the data in the unit of the original data block is carried out. The specific pipeline parallel processing flow is as follows: (1) The original data reading thread continuously parses and reads the original data block according to the characteristics of the recorded data, loops to find the empty block buffer in the original data circular double buffer queue of each compression worker thread in turn, and puts the original data block in the input, and then release this block buffer to the end of the original data block queue in this circular double buffer queue; The original data reading thread uses memory mapping combined with data block technology; (2) Each compression worker thread continuously obtains the original data block from the head of the original data block queue in the original data circular double buffer queue of this thread, and then performs compression processing; (3) Each compression worker thread continuously fills the compressed block data into the empty block buffer in the obtained compressed data circular double buffer queue of this thread, and releases this buffer to the compression of this circular double buffer queue the tail of the data block queue; (4) The compressed data writing thread continuously searches for the thread number of the block data that has been compressed and processed in sequence according to the block number from small to large, and obtains the compressed data block queue head in the compressed data circular double buffer queue in this thread This block in compressed data is written to the final compressed file. 2. DNA reading sequence data FASTQ file parallel compression method according to claim 1, is characterized in that: described original data circular double-buffer queue processing mode is as follows: (1) Original data circular double buffer queue initialization processing: instantiate the empty block buffer queue, with a specific number of empty block buffers, and the original data block queue is empty; (2) The raw data reading thread reads a raw data block; (3) Obtain an empty block buffer at the head of the empty block buffer queue; (4) Fill the obtained empty block buffer with the original data block; (5) Put this padded raw data block at the end of the raw data block queue; (6) The compression worker thread obtains the block data in an original data block buffer from the head of the original data block queue for compression processing; (7) Clear the original data block buffer and put it into the empty block buffer queue. 3. DNA sequence data FASTQ file parallel compression method according to claim 1, is characterized in that: the memory mapping that described raw data reading thread adopts combines data block technology, is used for improving the reading speed of large file, Combined with data partitioning, it is mainly based on the size of the memory page and the size of the mapped space to calculate the position of the data of each block in the memory mapped space, and when to release and remap the memory mapped space. 4. A parallel decompression method for DNA reading sequence data FASTQ files, characterized in that it comprises the following parts: (1) Determine the compressed files to be processed by the parallel decompression process according to the process number The FASTQ file to be compressed obtains the corresponding number of compressed files according to the number of parallel compression processes set; in parallel decompression, the number of parallel decompression processes is set according to the number of compressed files, and the sequence of decompressed files obtained by each decompression process It is determined by the order of compressed files; each decompression process does not consume communication time with each other during processing, which improves the processing efficiency of data parallelism; (2) Read the end of the compressed file to obtain block settings, block index and block number information At the beginning of each process, the setting of the number of records contained in the block, the position index of each block in the compressed file, and the number of blocks are obtained from the end of the compressed file; (3) Multi-thread pipeline parallel decompression in parallel decompression process Each parallel decompression process includes a compressed data read thread, a decompressed data write thread and multiple decompression worker threads; Each decompression worker thread has two circular double buffer queues, one is the compressed data circular double buffer queue, and the other is the decompressed data circular double buffer queue; each compressed data circular double buffer queue contains two queues: one is an empty block The buffer queue, the other is the compressed data block queue; each decompressed data circular double buffer queue also contains two queues: one is the empty block buffer queue, and the other is the decompressed data block queue; In each process, the parallel decompression pipeline processing of the data in units of compressed blocks is performed. The specific parallel pipeline processing flow is as follows: (1) The compressed data reading thread continuously reads the compressed blocks with known compression sizes according to the position index information of the compressed blocks obtained at the end of the compressed file, in order of block numbers from small to large, and searches for each decompression job in turn in a loop The compressed data of the thread is found in the empty block buffer at the head of the circular double-buffer queue. After finding it, put the compressed block data into it, and release this buffer to the end of the compressed data block queue in the circular double-buffer queue; The compressed data reading thread adopts circular dual memory mapping combined with data block technology; (2) Each decompression worker thread continuously obtains compressed data blocks from the head of the compressed data block queue in the compressed data circular double buffer queue of this thread, and then performs decompression processing; (3) Each decompression worker thread continuously fills the decompressed block data into the empty block buffer in the obtained thread's decompressed data circular double buffer queue, and releases this buffer to this circular double buffer The decompressed data block queue tail of the queue; (4) The decompressed data writing thread continuously searches for the thread number of the block data that has been compressed and processed in sequence according to the block number from small to large, and obtains the decompressed data in this thread and the decompressed data in the circular double buffer queue This block at the head of the block queue decompresses the data, writing the final compressed file. 5. the method for parallel decompression of DNA sequence data FASTQ files according to claim 4, characterized in that: the compressed data block buffer in the compressed data circular double buffer queue is implemented using a structure, comprising four fields— —Memory mapping area pointer, starting point of block in memory mapping area, length of compressed data block and number of compressed data block; in order to save space and time for multiple copying of data, directly use the pointer to point to the memory mapping area where the compressed data block is located and where the block is located The starting point of the memory mapped region. 6. The method for parallel decompression of DNA sequence data FASTQ files according to claim 4, characterized in that: the cyclic double memory mapping technology adopted by the compressed data reading thread is combined with data block technology to improve the performance of large data files. The reading speed of , the specific implementation is as follows: The key technology is the circular dual memory mapping technology, which enables the decompression worker thread to read the compressed data for decompression and the memory mapping of the compressed data reading thread to execute in parallel, that is, there are two memory maps——memory map 1 and memory map 2, according to The order of the compressed blocks is put into these two memory maps in turn; according to the compressed block data position index information at the end of the compressed file, and the size of the two memory map spaces, each compressed block is calculated sequentially in the order of block numbers from small to large. The memory-mapped buffer where the block data is located and the location information in the memory-mapped buffer; the decompression worker thread directly uses this circular double-memory-mapped area in the compressed data circular double-buffer queue to reduce the number of data copies; For memory mapping, it is necessary to wait for the previous mapping data of this memory mapping to be used by all decompression worker threads before performing memory mapping again.

Images