基因是指控制生物性狀的遺傳信息,通常由DNA序列承載,可以視作基本遺傳單位�；虻漠a(chǎn)物可以是蛋白質(zhì)和RNA,從而控制生物個體的性狀差異表現(xiàn)。而兩個基因的相似度有多高,演化上是否可能同源。歸結(jié)到計算上,就是如何找到兩個序列的最優(yōu)或近似最優(yōu)的比對。隨著人類基因組計劃的測序工作的完成,生物信息科學的研究重點放在了探明基因序列的功用上。而在高通量測序技術(shù)快速進展的背景之下,生物數(shù)據(jù)呈現(xiàn)指數(shù)型增長。因此產(chǎn)生了對大量生物信息數(shù)據(jù)進行高效準確分析的需求。基因序列決定了生物的性狀,查找出基因差異性對于人類克服疾病具有深遠的意義。本文在Xeon Phi眾核架構(gòu)上,設計并實現(xiàn)了一個全新的超長序列比對算法SLPal。該算法的計算核心是基于位并行的BitPAI算法。在粗粒度上,為了實現(xiàn)多線程并行,我們將超大規(guī)模的矩陣進行了劃分。在垂直和水平方向上分別進行劃分,將矩陣分成了網(wǎng)格。然后通過Intel TBB并行編程庫構(gòu)建了有向無環(huán)圖模型來實現(xiàn)該網(wǎng)格中矩陣塊之間的并行。在細粒度上,我們用Xeon Phi上的指令集編寫了 Intrinsic指令。SLPal中的一些操作沒有對應的向量化實現(xiàn),我們采用手動編寫函數(shù)來實現(xiàn)了... 

【文章來源】：山東大學山東省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：59 頁

【學位級別】：碩士

【部分圖文】：

圖3一2位向量刁擴的計算實例

?山東大學碩士學位論文???ＣＰＵ數(shù)量等優(yōu)勢，而且ＴＢＢ?lián)碛胁⑿醒h(huán)，并行排序，流的并行和并行容器，??以及可擴展的內(nèi)存分配，動態(tài)任務調(diào)度器。所以最終本人選擇ＴＢＢ來編寫本人??的程序。任務調(diào)度器是線程構(gòu)建模塊的核心組件，它是通過線程來提升性能的。??在ＴＢＢ的任務調(diào)度中，一個任務作為一個基本計算單元，由調(diào)度器將線程與任??務結(jié)合在一起，并且將任務分派到物理線程進行執(zhí)行。任務調(diào)度器擁有一個全??局線程池，進行任務調(diào)度之前，需要初始化線程構(gòu)建模塊，然后任務調(diào)度器會??根據(jù)這個線程池自動管理任務，將每個任務動態(tài)分配到壓力較小的物理線程上，??實現(xiàn)負載均衡。??

由于計算超長序列的全局序列比對，相當于要計算一個ＭＸＮ的動態(tài)規(guī)劃矩??陣，其中Ｍ和Ｎ分別為所對比的２個序列的長度。且Ｍ和Ｎ可能長為１００Ｍ大小，??所以為了充分利用多線程資源，本人將所要計算的矩陣劃分為如圖３－６所示的??子矩陣，并且其中每一個子矩陣都是一個任務類的實現(xiàn)，也就是ＳＬＰａｌＴＵｅ??類的實例，ＳＬＰａｌＴｉｌｅ繼承自ｔｂｂ：：ｔａｓｋ類。并且ｔａｓｋ類交由ＴＢＢ［４６］任務管??理器ｔａｓｋ＿ｓｃｈｃｄｕｌｃｒ＿ｉｎｉｔ進行管理。根據(jù)前面說明的ＢｉｔＰＡｌ算法可以得知，??計算每個單元格的數(shù)據(jù)依賴僅僅存在于上方和左側(cè)的單元格，所以ｔａｓｋ之間的??３０??


本文編號：2951784