异构机群系统上最长公共子序列并行计算分析

《异构机群系统上最长公共子序列并行计算分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、StudyonParallelAlgorithmsforLongestCommonSubsequenceonHeterogeneousClusterComputingSystemsABSTRACTSolvingthelongestcommonsubsequence(Lcs)ofanygivenstringsisoneofthebasicandimportant陀searchproblemsincomputerscience．ItisaapproximatestringmatchingproblemwhichisonlyallowedtodOtheeditingoperationsofinse

2、rtionanddeletion．ThelongestcommonsubsequencehasbeenwidelyapplyingtOmanyareassuchasbiologicalsequencesimilarityanalysis，networkintrusiondetection,net、帕^(佗moteinstruction，E-commerce，informationretrieval，dataminingandautomaticproposition·Withthegrowthofstringsequence，therapidserialalgorithmtosolveLCSp

3、roblemalsoappearsinefficient·Duetohighperformanceandlowcostoftheclustercomputingsystems，parallelprocessingforthelongestcommonsubsequenceontheheterogeneousclustercomputingsystemsISverymeaningfulinpractice．FortheLCSproblemwithmultiplesequences，basedontheoptimalityprincipleofdivisibleloadtheoryandthef

4、ixedsequenceofobjectivestringsdistribution，anoptimalobjectivestringsdistributionstrategyispresentedontheheterogeneousclustercomputingsystemsthatprocessorshavedifferentcomputingspeedsandcommunicationcapabilities．WiththisstrategyeveryslaveprocessorstartstheimplementationofserialLCSalgorithmandfinishe

5、sthecomputingatthesametimewiththefixed辩quenceofobjectivestringsdistribution，SOthattherequiredparallelprocessingtimeforparallelLCSAlgorithmistoobtainminimumvalue．ThealgorithmsanalysisandexperimentalresultsontheclusterofpersonalcomputersshowthattherequiredparallelprocessingtimeforparallelLCSAlgorithm

6、applyingtheoptimalobjectivestringsdistributionstrategydecreases6^_32％comparedtodividingtheobjectivestringsequally．Forthepair-wisesequenceLCSproblem，andtheassumptionthatthedistributionofprocessorsinafixedorder．anoptimalsequencedistributionstrategyisfirstpresentedbydividingintothedynamicprogrammingma

7、trixofpair-wisesequenceanditscorrespondingclosed·formexpressionsaregivenontheheterogeneousclustercomputingsystemsthatprocessorshaveIIIdifferentcomputingspeedsandcommunicationcapabilities．Bycoordinatingtheco