隨著測(cè)序技術(shù)的發(fā)展,基因序列的數(shù)量得到了迅猛的增長,為了有效地利用這些序列數(shù)據(jù),我們往往需要將它們與已知的基因組進(jìn)行比對(duì),從而獲取序列間的相似性以及同源性等信息,為后續(xù)的進(jìn)一步分析打下基礎(chǔ)。傳統(tǒng)的序列比對(duì)算法由于自身算法復(fù)雜度的限制,在處理海量序列的比對(duì)時(shí),往往難以達(dá)到期望的效果。近年來隨著硬件和軟件技術(shù)的發(fā)展,尤其是眾核架構(gòu)的出現(xiàn),高性能計(jì)算在自然語言處理、人工智能、計(jì)算生物學(xué)等領(lǐng)域發(fā)揮著越來越重要的作用。將高性能計(jì)算應(yīng)用于序列比對(duì),可以顯著地改善比對(duì)的速度,提高序列分析的效率。本文主要基于英特爾的多核和眾核平臺(tái),針對(duì)全局序列比對(duì)問題進(jìn)行研究,利用多核及眾核平臺(tái)的高速計(jì)算能力對(duì)全局序列比對(duì)算法進(jìn)行加速優(yōu)化,進(jìn)一步提升算法的性能。目前常用的全局序列比對(duì)算法是Needleman-Wunsch算法,在此算法的基礎(chǔ)上衍生出兩種基于位并行優(yōu)化的比對(duì)算法:Myers和BitPAl,它們?cè)诠δ苄陨献隽艘恍┫鳒p,以獲取更高的性能。我們主要從兩個(gè)維度對(duì)上述算法進(jìn)行了優(yōu)化:線程并行和SIMD并行,線程并行主要利用多線程技術(shù),將序列數(shù)據(jù)劃分為多個(gè)數(shù)據(jù)塊,每個(gè)線程并行地處理一塊數(shù)據(jù)。在線程內(nèi)部,我們利用SSE、AVX2、KNC和AVX512等SIMD指令進(jìn)行更加細(xì)粒度的并行優(yōu)化。為了提升系統(tǒng)的可擴(kuò)展性,我們?cè)O(shè)計(jì)并實(shí)現(xiàn)了一個(gè)模塊化的并行框架,我們將系統(tǒng)中的功能進(jìn)行拆分細(xì)化,劃分出多個(gè)獨(dú)立的功能性模塊,模塊間相互協(xié)作,共同完成指定的任務(wù)。比對(duì)算法的邏輯被抽象為一個(gè)計(jì)算模塊,其他的模塊只需向該模塊中傳入數(shù)據(jù),然后獲取對(duì)應(yīng)的計(jì)算結(jié)果,無需關(guān)心計(jì)算模塊的具體實(shí)現(xiàn),這樣如果需要往并行框架中加入新的比對(duì)算法,我們只需修改計(jì)算模塊的實(shí)現(xiàn),便可以復(fù)用框架的其他功能,保證了系統(tǒng)具有良好的擴(kuò)展性。同時(shí)為了解決SIMD指令集不統(tǒng)一的問題,我們?cè)O(shè)計(jì)了虛擬SIMD指令,并實(shí)現(xiàn)了對(duì)應(yīng)的指令解釋器,利用虛擬SIMD指令,我們只需維護(hù)一份代碼,通過虛擬指令解釋器,我們可以將其翻譯為針對(duì)不同指令集的代碼,可以極大地提高開發(fā)效率。我們?cè)诓煌钠脚_(tái)上對(duì)我們的并行算法做了測(cè)試,實(shí)驗(yàn)證明我們的并行算法取得了很好的加速效果,同時(shí)我們和其他的并行實(shí)現(xiàn)做了對(duì)比,我們的算法取得了更加優(yōu)異的性能。
【學(xué)位單位】：山東大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類】：Q811.4;TP38
【部分圖文】：

ＡＶＸ２、ＫＮＣ和ＡＶＸ５１２指令集優(yōu)化的算法。??３．１框架概述??圖３－１展示了并行框架的整體架構(gòu)圖，我們的并行框架大概分為以下幾個(gè)部??分：??？輸入模塊，用來讀取序列數(shù)據(jù)，解析數(shù)據(jù)格式，并轉(zhuǎn)換成預(yù)處理模塊需要??的中間數(shù)據(jù)結(jié)構(gòu)。??？預(yù)處理模塊，該模塊會(huì)對(duì)序列數(shù)據(jù)進(jìn)行進(jìn)一步的處理，生成更加適合并行??處理的數(shù)據(jù)結(jié)構(gòu)，以便在計(jì)算模塊中可以充分發(fā)揮硬件的計(jì)算能力。??？數(shù)據(jù)傳輸模塊，該模塊主要針對(duì)ＫＮＣ平臺(tái)，用來保障ＣＰＵ和ＫＮＣ之間??的高效數(shù)據(jù)傳輸。??？任務(wù)分發(fā)模塊，處理設(shè)備以及線程間的任務(wù)分發(fā)工作，該模塊需要盡量保??證設(shè)備以及線程間的負(fù)載均衡，以充分利用計(jì)算資源。??？計(jì)算模塊，執(zhí)行核心比對(duì)算法，返回計(jì)算結(jié)果。??？輸出模塊

