串匹配算法的并行實(shí)現(xiàn)策略.pdf

1、隨著超級(jí)計(jì)算需求的擴(kuò)大，人們把高性能計(jì)算更多的應(yīng)用于數(shù)據(jù)挖掘應(yīng)用、圖像處理業(yè)務(wù)、基因測(cè)序比對(duì)處理、過(guò)程控制、氣象檢測(cè)等大型數(shù)據(jù)處理領(lǐng)域?？茖W(xué)計(jì)算的規(guī)模迅速膨脹，使得傳統(tǒng)的串行計(jì)算機(jī)已經(jīng)不能滿足需求，從而提出了并行計(jì)算的概念。
　　 并行計(jì)算機(jī)是指有多個(gè)處理器的計(jì)算機(jī)，只有一個(gè)處理器的計(jì)算機(jī)稱為串行機(jī)，在串行機(jī)上進(jìn)行的計(jì)算稱為串行計(jì)算，在并行計(jì)算機(jī)或者通過(guò)網(wǎng)絡(luò)共享方式模擬的并行計(jì)算機(jī)環(huán)境下進(jìn)行的運(yùn)算稱為并行計(jì)算。它將進(jìn)程相對(duì)獨(dú)立的

2、分配于不同的節(jié)點(diǎn)上，由各自獨(dú)立的操作系統(tǒng)調(diào)度，享有獨(dú)立的CPU和內(nèi)存資源；進(jìn)程間通過(guò)消息傳遞相互交換信息。
　　 MPI是1994年5月發(fā)布的一種消息傳遞接口，是為消息傳遞程序提供的標(biāo)準(zhǔn)庫(kù)。MPI以語(yǔ)言獨(dú)立的形式來(lái)定義這個(gè)接口庫(kù)，并提供了與C和Fortran語(yǔ)言的綁定，是目前高效率的超大規(guī)模并行計(jì)算最可信賴的平臺(tái)。
　　 目前，Internet連接著大量的個(gè)人PC機(jī)和各種超級(jí)計(jì)算機(jī)，匯集了大量的計(jì)算資源。為了利用Inte

3、rnet上廣泛分布的空閑計(jì)算資源，目前已經(jīng)有多個(gè)分布式計(jì)算項(xiàng)目。這些項(xiàng)目已經(jīng)證實(shí)了這種計(jì)算模型的可行性。不過(guò)這些系統(tǒng)的資源高度不穩(wěn)定、用戶不可信任、通信帶寬有限、延遲巨大。
　　 本文在對(duì)經(jīng)典的串行算法進(jìn)行分析和介紹的基礎(chǔ)上，結(jié)合并行計(jì)算中的相關(guān)知識(shí)，對(duì)串行的串匹配算法進(jìn)行改進(jìn)，在硬件的基礎(chǔ)上實(shí)現(xiàn)串匹配中的部分并行性，同時(shí)也結(jié)合了MPI并行程序設(shè)計(jì)技術(shù)，使用MPI中的消息函數(shù)來(lái)實(shí)現(xiàn)在不同處理器中的并行匹配，給出了并行實(shí)現(xiàn)中的核心