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

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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖3一2位向量刁擴(kuò)的計(jì)算實(shí)例

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

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


本文編號(hào)：2951784