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

论文摘要

串匹配是计算机科学中一个基本、重要的研究问题。多目标和多模式匹配是串匹配技术的重要研究内容。多目标和多模式精确串匹配技术要求目标串（正文串）与查询串（模式串）完全一致匹配。但是,在很多实际应用中,并不要求目标串与模式完全精确匹配,于是引入了多目标和多模式近似串匹配技术。许多应用的正文串（目标串）的规模往往很大,需要设计高效的多目标和多模式近似匹配并行算法来快速求解这类问题。机群系统具有高性能、低成本、可扩展性好的特点。本文将在处理机节点具有不同计算速度、不同通信延迟、不同存储容量的异构机群系统上,设计、实现高效的多目标和多模式精确与近似串匹配并行算法,并分析和测试并行算法的性能。运用基于孙子定理构造的均匀Hash函数并继承Karp-Rabin模式匹配思想,通过“筛选”方法,给出一种机群系统上多目标串精确匹配并行算法。该算法将字符串映射成惟一的一对整数值并采用比较一对整数值来取代逐个字符比较模式和目标串的方法,使得比较过程快速且匹配结果是确定的。算法分析和实验结果表明该并行算法简明、高效和可扩展。针对处理机节点具有不同的计算速度、通信延迟和存储容量的情形,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,分别建立单层和两层树结构模型的存储受限异构机群系统的目标串最优分配线性规划模型,给出相应的目标串最优分配方法,并讨论了处理机最优分配顺序。异构PC机群系统上的实验结果表明,本文提出的基于最优分配方法的多目标串近似匹配并行算法优于平均分配算法,获得了接近线性的加速,具有良好的可扩展性。对于给定的正文串和多个模式串,运用均匀Hash函数将所有模式串的签名映射成惟一的一对整数值并存储于Hash表中,给出正文串窗口签名Hash值的推算公式;在节点具有不同的计算速度、通信延迟、存储容量的异构机群系统上,考虑计算和通信启动开销,基于可分负载理论,建立正文串最优分配线性规划模型,提出一种允许1个错误字符的多模式近似匹配并行算法。异构PC机群系统上的实验结果表明,该算法获得了较好的加速和可扩展性,它比基于均匀分配正文串策略的多模式近似匹配并行算法平均快25%。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 串匹配及其应用
• 1.2 多目标串和多模式近似匹配
• 1.2.1 多目标串和多模式近似匹配问题
• 1.2.2 编辑操作与距离函数
• 1.2.3 编辑距离的计算
• 1.3 多目标串和多模式近似匹配并行算法研究现状
• 1.3.1 多目标串近似匹配串行和并行算法研究进展
• 1.3.2 多模式近似匹配串行和并行算法研究综述
• 1.4 论文选题的目的和意义
• 1.5 论文的主要研究内容和论文的组织
• 第二章 并行计算理论基础
• 2.1 并行计算概述
• 2.2 当代并行计算机体系结构
• 2.3 并行计算模型
• 2.4 并行算法基础知识
• 2.4.1 并行算法的定义和分类
• 2.4.2 并行算法的复杂性度量
• 2.4.3 并行算法的性能评价
• 2.5 机群计算系统
• 2.5.1 机群系统的概念
• 2.5.2 机群系统的分类
• 2.5.3 机群系统的关键技术
• 2.5.4 机群系统的发展现状
• 第三章 机群系统上基于Hashing的多目标串匹配并行算法
• 3.1 引言
• 3.2 Hash函数及均匀Hash函数的构造
• 3.3 机群系统上多目标串匹配并行算法
• 3.4 实验
• 3.5 本章小结
• 第四章 存储受限异构机群系统的多目标串近似匹配并行算法
• 4.1 引言
• 4.2 可分负载理论与异构机群系统的多目标串近似匹配问题
• 4.3 多目标串最优分配方法
• 4.3.1 单层树结构模型的存储受限异构机群系统的多目标串最优分配方法
• 4.3.2 两层树结构模型的存储受限异构机群系统的多目标串最优分配方法
• 4.3.3 处理机最优分配顺序
• 4.4 实验
• 4.4.1 实验环境
• 4.4.2 实验结果
• 4.4.3 可扩展性分析
• 4.5 本章小结
• 第五章 异构机群系统上的多模式近似匹配
• 5.1 引言
• 5.2 MultiHash算法
• 5.3 模式串处理和正文窗口签名Hash值的计算
• 5.3.1 模式串并行处理
• 5.3.2 正文窗口签名Hash值的计算
• 5.4 正文串最优分配方法
• 5.5 允许1个错误字符的多模式近似匹配并行算法
• 5.6 实验
• 5.6.1 实验环境
• 5.6.2 实验结果
• 5.7 本章小结
• 第六章 总结
• 6.1 本文的主要工作
• 6.2 本文的贡献与创新之处
• 6.3 下一步的工作
• 参考文献
• 致谢
• 攻读硕士学位期间参加的科研项目
• 攻读硕士学位期间发表/录用的学术论文