異構(gòu)機群系統(tǒng)上單模式單正文串近似串匹配并行算法研究.pdf

1、串匹配問題是計算機科學(xué)中的一個基本問題。精確串匹配技術(shù)要求模式與正文子串完全匹配，不允許有錯誤。但是在許多實際情況中，并不要求模式與文本子串完全精確匹配，因此人們引入了近似串匹配技術(shù)。在許多實際應(yīng)用中，正文串的規(guī)模很大，即使利用最快的近似串匹配順序算法也很耗時，因此需要設(shè)計高效的近似串匹配并行算法以快速求解這類問題。由于機群計算系統(tǒng)具有高性能和低成本的特點，所以在異構(gòu)機群系統(tǒng)上研究近似串匹配的并行處理具有重要的現(xiàn)實意義。這種粗粒度并行的

2、近似串匹配技術(shù)的關(guān)鍵問題是如何恰當(dāng)?shù)貏澐终拇⑵浞峙涞胶线m的處理機上，以使得從分配正文串開始到所有處理機完成近似串匹配所經(jīng)歷的時間最短。 基于可分負(fù)載理論的最優(yōu)原則，在假定正文串分配順序固定的前提下，考慮處理機節(jié)點具有不同計算速度、不同通信能力的情況，提出異構(gòu)機群計算環(huán)境下的最優(yōu)正文串單輪分配策略并給出最優(yōu)正文串分配的閉合解；進(jìn)一步地，對于節(jié)點具有不同計算速度、不同通信能力、不同存儲容量的異構(gòu)機群系統(tǒng)，建立正文串最優(yōu)分配的線

3、性規(guī)劃模型；并且針對幾種特殊情況討論正文串的最優(yōu)分配順序。算法分析與實驗結(jié)果表明，與平均分配正文串策略以及按照從處理機能力分配正文串策略相比，利用本文提出的最優(yōu)正文串單輪分配策略進(jìn)行單模式單正文串近似匹配并行處理所需的時間分別縮短了10～40％和5～20％。 在給定正文串分配輪數(shù)的前提下，考慮處理機節(jié)點具有不同計算速度、不同通信能力的情況，根據(jù)是否允許處理機重疊執(zhí)行計算和通信操作，本文提出異構(gòu)機群計算環(huán)境下的最優(yōu)正文串多輪分配策