異構(gòu)機(jī)群系統(tǒng)上最長公共子序列并行計算研究.pdf

1、求解任意給定的兩個字符串的最長公共子序列(LCS)的問題是計算機(jī)科學(xué)中一個基本和重要的問題，它是一種僅僅允許對模式和正文進(jìn)行插入和刪除編輯操作的近似串匹配問題。最長公共子序列在生物序列相似性分析、網(wǎng)絡(luò)入侵檢測、網(wǎng)絡(luò)遠(yuǎn)程教學(xué)、電子商務(wù)、信息檢索、數(shù)據(jù)挖掘、自動命題等領(lǐng)域應(yīng)用廣泛。隨著串序列數(shù)量的增長，即使采用快速的LCS串行算法求解也顯得力不從心。機(jī)群計算系統(tǒng)具有高性能和低成本的特點，在異構(gòu)機(jī)群系統(tǒng)上研究最長公共子序列的并行計算具有重要的

2、現(xiàn)實意義。 對于多序列的LCS問題，基于可分負(fù)載理論的最優(yōu)原則，在將目標(biāo)串分配給從處理機(jī)的順序固定的前提下，考慮處理機(jī)節(jié)點具有不同計算速度、不同通信能力和存儲容量的情況，本文提出了一種異構(gòu)機(jī)群計算環(huán)境下的最優(yōu)目標(biāo)串分配策略，在這種分配策略下各個從處理機(jī)按照目標(biāo)串的分配順序開始執(zhí)行串行LCS算法并同時結(jié)束，從而使得LCS并行算法的完成時間最小。實驗結(jié)果表明，在異構(gòu)機(jī)群系統(tǒng)上，與按平均分配目標(biāo)串策略相比，利用本文提出的最優(yōu)目標(biāo)串分配

3、策略求解擴(kuò)展最長公共子序列問題的并行算法所需的時間縮短了6～32％。 對于雙序列的LCS問題，在假定從處理機(jī)分配順序固定的前提下，考慮處理機(jī)節(jié)點具有不同計算速度、不同通信能力的異構(gòu)機(jī)群系統(tǒng)情況，本文提出一種最優(yōu)序列串分配策略，并給出了相應(yīng)的序列串分配的閉合解，以此劃分雙序列的動態(tài)規(guī)劃矩陣，通過各從處理機(jī)之間的相互協(xié)調(diào)通信以最小化并行求解雙序列LCS問題的時間。算法分析與實驗結(jié)果表明，按最優(yōu)序列串分配策略比按平均分配策略執(zhí)行算法顯