基于機(jī)群的并行匹配算法

《基于機(jī)群的并行匹配算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、維普資訊http://www.cqvip.com第31卷第6期測(cè)繪科學(xué)Vo1．31N62006年11月ScienceofSurveyingandMapping基于機(jī)群的并行匹配算法張春玲①。邱振戈②(①河南省測(cè)繪局，鄭州450052；②中國(guó)測(cè)繪科學(xué)研究院重點(diǎn)實(shí)驗(yàn)室，北京100039)【摘要】隨著衛(wèi)星遙感技術(shù)的發(fā)展，需要快速地將衛(wèi)星遙感圖像數(shù)據(jù)轉(zhuǎn)化為用戶需要的信息，并行圖像處理技術(shù)是解決“快速”的重要途徑。并行程序的性能與計(jì)算機(jī)體系結(jié)構(gòu)密切相關(guān)，不但取決于CPU，還與系統(tǒng)架構(gòu)、指令結(jié)構(gòu)、存儲(chǔ)部件的存取速度等因

2、素有關(guān)。一般意義上，提高并行程序的性能采用粗粒度并行，指令級(jí)優(yōu)化(ILP)和存儲(chǔ)優(yōu)化等技術(shù)。作為嘗試，本文討論了在工業(yè)標(biāo)準(zhǔn)化機(jī)群上采用軟件式共享存儲(chǔ)系統(tǒng)做的并行影像匹配方法，以影像匹配算法為例子，討論了如何在粗粒度并行、指令級(jí)優(yōu)化(ILP)和存儲(chǔ)優(yōu)化三個(gè)方面提高圖像處理的計(jì)算速度?！娟P(guān)鍵詞】影像匹配；粗粒度并行；指令級(jí)優(yōu)化(ILP)；和存儲(chǔ)優(yōu)化；機(jī)群【中圖分類號(hào)】研51【文獻(xiàn)標(biāo)識(shí)碼】A【文章編號(hào)】1009—2307(2006)06—0127-03伽為與(uIIlg0，Rimg0)關(guān)聯(lián)的匹配算子；(Limgl

3、，Rimgl，1引言1)映射到處理器P；??，(Limg7，Rimg7，q~／)映射到處隨著計(jì)算機(jī)處理器的多核化發(fā)展，高性能計(jì)算正在以理器。由，，??．，8個(gè)處理器并行計(jì)算。前所未有的勢(shì)頭開始普及，低成本高性能計(jì)算將普及到低端計(jì)算機(jī)用戶，為用戶提供廉價(jià)的幾個(gè)到幾十個(gè)CPU的計(jì)3不同節(jié)點(diǎn)上的訪問局部性分析算平臺(tái)。高性能并行計(jì)算的普及為遙感圖像處理提供了一在機(jī)群系統(tǒng)中，如果對(duì)內(nèi)存的訪問在本機(jī)不命中，遠(yuǎn)個(gè)新的發(fā)展空間。程取數(shù)的代價(jià)大；因?yàn)樵诠?jié)點(diǎn)不命中時(shí)P。就要從其他機(jī)本文從影像匹配算法的粗粒度并行性、不同節(jié)點(diǎn)上的

4、器上將相應(yīng)數(shù)據(jù)取到本機(jī)，此過程有一定的時(shí)延。如果數(shù)訪問局部性、單節(jié)點(diǎn)上的存儲(chǔ)優(yōu)化、基于SIMD的指令級(jí)影據(jù)分配不合理，本機(jī)不命中率高，并行計(jì)算效率會(huì)很低，像匹配加速方面，討論了在工業(yè)標(biāo)準(zhǔn)化機(jī)群上用軟件式共大量時(shí)間用在通訊上，計(jì)算時(shí)間的比例很低。在本文設(shè)計(jì)享存儲(chǔ)系統(tǒng)做的并行影像匹配算法的方法，并給出了計(jì)算的影像匹配并行算法中，每個(gè)處理器在對(duì)其邊界數(shù)據(jù)進(jìn)行效率的實(shí)驗(yàn)結(jié)果。計(jì)算時(shí)會(huì)出現(xiàn)本機(jī)不命中，如圖2所示，在上的相應(yīng)的2影像匹配算法的粗粒度并行性分析匹配算子4J0對(duì)Limg0，RimgO的邊界計(jì)算時(shí)要用到FLo

