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

基于并行Boost图库的单源最短路径并行算法的研究

作　者: 彭强
导　师: 肖文俊
学　校: 华南理工大学
专　业: 计算机软件与理论
关键词: 单源最短路径 并行算法 并行Boost图库 分布式并行集群系统
分类号: TP301.6
类　型: 硕士论文
年　份: 2010年
下　载: 97次
引　用: 0次
阅　读: 论文下载
 

内容摘要


以单源最短路径为主的最优路径问题是众多社会应用领域内选择最优问题的基础。随着社会信息的不断膨胀,最短路径问题所面临的数据量是非常庞大的,求解的计算时间和存储空间大大增加。因此,为了满足更快的计算效率和大的计算存储空间的严格要求,求解最短路径问题可以借助于并行计算技术,它利用并行计算机来提供足够多的内存和运算能力,并根据相应的并行计算模型开发一个行之有效的并行算法可以大大的节省最短路径问题的求解时间。本文探讨了实现技术不同的两类求解单源最短路径问题的串行算法:基于标记设定的Dijkstra算法和基于标记修正的BFM算法。同时,提出了结合这两类算法思想的一种基于桶结构的单源最短路径串行算法,算法具有好的运行时间复杂度和可并行性。然后,本文在深入研究了并行Boost图库的模块组件和功能方法的基础上,针对Dijkstra算法和BFM算法在并行Boost图库上的一般并行化实现框架和基本思想,我们提出了相应的改进方法,改进后的并行算法具有好的加速比和可扩展性。此外,本文重点针对提出的基于桶结构的单源最短路径串行算法,利用直接并行化法的并行算法设计方法和并行Boost图库的各类分布式数据结构和通信机制,设计和实现了分布式集群并行计算机上的桶结构并行算法。基于桶宽参数的桶结构、较优的图划分存储、异步的并行通信策略和较小的消息传输包等设计,使得桶结构并行算法在求解不同数据规模和结构特征的单源最短路径问题上都具有好的加速比和可扩展性。

全文目录


摘要  5-6
Abstract  6-10
第一章 绪论  10-14
  1.1 研究背景及意义  10-11
  1.2 国内外研究现状  11-12
  1.3 本文的工作  12-13
  1.4 本文的组织结构  13-14
第二章 并行计算概述  14-23
  2.1 并行计算机  14-16
  2.2 并行计算模型  16-18
  2.3 并行算法分类  18-19
  2.4 并行算法性能评价  19-20
  2.5 基于消息传递的并行编程  20-22
  2.6 本章小结  22-23
第三章 单源最短路径串行算法  23-35
  3.1 图的基本概念  23-26
  3.2 单源最短路径问题及算法分类  26-27
  3.3 Dijkstra 串行算法  27-29
    3.3.1 算法描述  27-28
    3.3.2 算法分析  28-29
  3.4 BFM 串行算法  29-31
    3.4.1 算法描述  29-30
    3.4.2 算法分析  30-31
  3.5 桶结构串行算法  31-34
    3.5.1 算法描述  31-32
    3.5.2 算法分析  32-34
  3.6 本章小结  34-35
第四章 单源最短路径并行算法  35-55
  4.1 并行Boost 图库  35-40
    4.1.1 并行Boost 图库概述  35-36
    4.1.2 分布式的图数据结构  36-38
    4.1.3 分布式的属性映射  38
    4.1.4 并行进程组  38-40
  4.2 并行算法设计方法和编程模式  40-41
    4.2.1 设计方法  40
    4.2.2 编程模式  40-41
  4.3 Dijkstra 并行算法  41-43
    4.3.1 并行化实现框架  41-42
    4.3.2 并行算法改进  42-43
  4.4 BFM 并行算法  43-44
    4.4.1 并行化基本思想  43-44
    4.4.2 并行算法改进  44
  4.5 桶结构并行算法的设计与实现  44-54
    4.5.1 数据结构设计和划分  44-45
    4.5.2 结点映射  45-46
    4.5.3 通信和同步  46-48
    4.5.4 桶宽的设定  48
    4.5.5 预处理过程  48-49
    4.5.6 主循环过程  49-52
    4.5.7 松弛过程  52-54
  4.6 本章小结  54-55
第五章 实验测试和分析  55-63
  5.1 实验环境  55-57
    5.1.1 硬件环境  55
    5.1.2 软件环境  55-57
  5.2 实验输入数据  57-58
    5.2.1 ER 随机图  57
    5.2.2 小世界模型图  57-58
  5.3 串行算法实验分析  58-59
  5.4 并行算法实验分析  59-62
  5.5 本章小结  62-63
结论  63-64
参考文献  64-68
攻读硕士学位期间取得的研究成果  68-69
致谢  69

相似论文

  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. 面向星载计算机的容错并行算法研究与实现,TP302.8
  12. 激光能量沉积光路追踪法及其并行化,TN241
  13. 基于LBM的两相流数值模拟及其并行算法的实现,O359
  14. 基于树形计算结构的电力系统潮流并行算法研究,TM744
  15. D-TIN并行构建方法及其在地图综合中的应用研究,P283
  16. 图像匹配的并行算法研究,TP301.6
  17. 求解大规模支持向量机问题的并行算法研究,TP18
  18. 迁移式并行遗传算法求解支持向量机反问题,TP18
  19. 基于MPI的海量数据拟合并行算法研究,TP301.6
  20. 旅行商问题的并行蚂蚁算法研究,TP301.6
  21. 基于机群的H.264/AVC并行算法研究,TN919.81

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