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

论文摘要

求解任意给定的两个字符串的最长公共子序列(LCS)的问题是计算机科学中一个基本和重要的问题,它是一种仅仅允许对模式和正文进行插入和删除编辑操作的近似串匹配问题。最长公共子序列在生物序列相似性分析、网络入侵检测、网络远程教学、电子商务、信息检索、数据挖掘、自动命题等领域应用广泛。随着串序列数量的增长,即使采用快速的LCS串行算法求解也显得力不从心。机群计算系统具有高性能和低成本的特点,在异构机群系统上研究最长公共子序列的并行计算具有重要的现实意义。对于多序列的LCS问题,基于可分负载理论的最优原则,在将目标串分配给从处理机的顺序固定的前提下,考虑处理机节点具有不同计算速度、不同通信能力和存储容量的情况,本文提出了一种异构机群计算环境下的最优目标串分配策略,在这种分配策略下各个从处理机按照目标串的分配顺序开始执行串行LCS算法并同时结束,从而使得LCS并行算法的完成时间最小。实验结果表明,在异构机群系统上,与按平均分配目标串策略相比,利用本文提出的最优目标串分配策略求解扩展最长公共子序列问题的并行算法所需的时间缩短了6～32%。对于双序列的LCS问题,在假定从处理机分配顺序固定的前提下,考虑处理机节点具有不同计算速度、不同通信能力的异构机群系统情况,本文提出一种最优序列串分配策略,并给出了相应的序列串分配的闭合解,以此划分双序列的动态规划矩阵,通过各从处理机之间的相互协调通信以最小化并行求解双序列LCS问题的时间。算法分析与实验结果表明,按最优序列串分配策略比按平均分配策略执行算法显著地缩短了并行求解双序列LCS问题所需的时间,获得了良好的加速和可扩展性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 最长公共子序列问题的研究背景
• 1.2 最长公共子序列问题的相关概念
• 1.2.1 编辑距离
• 1.2.2 最长公共子序列问题的定义
• 1.2.3 扩展的最长公共子序列问题
• 1.3 最长公共子序列顺序及并行算法研究综述
• 1.3.1 双序列最长公共子序列算法研究综述
• 1.3.2 多序列最长公共子序列算法研究综述
• 1.4 论文的主要工作和论文的组织
• 第二章 并行计算理论基础
• 2.1 并行计算概述
• 2.1.1 并行计算涉及的内容
• 2.1.2 并行计算相关概念
• 2.1.3 并行计算机的分类
• 2.2 并行算法的基础知识
• 2.2.1 并行算法和粒度
• 2.2.2 并行算法分类
• 2.2.3 并行算法设计策略
• 2.2.4 并行算法性能评估
• 2.3 并行计算模型
• 2.3.1 PRAM模型
• 2.3.2 BSP模型
• 2.3.3 LogP模型
• 2.3.4 可重构 MESH互连的光计算模型
• 2.4 机群系统概述
• 2.4.1 机群系统特点
• 2.4.2 机群系统分类
• 2.4.3 MPI软件
• 2.4.4 机群系统上的并行计算方法
• 2.5 本章小结
• 第三章 异构机群系统上求解扩展最长公共子序列问题的并行算法
• 3.1 引言
• 3.2 可分负载理论简介
• 3.3 并行求解扩展最长公共子序列问题的最优目标串分配策略
• 3.4 算法设计与分析
• 3.5 实验
• 3.5.1 实验环境
• 3.5.2 实验结果及分析
• 3.6 本章小结
• 第四章 异构机群系统上并行计算双序列的最长公共子序列
• 4.1 引言
• 4.2 异构机群系统上双序列的最长公共子序列问题
• 4.3 序列分配策略及算法描述
• 4.4 实验
• 4.4.1 实验环境
• 4.4.2 实验结果分析
• 4.5 本章小结
• 第五章 总结
• 5.1 本文的主要工作
• 5.2 进一步的工作
• 参考文献
• 致谢
• 攻读硕士学位期间参加的科研项目
• 攻读硕士学位期间录用发表的学术论文