多核CPU和GPU系統(tǒng)上Motif發(fā)現(xiàn)并行算法研究.pdf

1、Motif(模體)是指DNA序列中長度較短、具有保守功能的序列片段,Motif發(fā)現(xiàn)即從DNA序列中尋找出Motif的過程,該問題是生物信息學(xué)中一個基礎(chǔ)而重要的研究課題。利用計算機技術(shù)來解決該問題的目標是尋找更長l的Motif。因此,在多核CPU和GPU系統(tǒng)上研究設(shè)計訪存高效、加速比高、可擴展性好的(l,d)-Motif發(fā)現(xiàn)并行算法具有現(xiàn)實意義。
　　本文結(jié)合多核計算機的多級緩存存儲結(jié)構(gòu)特點,設(shè)計實現(xiàn)了一種訪存高效、加速比高、可擴展

2、性好的線程級并行(l,d)-Motif發(fā)現(xiàn)算法。充分利用多核結(jié)構(gòu)的共享三級緩存、私有二級和一級緩存容量大小,將求解(l,d)-Motif發(fā)現(xiàn)問題過程中產(chǎn)生的大量不同位置組合的數(shù)據(jù),以多輪方式調(diào)度分配到各級緩存中,使得各個核心在并行求解(l,d)-Motif發(fā)現(xiàn)問題時,大大減少了數(shù)據(jù)在主存和緩存之間的交換次數(shù),實現(xiàn)了并行算法的訪存高效;同時,通過線程綁定平衡了各計算核心的負載、減少了線程遷移開銷。實驗測試綜合考慮了不同(l,d)-Moti

3、f發(fā)現(xiàn)問題規(guī)模、處理核心數(shù)、線程數(shù)目、各級緩存可利用大小等多種因素對多核計算機上(l,d)-Motif發(fā)現(xiàn)并行算法性能的影響。實驗結(jié)果表明,隨著處理核心數(shù)的增加,本文多核計算機上(l,d)-Motif發(fā)現(xiàn)并行算法表現(xiàn)出越高的效率,具有良好的加速比和可擴展性,在并行求解較長l的(l,d)-Motif發(fā)現(xiàn)問題時,其所需的運行時間明顯少于同類研究的其他算法。
　　根據(jù)GPU的結(jié)構(gòu)特點以及存儲器特點,將求解(l,d)-Motif發(fā)現(xiàn)問題過

4、程中產(chǎn)生的大量不同位置組合的數(shù)據(jù)和候選序列集合綁定到紋理存儲器中,通過緩存加速訪問,減少訪存時間;對不同的(l,d)-Motif發(fā)現(xiàn)問題規(guī)模,依據(jù)組合數(shù)據(jù)大小設(shè)置GPU端線程塊的尺寸,設(shè)計實現(xiàn)了多核CPU與單GPU混合機器上(l,d)-Motif發(fā)現(xiàn)并行算法,為提高處理較大規(guī)模(l,d)-Motif發(fā)現(xiàn)問題的加速效果,同時設(shè)計實現(xiàn)了多核CPU與多GPU混合機器上(l,d)-Motif發(fā)現(xiàn)并行算法。實驗測試綜合考慮了不同(l,d)-Mot