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

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

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

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