本文選題：多核 + OpenMP�。� 參考：《黑龍江大學(xué)》2015年碩士論文

【摘要】：隨著大數(shù)據(jù)時(shí)代的到來,如何提高計(jì)算效率已經(jīng)成為焦點(diǎn)問題。隨著生物數(shù)據(jù)庫信息的日益增多,需要對原有的串行計(jì)算模式進(jìn)行改變。同時(shí)提高主頻和淘汰單核心的多核心結(jié)構(gòu)成為并行計(jì)算的主流。不同于GPU特殊的硬件要求,多核結(jié)構(gòu)在數(shù)據(jù)傳輸、可移植性能上和發(fā)展前景上都具有優(yōu)勢,所以本文選擇在多核平臺上使用Open MP語言對廣泛使用的BLASTN進(jìn)行并行計(jì)算的研究,同時(shí)使用基于Trie樹的預(yù)處理機(jī)制和調(diào)度分配算法更好的減少時(shí)間花銷。首先,本文提出基于Trie樹的預(yù)處理算法,主要思想是利用Trie樹過濾完全相同的字組,對數(shù)據(jù)庫進(jìn)行簡化處理,減少BLASTN算法中匹配的次數(shù)。預(yù)處理機(jī)制包括將原數(shù)據(jù)庫分割成多個(gè)小數(shù)據(jù)庫,將數(shù)據(jù)庫中的目標(biāo)序列劃分成長度為W的字組哈希表,建立Trie樹存儲相同的字組。實(shí)驗(yàn)表明,建立Trie樹的預(yù)處理機(jī)制在數(shù)據(jù)庫規(guī)模較小時(shí)反而不如數(shù)據(jù)庫規(guī)模較大時(shí)高效,但是對于優(yōu)化BLASTN的并行算法有一定的作用。其次,本文研究了BLASTN算法的串行程序,分析其并行化可行性,使用Perf對BLASTN進(jìn)行熱點(diǎn)函數(shù)分析,對BLASTN進(jìn)行并行化改造。其并行BLASTN的思想主要在種子階段和延伸匹配階段,前者將查詢序列的字組劃分階段和查詢序列的字組與目標(biāo)序列字組比對得到高分字組(HSP)階段同時(shí)并行化,同時(shí),利用多個(gè)核心同時(shí)計(jì)算任務(wù)量;后者對延伸匹配階段實(shí)行左右同時(shí)進(jìn)行延伸匹配和合并HSP的位置搜索樹上連續(xù)相鄰的字組,減少重復(fù)匹配次數(shù),使并行改造后的BLASTN進(jìn)行加速。實(shí)驗(yàn)表明,最好的情況下,并行后的BLASTN算法的時(shí)間與原來相比減小接近一半,即加速比為2,但是隨著序列數(shù)據(jù)庫的增加,加速比曲線將會持續(xù)上升。最后,針對處理器上多核心的計(jì)算任務(wù)的分配調(diào)度提出了基于棧的周期性調(diào)度分配算法ZD,衡量任務(wù)量大小的基準(zhǔn)采用數(shù)據(jù)庫中序列的長度。實(shí)驗(yàn)表明,本調(diào)度算法在一般情況下對計(jì)算量均衡分配和調(diào)度,在最壞的情況下ZD算法與無調(diào)度算法效率相同,并不影響其正常運(yùn)行。
[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.
【學(xué)位授予單位】：黑龍江大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：Q811.4;TP311.13
，

本文編號：2118087