多核CPU和GPU并行求解最短公共超串.pdf

1、人類基因組計劃目標(biāo)是完成人類染色體的全部 DNA的測序,這對于治療遺傳病有著重要的意義?，F(xiàn)有的技術(shù)不可能直接連續(xù)測序超過幾百個堿基的片段,只能使用散彈槍法獲得并測序大量的片段,然后根據(jù)片段間的重疊來重構(gòu)目標(biāo)分子,所以將該問題轉(zhuǎn)化為最短公共超串問題,并使用計算機(jī)來快速求解是一種新途徑。因此,研究在多核CPU/GPU系統(tǒng)上最短公共超串的并行求解具有重要意義。
　　本文依據(jù)各級緩存容量,將 CPU主存中種群個體和螞蟻個體數(shù)據(jù)劃分存儲到一

2、級、二級和三級緩存中,以減少并行計算過程中數(shù)據(jù)在各級存儲之間的傳輸開銷,在 CPU與 GPU之間采取異步傳送和不完全傳送數(shù)據(jù)、GPU多個內(nèi)核函數(shù)異步執(zhí)行多個流的方法,設(shè)置GPU block線程數(shù)量為16的倍數(shù)、GPU共享存儲器劃分大小為32倍的bank,使用GPU常量存儲器存儲交叉概率、變異概率等需頻繁訪問的只讀參數(shù),將輸入串矩陣和重疊部分長度矩陣只讀大數(shù)據(jù)結(jié)構(gòu)綁定到GPU紋理存儲器,設(shè)計實現(xiàn)了一種多核 CPU和GPU協(xié)同求解最短公共超

3、串問題的計算、存儲和通信高效的并行算法。求解多種規(guī)模的最短公共超串問題的實驗結(jié)果表明,多核CPU與GPU協(xié)同并行算法比串行算法快70倍以上。
　　對于節(jié)點具有不同計算能力和存儲能力的CPU/GPU異構(gòu)機(jī)群系統(tǒng),以節(jié)點完成任務(wù)量時間最短為目標(biāo),給出帶返回信息的可分負(fù)載最優(yōu)多輪調(diào)度模型,設(shè)計適用于求解最短公共超串問題的數(shù)據(jù)分配算法,采取每個節(jié)點運行融合遺傳蟻群算法并行求解最短公共超串的方法,設(shè)計實現(xiàn)多核CPU/GPU異構(gòu)機(jī)群并行求解最