5、，通常的影像匹配算法，從程序設(shè)計(jì)的角度可以看成一FRO所標(biāo)記的區(qū)域數(shù)據(jù)，而FLO，F(xiàn)RO所標(biāo)記的區(qū)域不在上，在P上，如圖2中的FL1和FR1；這時(shí)發(fā)出調(diào)頁請(qǐng)求，系統(tǒng)從P上將數(shù)據(jù)復(fù)制到本機(jī)的虛擬Cache(VCache)中，數(shù)據(jù)操作如圖3所示，P。將P的Home中的數(shù)圖3本機(jī)和遠(yuǎn)程據(jù)復(fù)制到本機(jī)的VCache中。數(shù)據(jù)訪問為了減小本機(jī)不命中率，要加大VCache的尺寸，讓VCache能裝下FL1，F(xiàn)R1的全部數(shù)據(jù)，這種情況下匹配算子伽在對(duì)LimsO，RimsO的邊界計(jì)算時(shí)只出現(xiàn)一次本機(jī)不命中，計(jì)算效率大為提高。4

6、單節(jié)點(diǎn)上的存儲(chǔ)優(yōu)化分析與飛速發(fā)展的CPU主時(shí)鐘頻率相比，CPU和主儲(chǔ)器之間的速度差距仍在不斷擴(kuò)大，主存儲(chǔ)器主要器件的DRAM已成為高速計(jì)算機(jī)的主要瓶頸。因此，充分利用存儲(chǔ)層次結(jié)構(gòu)的特圖1影像匹配數(shù)據(jù)操作圖2并行匹配域分解點(diǎn)，是提高應(yīng)用程序性能的另一個(gè)重要途徑。緩存是計(jì)算機(jī)存如圖2所示，我們將按行把Limg、Rimg分成8塊進(jìn)行并儲(chǔ)層次結(jié)構(gòu)的核心，高速緩沖存儲(chǔ)器Cache是位于CPU與內(nèi)存行匹配計(jì)算。將(LimsO，RimsO，伽)映射到處理器，其中之間的臨時(shí)存儲(chǔ)器，它的容量比內(nèi)存小但交換速度快。Cache中

7、的數(shù)據(jù)是內(nèi)存中的一小部分，這-／b部分是短時(shí)間內(nèi)CPU作者簡(jiǎn)介：張春玲(1964一)，女，本科，即將訪問的數(shù)據(jù)，CPU要讀取一個(gè)數(shù)據(jù)時(shí)，首先從Cache中查工程師，主要從事航空攝影測(cè)量、高性找，如果找到就立即讀取并送給CPU處理；如果沒有找到，能計(jì)算方面的研究。就用相對(duì)慢的速度從內(nèi)存中讀取并送給CPU處理，同時(shí)把這E—mail：zhangchunling06@sina．tom個(gè)數(shù)據(jù)所在的數(shù)據(jù)塊調(diào)入Cache中，這使得以后對(duì)該塊數(shù)據(jù)的讀取在Cache中進(jìn)行，不必再調(diào)用內(nèi)存?！崭迦掌冢?006—04—20如圖

8、4所示，計(jì)算機(jī)內(nèi)的數(shù)據(jù)是順序存放的，CPU每次讀人一塊數(shù)據(jù)到Cache中，在影像匹配計(jì)算時(shí)，每行數(shù)據(jù)在計(jì)算時(shí)是被一塊塊讀人，所以在調(diào)入Cache后，計(jì)算用到的相鄰數(shù)據(jù)是Cache命中的(圖中實(shí)心黑點(diǎn))，而換行維普資訊http://www.cqvip.com128測(cè)繪科學(xué)第31卷5．3基于SIMD的指令級(jí)影像匹配加速關(guān)鍵步驟SIMD擴(kuò)展指令集中相關(guān)SIMD指令有：MOVUPS用于將128位數(shù)據(jù)從內(nèi)存?zhèn)鬏數(shù)絊IMD浮