異構(gòu)機(jī)群系統(tǒng)上多目標(biāo)和多模式近似串匹配并行算法研究.pdf

1、串匹配是計(jì)算機(jī)科學(xué)中一個(gè)基本、重要的研究問(wèn)題。多目標(biāo)和多模式匹配是串匹配技術(shù)的重要研究?jī)?nèi)容。多目標(biāo)和多模式精確串匹配技術(shù)要求目標(biāo)串(正文串)與查詢(xún)串(模式串)完全一致匹配。但是，在很多實(shí)際應(yīng)用中，并不要求目標(biāo)串與模式完全精確匹配，于是引入了多目標(biāo)和多模式近似串匹配技術(shù)。許多應(yīng)用的正文串(目標(biāo)串)的規(guī)模往往很大，需要設(shè)計(jì)高效的多目標(biāo)和多模式近似匹配并行算法來(lái)快速求解這類(lèi)問(wèn)題。機(jī)群系統(tǒng)具有高性能、低成本、可擴(kuò)展性好的特點(diǎn)。本文將在處理機(jī)節(jié)點(diǎn)

2、具有不同計(jì)算速度、不同通信延遲、不同存儲(chǔ)容量的異構(gòu)機(jī)群系統(tǒng)上，設(shè)計(jì)、實(shí)現(xiàn)高效的多目標(biāo)和多模式精確與近似串匹配并行算法，并分析和測(cè)試并行算法的性能。 運(yùn)用基于孫子定理構(gòu)造的均勻Hash函數(shù)并繼承Karp-Rabin模式匹配思想，通過(guò)“篩選”方法，給出一種機(jī)群系統(tǒng)土多目標(biāo)串精確匹配并行算法。該算法將字符串映射成惟一的一對(duì)整數(shù)值并采用比較一對(duì)整數(shù)值來(lái)取代逐個(gè)字符比較模式和目標(biāo)串的方法，使得比較過(guò)程快速且匹配結(jié)果是確定的。算法分析和實(shí)驗(yàn)

3、結(jié)果表明該并行算法簡(jiǎn)明、高效和可擴(kuò)展。 針對(duì)處理機(jī)節(jié)點(diǎn)具有不同的計(jì)算速度、通信延遲和存儲(chǔ)容量的情形，考慮計(jì)算和通信啟動(dòng)開(kāi)銷(xiāo)，給定處理機(jī)分配順序，基于可分負(fù)載理論，分別建立單層和兩層樹(shù)結(jié)構(gòu)模型的存儲(chǔ)受限異構(gòu)機(jī)群系統(tǒng)的目標(biāo)串最優(yōu)分配線(xiàn)性規(guī)劃模型，給出相應(yīng)的目標(biāo)串最優(yōu)分配方法，并討論了處理機(jī)最優(yōu)分配順序。異構(gòu)PC機(jī)群系統(tǒng)上的實(shí)驗(yàn)結(jié)果表明，本文提出的基于最優(yōu)分配方法的多目標(biāo)串近似匹配并行算法優(yōu)于平均分配算法，獲得了接近線(xiàn)性的加速，具有良

4、好的可擴(kuò)展性。 對(duì)于給定的正文串和多個(gè)模式串，運(yùn)用均勻Hash函數(shù)將所有模式串的簽名映射成惟一的一對(duì)整數(shù)值并存儲(chǔ)于Hash表中，給出正文串窗口簽名Hash值的推算公式；在節(jié)點(diǎn)具有不同的計(jì)算速度、通信延遲、存儲(chǔ)容量的異構(gòu)機(jī)群系統(tǒng)上，考慮計(jì)算和通信啟動(dòng)開(kāi)銷(xiāo)，基于可分負(fù)載理論，建立正文串最優(yōu)分配線(xiàn)性規(guī)劃模型，提出一種允許1個(gè)錯(cuò)誤字符的多模式近似匹配并行算法。異構(gòu)PC機(jī)群系統(tǒng)上的實(shí)驗(yàn)結(jié)果表明，該算法獲得了較好的加速和可擴(kuò)展性，它比基于均