基于CPU-MIC協(xié)同的DNA序列分析關(guān)鍵算法并行技術(shù)研究.pdf

1、DNA序列分析是從分子層面對生命現(xiàn)象的規(guī)律進(jìn)行探究和認(rèn)識(shí)，是進(jìn)一步研究和改造生物性狀的基礎(chǔ)。DNA二三代測序技術(shù)的迅猛發(fā)展引起測序數(shù)據(jù)規(guī)模的爆炸式增長，其增長速度已遠(yuǎn)遠(yuǎn)超越了摩爾定律。導(dǎo)致現(xiàn)有服務(wù)器以及序列分析算法已經(jīng)無法及時(shí)有效地處理如此大規(guī)模的DNA大數(shù)據(jù)。本課題即是針對上述問題，選取了DNA序列分析中三個(gè)目前使用較廣泛的關(guān)鍵算法，這其中既包括短序列分析算法（SOAPsnp、BWA），又包括長序列分析算法（MC3），并結(jié)合天河2號(hào)的

2、大規(guī)模CPU-MIC微異構(gòu)體系結(jié)構(gòu)進(jìn)行了并行技術(shù)的研究，在保證算法精確度的前提下，設(shè)計(jì)了三種 CPU-MIC協(xié)同的新型并行算法，以提高這三鐘典型 DNA序列分析算法的時(shí)空效率。主要包括以下三個(gè)方面的工作：
　　1. SOAPsnp是一款在國內(nèi)外具有較大影響力的SNP檢測軟件，它基于貝葉斯概率模型，具有精度高、使用廣泛的特點(diǎn)。該軟件核心算法存在計(jì)算冗余，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)也較為復(fù)雜，導(dǎo)致程序執(zhí)行效率不高。針對以上問題，本文對算法和數(shù)據(jù)結(jié)構(gòu)

3、進(jìn)行了重新設(shè)計(jì)，提出了四維矩陣壓縮降維、基于快表的去冗計(jì)算、和一致性梯度排序等一系列優(yōu)化策略，將算法復(fù)雜度從O(n5)降低到O(n)，并設(shè)計(jì)實(shí)現(xiàn)了面向天河2號(hào)的CPU-MIC微異構(gòu)協(xié)同大規(guī)模并行算法。并在天河2號(hào)上進(jìn)行了實(shí)測，單節(jié)點(diǎn)獲得了50倍以上加速比，并行效率達(dá)到73.6％以上，多節(jié)點(diǎn)（512個(gè)計(jì)算節(jié)點(diǎn)，12,288 CPU核心+86,016 MIC核心）獲得了483.6倍的并行加速比和近線性可擴(kuò)展性。將原來需要一周處理完成的人類D

4、NA基因組大數(shù)據(jù)（6TB）在一小時(shí)內(nèi)處理完畢。
　　2. BWA是目前廣泛使用的一種DNA短序列比對工具，它采用基于FM索引的后向搜索方法并支持堿基錯(cuò)配。針對目前BWA在處理大規(guī)模短序列時(shí)，比對速度慢，時(shí)空效率低的問題，本文設(shè)計(jì)實(shí)現(xiàn)了一種基于三級流水的CPU-MIC微異構(gòu)協(xié)同并行比對算法，該算法不但隱藏了數(shù)據(jù)I/O時(shí)間，而且實(shí)現(xiàn)了面向天河2號(hào)的CPU-MIC微異構(gòu)協(xié)同并行序列比對，并在天河2號(hào)上實(shí)現(xiàn)了跨節(jié)點(diǎn)的大規(guī)模并行實(shí)驗(yàn)測試，最

5、大測試規(guī)模達(dá)到2,048個(gè)計(jì)算節(jié)點(diǎn)，共使用49,152 CPU核心和344,064 MIC核心，并行效率保持在63.4%以上，獲得了良好的可擴(kuò)展性。
　　3. MrBayes主要用于系統(tǒng)發(fā)育推斷，廣泛應(yīng)用于系統(tǒng)發(fā)育學(xué)和生物進(jìn)化學(xué)模型中。但現(xiàn)有MrBayes MC3并行算法計(jì)算復(fù)雜、迭代次數(shù)多，并行規(guī)模受限于馬爾克夫鏈的數(shù)量。針對以上問題，本文提出了系統(tǒng)發(fā)育樹同構(gòu)分割并行構(gòu)建策略，將一棵發(fā)育樹分割為多棵拓?fù)浣Y(jié)構(gòu)相同的子樹，實(shí)現(xiàn)了馬爾