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

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

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

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

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