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

论文摘要

串匹配问题是计算机科学中的一个基本问题。精确串匹配技术要求模式与正文子串完全匹配，不允许有错误。但是在许多实际情况中，并不要求模式与文本子串完全精确匹配，因此人们引入了近似串匹配技术。在许多实际应用中，正文串的规模很大，即使利用最快的近似串匹配顺序算法也很耗时，因此需要设计高效的近似串匹配并行算法以快速求解这类问题。由于机群计算系统具有高性能和低成本的特点，所以在异构机群系统上研究近似串匹配的并行处理具有重要的现实意义。这种粗粒度并行的近似串匹配技术的关键问题是如何恰当地划分正文串并将其分配到合适的处理机上，以使得从分配正文串开始到所有处理机完成近似串匹配所经历的时间最短。基于可分负载理论的最优原则，在假定正文串分配顺序固定的前提下，考虑处理机节点具有不同计算速度、不同通信能力的情况，提出异构机群计算环境下的最优正文串单轮分配策略并给出最优正文串分配的闭合解；进一步地，对于节点具有不同计算速度、不同通信能力、不同存储容量的异构机群系统，建立正文串最优分配的线性规划模型；并且针对几种特殊情况讨论正文串的最优分配顺序。算法分析与实验结果表明，与平均分配正文串策略以及按照从处理机能力分配正文串策略相比，利用本文提出的最优正文串单轮分配策略进行单模式单正文串近似匹配并行处理所需的时间分别缩短了10～40％和5～20％。在给定正文串分配轮数的前提下，考虑处理机节点具有不同计算速度、不同通信能力的情况，根据是否允许处理机重叠执行计算和通信操作，本文提出异构机群计算环境下的最优正文串多轮分配策略，同时提出一种周期性的正文串多轮分配策略，此策略可以求出最优的分配轮数，并给出了相应的正文串多轮分配的闭合解。算法分析与实验结果表明，按正文串多轮分配策略比按正文串单轮分配策略执行的并行算法大大缩短了单模式单正文串近似匹配处理所需的时间。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 近似串匹配问题的研究背景
• 1.2 近似串匹配问题的相关概念
• 1.2.1 近似串匹配问题的定义
• 1.2.2 编辑操作与距离函数
• 1.2.3 几种常见的距离函数
• 1.3 单模式与单正文串近似串匹配顺序算法研究综述
• 1.3.1 基于动态规划方法的单模式与单正文串近似串匹配算法研究综述
• 1.3.2 基于自动机理论的单模式单正文串近似串匹配算法研究综述
• 1.3.3 基于位并行方法的单模式单正文串近似串匹配算法研究综述
• 1.3.4 基于过滤方法的单模式与单正文串近似串匹配算法研究综述
• 1.4 单模式单正文串近似串匹配并行算法研究现状
• 1.5 论文的主要研究内容和论文的组织
• 第二章 并行计算理论基础
• 2.1 并行计算机系统
• 2.1.1 并行计算机的发展
• 2.1.2 并行计算机的分类
• 2.2 并行算法的基础知识
• 2.2.1 并行算法的定义
• 2.2.2 并行算法的分类
• 2.2.3 并行算法的性能评价标准
• 2.3 并行计算模型
• 2.3.1 PRAM模型
• 2.3.2 异步APRAM模型
• 2.3.3 BSP模型
• 2.3.4 LogP模型
• 2.4 机群系统概述
• 2.4.1 机群系统特点
• 2.4.2 机群系统分类
• 2.4.3 机群技术发展现状
• 2.4.4 机群系统的组建
• 第三章 基于单轮分配方式的单模式单正文串近似串匹配并行算法
• 3.1 引言
• 3.2 可分负载理论简介
• 3.3 异构机群系统上基于单轮分配方式的单模式单正文串近似串匹配问题
• 3.4 最优正文串单轮分配策略
• 3.4.1 不考虑处理机存储受限的正文串单轮分配策略
• 3.4.2 处理机存储受限的正文串单轮分配策略
• 3.4.3 最优正文串分配顺序
• 3.5 实验
• 3.5.1 实验环境
• 3.5.2 实验结果分析
• 3.6 本章小结
• 第四章 基于多轮分配方式的单模式单正文串近似串匹配并行算法
• 4.1 引言
• 4.2 异构机群系统上基于多轮分配方式的单模式单正文串近似串匹配问题
• 4.3 分配轮数给定的最优正文串多轮分配策略
• 4.3.1 不允许处理机重叠执行计算和通信操作的最优正文串多轮分配策略
• 4.3.2 允许处理机重叠执行计算和通信操作的最优正文串多轮分配策略
• 4.4 周期性正文串多轮分配策略
• 4.4.1 不允许处理机重叠执行计算和通信操作的周期性正文串多轮分配策略
• 4.4.2 允许处理机重叠执行计算和通信操作的周期性正文串多轮分配策略
• 4.5 实验
• 4.5.1 实验环境
• 4.5.2 实验结果分析
• 4.6 本章小结
• 第五章 总结
• 5.1 本文的主要贡献和研究特色
• 5.2 进一步的工作
• 参考文献
• 致谢
• 攻读硕士学位期间参加的科研项目
• 攻读硕士学位期间录用发表的学术论文