异构机群系统上多目标和多模式近似串匹配并行算法研究

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

1、广西大学硕士学位论文异构机群系统上多目标和多模式近似串匹配并行算法研究姓名：范曾申请学位级别：硕士专业：计算机应用技术指导教师：钟诚20080628异构机群系统上多目标和多模式近似串匹配并行算法研究摘要串匹配是计算机科学中一个基本、重要的研究问题。多目标和多模式匹配是串匹配技术的重要研究内容。多目标和多模式精确串匹配技术要求目标串(正文串)与查询串(模式串)完全一致匹配。但是，在很多实际应用中，并不要求目标串与模式完全精确匹配，于是引入了多目标和多模式近似串匹配技术。许多应用的正文串(目标串)的规

2、模往往很大，需要设计高效的多目标和多模式近似匹配并行算法来快速求解这类问题。机群系统具有高性能、低成本、可扩展性好的特点。本文将在处理机节点具有不同计算速度、不同通信延迟、不同存储容量的异构机群系统上，设计、实现高效的多目标和多模式精确与近似串匹配并行算法，并分析和测试并行算法的性能。运用基于孙子定理构造的均匀Hash函数并继承K唧．Rabin模式匹配思想，通过“筛选"方法，给出一种机群系统上多目标串精确匹配并行算法。该算法将字符串映射成惟一的一对整数值并采用比较一对整数值来取代逐个字符比较模式和

3、目标串的方法，使得比较过程快速且匹配结果是确定的。算法分析和实验结果表明该并行算法简明、高效和可扩展。针对处理机节点具有不同的计算速度、通信延迟和存储容量的情形，考虑计算和通信启动开销，给定处理机分配顺序，基于可分负载理论，分别建立单层和两层树结构模型的存储受限异构机群系统的目标串最优分配线性规划模型，给出相应的目标串最优分配方法，并讨论了处理机最优分配顺序。异构PC机群系统上的实验结果表明，本文提出的基于最优分配方法的多目标串近似匹配并行算法优于平均分配算法，获得了接近线性的加速，具有良好的可扩

4、展性。对于给定的正文串和多个模式串，运用均匀Hash函数将所有模式串的签名映射成惟一的一对整数值并存储于Hash表中，给出正文串窗口签名Hash值的推算公式；在节点具有不同的计算速度、通信延迟、存储容量的异构机群系统上，考虑计算和通信启动开销，基于可分负载理论，建立正文串最优分配线性规划模型，提出一种允许1个错误字符的多模式近似匹配并行算法。异构PC机群系统上的实验结果表明，该算法获得了较好的加速和可扩展性，它比基于均匀分配正文串策略的多模式近似匹配并行算法平均快25％。关键词：多目标串近似匹配多

5、模式近似匹配异构机群系统并行算法Hashing可分负载存储受限lIstudyonParaHelAlgorithmsforApproximateMulti-ObjectandMulti-PatternMatchingonHeterogeneousClusterSystemsABSTRACTStringmatcIlingisoIleofthebaSicandimportantresearchproblemsincomputerscience．Multi-objectmatchinga11dmulti-

6、pa吮mmatchingareimport锄tissuesiIlstringmatcllingfield．Exactmuni—objectmatchingandmIllti·pattemmatchingrequiretllattheobjectstringsorthesubstringsoftextmatchcompletely而ththeque巧嘶ngorpattemsa11ddon’ta110wanyerror．Butinmally印plications，meobjectstringsorth

7、esubstringsoftcXtcanmatch谢thtlleque盯stringorpa_ttemsallo、啊ngsomeerrors．SincethesizeofteXtortllem啪berofobjectstringsisoRenVe巧large，itisnecessa巧t0desi印KgmyemcientparallelalgoritIlIIlsfor印proximatemulti—objectandmulti-pattemmatching．ThecluStercomputingsy

8、stemshaVethecharaIcteriSticsofhi曲pe墒册ance，lowcostandsCalabili够11lisp印er姗iest0desi弘aIldimplementtliglllyemcientparallelalgoritl姗sforexactand印proximatemulti—object锄dmulti-pattemmatchingonheterogeneouScluStersystemsthatprocessorshaVedifrerentcomp