学位论文 > 优秀研究生学位论文题录展示

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

作　者: 许莉莉
导　师: 钟诚
学　校: 广西大学
专　业: 计算机软件与理论
关键词: 最长公共子序列 并行算法 异构机群系统 可分负载 分配策略
分类号: TP301.6
类　型: 硕士论文
年　份: 2008年
下　载: 85次
引　用: 0次
阅　读: 论文下载
 

内容摘要


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

全文目录


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

相似论文

  1. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  2. 基于并行算法的模糊综合评价模型的设计与应用,TP18
  3. 基于视觉反馈与行为记忆的GPU并行蚁群算法,TP301.6
  4. GPU加速的仿射算术在几何设计中的应用研究,TP391.41
  5. 基于GPU的H.264到AVS视频转码并行设计,TN919.81
  6. H.264并行编码算法设计及其在GPU上的实现,TP391.41
  7. 基于ADSPTS201S的并行信号处理系统的设计与实现,TN957.51
  8. 基于小波变换的图像压缩并行算法研究,TP391.41
  9. 基于GPU的并行蚁群优化算法的研究与实现,TP301.6
  10. 基于MapReduce的聚类算法的并行化研究,TP311.13
  11. SSD文件系统优化技术的研究与实现,TP316
  12. 面向星载计算机的容错并行算法研究与实现,TP302.8
  13. 激光能量沉积光路追踪法及其并行化,TN241
  14. 基于LBM的两相流数值模拟及其并行算法的实现,O359
  15. 基于树形计算结构的电力系统潮流并行算法研究,TM744
  16. D-TIN并行构建方法及其在地图综合中的应用研究,P283
  17. 图像匹配的并行算法研究,TP301.6
  18. 求解大规模支持向量机问题的并行算法研究,TP18
  19. 面向网页去重的特征提取与重复模式发现,TP393.092
  20. 基于负荷预测的既有建筑制冷机组运行节能研究,TU831.3
  21. 迁移式并行遗传算法求解支持向量机反问题,TP18

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com