們的工作線程就會(huì)一直處于工作狀態(tài)，可以充分發(fā)揮硬件的計(jì)算能力。這里我??們使用Ｐｔｈｒｅａｄｓ?（ＰＯＳＩＸ?Ｔｈｒｅａｄｓ）來創(chuàng)建輸入和輸出線程，利用條件變量和互??斥鎖來實(shí)現(xiàn)同步控制器。圖３－３展示了該實(shí)現(xiàn)的示意圖。??；輸入緩沖區(qū)ｉ?丨輸出緩沖區(qū)ｉ??＿一?＿?丨＿＿＾—圍??＇?ｉ緩沖區(qū)２１?！?ｉ緩沖區(qū)４?！?＾??＼?ｉ?—??＇?＞?，?Ａ?ｖ—＇?’?１丨?／??Ｎ?、?＇?、?Ｉ?？?、?ｊ?ｆ??Ｖ?＿＿?／??＼?＾?Ｉ?岑、?Ｚ??仏４“．??■ＢＢＰ＊??圖３－３流水線實(shí)現(xiàn)示意圖??３．３任務(wù)分發(fā)模塊??任務(wù)分發(fā)模塊主要用來在設(shè)備以及線程間進(jìn)行比對(duì)任務(wù)的分配，在單獨(dú)的??ＣＰＵ或者ＫＮＬ平臺(tái)上，我們可以借助于ＯｐｅｎＭＰ?（Ｏｐｅｎ?Ｍｕｌｔｉ－Ｐｒｏｃｅｓｓｉｎｇ）提??供的調(diào)度功能來實(shí)現(xiàn)線程間的負(fù)載均衡。但是在由ＣＰＵ和ＫＮＣ構(gòu)成的異構(gòu)平??臺(tái)中，ＣＰＵ和ＫＮＣ會(huì)同時(shí)參與到計(jì)算，因此我們需要保證各設(shè)備間的負(fù)載均??衡，以充分發(fā)揮各個(gè)設(shè)備的計(jì)算性能。關(guān)于ＯｐｅｎＭＰ的相關(guān)內(nèi)容我們會(huì)在下一??章中進(jìn)行詳細(xì)的敘述，這里主要介紹一下我們針對(duì)多設(shè)備設(shè)計(jì)的任務(wù)分發(fā)框架。??因?yàn)槊總�(gè)設(shè)備的計(jì)算能力不同，所以我們不能簡(jiǎn)單的為每個(gè)設(shè)備分配相同的任??務(wù)。我們維護(hù)了一個(gè)任務(wù)劃分的比例表

根據(jù)ｉ？對(duì)數(shù)據(jù)塊進(jìn)行劃分，將數(shù)據(jù)分配給相應(yīng)的設(shè)備，當(dāng)處理完成之后，我們??會(huì)收集各設(shè)備的處理時(shí)間，然后更新在處理下一個(gè)數(shù)據(jù)塊時(shí)使用更新后的??Ｈ進(jìn)行數(shù)據(jù)劃分。圖３－４展示了任務(wù)分發(fā)模塊的運(yùn)行流程。??動(dòng)態(tài)調(diào)節(jié)??Ｖ?＞?、??；?一一｜??：?Ｉ?丨?；??圖３－４任務(wù)分發(fā)模塊示意圖??下面我們來看下動(dòng)態(tài)調(diào)節(jié)尺的過程。我們首先定義幾個(gè)符號(hào)，??？州，Ｍｂ表示在處理第ｊ個(gè)數(shù)據(jù)塊時(shí)，第ｉ個(gè)設(shè)備分配到的任務(wù)量和第１??個(gè)設(shè)備的比例，其中有？三１。??？?Ｔ，?７＾表示在處理第ｊ個(gè)數(shù)據(jù)塊時(shí)，第ｉ個(gè)設(shè)備耗費(fèi)的計(jì)算時(shí)間：。??假設(shè)我們有ｎ個(gè)設(shè)備，在處理第ｊ個(gè)數(shù)據(jù)塊時(shí)，我們會(huì)首次計(jì)算出丨Ｖ的??值，然后根據(jù)公式３．１來計(jì)算出７？的值。??Ｒｉ?＝?＾７）—，７７?（３．１）??２＾＝１?”？??在理想情況下
【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王進(jìn)科;馮萍;康繼昌;陳亞東;;基于布爾邏輯的雙序列比對(duì)協(xié)處理器的設(shè)計(jì)與實(shí)現(xiàn)[J];西北工業(yè)大學(xué)學(xué)報(bào);2011年01期

