异构机群系统上单模式单正文串近似串匹配并行算法分析

《异构机群系统上单模式单正文串近似串匹配并行算法分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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