資源描述：
《異構(gòu)機(jī)群系統(tǒng)上單模式單正文串近似串匹配并行算法分析》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、StudyonParallelAlgorithmsforApproximateStringMatchingwithSinglePatternandSingleTextonHeterogeneousClusterComputingSystemsABSTRACTThestringmatchingisoneofbasicresearchproblemsincomputerscience．Theexactstringmatchingtechnologyrequiresthatthepatternmatchescompletelythesu
2、bstringsofthetextanditdoesn’tallowerrors．Inmanyapplications,thepatternneedn’tmatchthesubstringsofthetextexactly,SOpeopleintroducetheapproximatestringmashingtechnology．Whenthetextisaverylongstring，itistime-consumingtosolvetheapproximates仃ingmatchingproblemevffilthought
3、hefastestsequentialalgorithmisaxecuted．Soitisnecessarytodesignhiglllyefficientparallelalgorithmforapproximatestringmatching．Duetohigllperformanceandlowcostoftheclustercomputingsystems，parallelprocessingforapproximatestringmatchingontheclustercomputingsystemsisverymean
4、ingfulinpractice．Thekeyofdevelopingthecoar∞·gainedparallelalgorithmsishowtodividethetextstringanddistributeittotheprocessorsproperlywiththeobjectivetominimizethetotalprocessingtimefromthenmsterprocessordistributesthetexttoalltheslaveprocessorsfinishthematchingwork．Bas
5、edontheoptimalityprincipleofdivisibleloadtheoryandthefixedsequenceoftextdistribution,anoptimaltextsingle-rounddistributionstrategyisfirstpresentedanditscorrespondingclosed-formexpressionsaregivenOlltheheterogeneousclustercomputingsystemsthatprocessorshavedifferentcomp
6、utingspeedsandcommunicationcapabilities．Furthermore，alinearprogrammingmodelfortheoptimaltextdistributionisconstructedfortheclustersystemsthatprocessorshavedifferentcomputingspeedsandcommun／cationcapabilitiesandmemorycapacities．Theoptimaltextdistributionsequenceforsome
7、specialcasesisalsostudied．Thealgorithmsanalysisandexperimentalresultsontheclusterofpersonalcomputersshowthattherequiredparallelprocessingtimeforapproximatestringmatchingwithsinglepatternandsingletextapplyingtheoptimaltextsingle-roundiiidistributionstrategydecreases10-
8、-40％and5--20％respectivelycomparedtodividingthetextequallyanddividingthetextaceordmgtothecomputingspeedsofprocessors．Secondly