2 張永;王瑞;;生物信息學(xué)中的序列比對(duì)算法[J];電腦知識(shí)與技術(shù);2008年01期

3 張濤濤;郭茂祖;鄒權(quán);;參數(shù)序列比對(duì)算法研究(英文)[J];生物信息學(xué);2008年02期

4 唐玉榮;生物信息學(xué)中一個(gè)優(yōu)化的全局雙序列比對(duì)算法[J];計(jì)算機(jī)應(yīng)用;2004年S1期

5 張敏;生物序列比對(duì)算法研究現(xiàn)狀與展望[J];大連大學(xué)學(xué)報(bào);2004年04期

6 單路超;王建章;許德森;李東垣;趙鵬;王國相;褚騰飛;;基于局部序列比對(duì)的漏洞挖掘技術(shù)研究[J];微型機(jī)與應(yīng)用;2017年03期

7 楊潔;劉海;;生物序列比對(duì)算法的研究現(xiàn)狀[J];中國科技信息;2011年09期

8 葉笑春;林偉;范東睿;張浩;;蛋白質(zhì)序列比對(duì)算法在眾核結(jié)構(gòu)上的并行優(yōu)化[J];軟件學(xué)報(bào);2010年12期

9 駱嘉偉;陳斐;彭東海;;基于混合行為的蟻群雙序列比對(duì)方法[J];計(jì)算機(jī)工程與應(yīng)用;2009年11期

10 吳德敏;陳俊;;雙序列比對(duì)的算法研究[J];計(jì)算機(jī)工程與應(yīng)用;2008年36期

相關(guān)博士學(xué)位論文 前10條

1 唐玉榮;生物信息學(xué)中的序列比對(duì)算法研究[D];中國農(nóng)業(yè)大學(xué);2004年

2 李玉崗;生物大分子序列比對(duì)和蛋白質(zhì)結(jié)構(gòu)分類算法[D];中國科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2004年

3 陳科;最優(yōu)化方法在生物序列比對(duì)中的應(yīng)用與研究[D];電子科技大學(xué);2010年

4 向旭宇;基因序列與結(jié)構(gòu)的信息分析及應(yīng)用算法研究[D];湖南大學(xué);2010年

5 馬爽;多功能雷達(dá)電子情報(bào)信號(hào)處理關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2013年

6 劉廣臣;若干統(tǒng)計(jì)計(jì)算模型研究及其在生物醫(yī)學(xué)信息處理中的應(yīng)用[D];山東大學(xué);2016年

7 李想;多重序列比對(duì)上的RNA相互作用問題[D];南開大學(xué);2013年

8 曹永忠;新城疫病毒生物信息分析系統(tǒng)的構(gòu)建及其全基因組的比較研究[D];揚(yáng)州大學(xué);2009年

9 Sagheer Atta;[D];西南大學(xué);2011年

10 楊凡;生物序列分析中若干問題的研究[D];電子科技大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 黃丹青;基于混合化學(xué)反應(yīng)優(yōu)化算法的序列比對(duì)研究[D];湖南大學(xué);2014年

2 張彩華;模糊隱馬氏模型及其在生物序列比對(duì)中的應(yīng)用[D];山東大學(xué);2018年

3 張吉?jiǎng)P;基于英特爾多核及眾核平臺(tái)的全局序列比對(duì)算法研究[D];山東大學(xué);2018年

4 郭睿東;基于變長種子的找全測(cè)序序列比對(duì)算法研究及優(yōu)化[D];中國科學(xué)技術(shù)大學(xué);2018年

5 姜鮮桃;雙序列比對(duì)Needleman-Wunsch算法研究[D];內(nèi)蒙古農(nóng)業(yè)大學(xué);2017年

6 何萬雙;雙序列比對(duì)算法研究[D];國防科學(xué)技術(shù)大學(xué);2006年

7 李川;雙序列比對(duì)算法研究與并行優(yōu)化[D];西安電子科技大學(xué);2011年

8 林敏;新一代則序技術(shù)中的短序列比對(duì)和組裝算法[D];福建農(nóng)林大學(xué);2011年

9 紀(jì)文娟;生物同源序列比對(duì)算法研究及其實(shí)現(xiàn)[D];江南大學(xué);2009年

10 馮百龍;雙序列比對(duì)Needleman-Wunsch算法的分布式并行優(yōu)化研究[D];內(nèi)蒙古農(nóng)業(yè)大學(xué);2015年

本文編號(hào)：2855558