多核环境下的生物信息序列比对并行优化方法的研究

发布时间：2018-07-12 18:26

  本文选题：多核 + OpenMP　； 参考：《黑龙江大学》2015年硕士论文

【摘要】：随着大数据时代的到来,如何提高计算效率已经成为焦点问题。随着生物数据库信息的日益增多,需要对原有的串行计算模式进行改变。同时提高主频和淘汰单核心的多核心结构成为并行计算的主流。不同于GPU特殊的硬件要求,多核结构在数据传输、可移植性能上和发展前景上都具有优势,所以本文选择在多核平台上使用Open MP语言对广泛使用的BLASTN进行并行计算的研究,同时使用基于Trie树的预处理机制和调度分配算法更好的减少时间花销。首先,本文提出基于Trie树的预处理算法,主要思想是利用Trie树过滤完全相同的字组,对数据库进行简化处理,减少BLASTN算法中匹配的次数。预处理机制包括将原数据库分割成多个小数据库,将数据库中的目标序列划分成长度为W的字组哈希表,建立Trie树存储相同的字组。实验表明,建立Trie树的预处理机制在数据库规模较小时反而不如数据库规模较大时高效,但是对于优化BLASTN的并行算法有一定的作用。其次,本文研究了BLASTN算法的串行程序,分析其并行化可行性,使用Perf对BLASTN进行热点函数分析,对BLASTN进行并行化改造。其并行BLASTN的思想主要在种子阶段和延伸匹配阶段,前者将查询序列的字组划分阶段和查询序列的字组与目标序列字组比对得到高分字组(HSP)阶段同时并行化,同时,利用多个核心同时计算任务量;后者对延伸匹配阶段实行左右同时进行延伸匹配和合并HSP的位置搜索树上连续相邻的字组,减少重复匹配次数,使并行改造后的BLASTN进行加速。实验表明,最好的情况下,并行后的BLASTN算法的时间与原来相比减小接近一半,即加速比为2,但是随着序列数据库的增加,加速比曲线将会持续上升。最后,针对处理器上多核心的计算任务的分配调度提出了基于栈的周期性调度分配算法ZD,衡量任务量大小的基准采用数据库中序列的长度。实验表明,本调度算法在一般情况下对计算量均衡分配和调度,在最坏的情况下ZD算法与无调度算法效率相同,并不影响其正常运行。
[Abstract]:With the arrival of big data era, how to improve computing efficiency has become the focus. With the increasing of biological database information, the original serial computing mode needs to be changed. At the same time, improving the main frequency and eliminating the single core multi-core architecture has become the mainstream of parallel computing. Different from the special hardware requirements of GPU, multi-core architecture has advantages in data transmission, portability and development prospects, so this paper chooses to use Open MP language on multi-core platform to study the parallel computing of widely used BLASTN. At the same time, the preprocessing mechanism and scheduling allocation algorithm based on Trie tree are used to reduce the time cost better. Firstly, a preprocessing algorithm based on Trie tree is proposed. The main idea is to use Trie tree to filter exactly the same groups of words, simplify the database and reduce the number of matching in BLASTN algorithm. The preprocessing mechanism consists of dividing the original database into several small databases, dividing the target sequences of the database into word-group hash tables with growth degree W, and establishing the Trie tree to store the same word groups. The experimental results show that the preprocessing mechanism of Trie tree is less efficient than that of large database when the scale of database is small, but it is useful to optimize the parallel algorithm of BLASTN. Secondly, the serial program of BLASTN algorithm is studied, and the feasibility of parallelization is analyzed. The hot function analysis of BLASTN is carried out by using Perf, and the parallel transformation of BLASTN is carried out. The idea of parallel BLASTN is mainly in seed stage and extended matching stage. The former parallelizes the word group of the query sequence and the target sequence word group to get the high score word group (HSP) phase simultaneously, and at the same time, Multiple cores are used to calculate the amount of work simultaneously, and the latter carries out the extension matching at the same time and combines the positions of HSP to search the successive adjacent word groups in the tree, which reduces the number of repeated matching and accelerates the parallel transformation of BLASTN. The experiments show that the time of the parallel BLASTN algorithm is nearly half that of the original algorithm, that is, the speedup ratio is 2, but with the increase of the sequence database, the speedup curve will continue to rise. Finally, a stack based periodic scheduling algorithm, ZD, is proposed for multi-core computing task allocation on the processor. The length of the sequence in the database is used as the benchmark to measure the size of the task. The experimental results show that the proposed algorithm has the same efficiency as the unscheduled algorithm in the worst case, and does not affect its normal operation.
【学位授予单位】：黑龙江大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：Q811.4;TP311.13
，

本文编号：2118087