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

并行图剖分优化策略研究

作　者: 汤继飞
导　师: 张理论
学　校: 国防科学技术大学
专　业: 软件工程
关键词: 并行图剖分 多核平台 两级通信 多水平算法 重剖分
分类号: TP338.6
类　型: 硕士论文
年　份: 2010年
下　载: 19次
引　用: 0次
阅　读: 论文下载
 

内容摘要


大规模数值并行计算应用通常采用“分而治之”思想进行任务划分。确保计算负载均衡和处理机间通信开销最小,是获得高效率的关键,因此如何合理有效地对任务剖分至关重要。图剖分是借助图论知识,将计算依赖关系抽象成图,把任务划分转换成图剖分问题。如何在并行平台下高效地将图剖分为多个子图,确保计算和通信负载均衡,是并行图剖分的主要研究内容。在设计图剖分算法时,需要综合考虑连通性、并行度、负载平衡、通信开销等因素。传统图剖分算法和软件未考虑当前多核机群平台中结点内和跨结点通信开销之间的差异,而是将通信开销单一化处理。随着单结点内处理器核数不断增加,结点内通信的比重日趋增加,结点内外这种通信开销差异的影响日益显著,对并行计算综合性能影响愈来愈不容忽视。为此,本文针对多核集群平台大规模并行计算,给出了一种新的图剖分策略,在尽可能满足计算负载平衡的前提下,使结点间通信开销最小,对剖分策略进行了性能分析和数值实验,结果显示该策略可以进一步用来减少多核集群平台上的通信开销。很多实际数值模拟问题(如动网格CFD计算、粒子模拟等)需要动态调整计算任务以满足计算和通信负载均衡,图(超图)重剖分策略重在解决此类并行任务动态划分问题。本文综合分析了基于扩散的重剖分策略和重映射重剖分策略,对现有的重剖分模型进行了量化,以权衡重剖分过程中的通信和迁移开销;在此基础上对超图的重剖分方法进行了改进,给出了一种适合超图的重剖分策略,开展了算法分析设计,并将该重剖分策略在典型并行剖分软件ParMetis中加以实现,与ParMetis中的已有两种剖分策略进行了对比分析和数值实验。结果显示该新重剖分策略的开销要优于ParMetis中的扩散方法和重映射方法,而执行时间也比较接近。

全文目录


摘要  9-10
ABSTRACT  10-11
第一章 绪论  11-15
  1.1 研究背景  11-12
  1.2 发展动态  12-13
  1.3 研究内容  13-14
  1.4 论文结构  14-15
第二章 相关知识  15-31
  2.1 图剖分基础  15-18
    2.1.1 图基本概念  15-16
    2.1.2 图剖分问题  16-18
  2.2 图剖分模型  18-23
    2.2.1 对分图模型  18-19
    2.2.2 超图剖分模型  19-21
    2.2.3 多约束多目标剖分模型  21-22
    2.2.4 异构平台图剖分模型  22-23
  2.3 图剖分方法  23-30
    2.3.1 几何方法  23-25
    2.3.2 组合方法  25-27
    2.3.3 多水平方法  27-29
    2.3.4 谱方法  29-30
  2.4 本章小结  30-31
第三章 图重剖分策略  31-39
  3.1 图重剖分问题  31-33
  3.2 基于扩散的重剖分算法  33-36
    3.2.1 扩散策略  33-35
    3.2.2 多水平的扩散重剖分算法  35-36
  3.3 基于重映射的重剖分方法  36-38
  3.4 本章小结  38-39
第四章 多核集群系统通信的图剖分优化策略研究与实现  39-47
  4.1 研究背景  39-40
    4.1.1 多核集群系统  39-40
    4.1.2 问题分析  40
  4.2 两级通信剖分  40-43
    4.2.1 剖分策略  40-42
    4.2.2 性能分析  42-43
  4.3 Metis 软件分析  43-44
  4.4 实验与分析  44-46
    4.4.1 测试环境  44-45
    4.4.2 实验数据  45
    4.4.3 通信开销测试  45
    4.4.4 执行时间测试  45-46
  4.5 本章小结  46-47
第五章 并行多级重剖分优化策略的设计与实现  47-58
  5.1 重剖分模型分析  47
  5.2 设计思想  47-49
  5.3 重剖分优化策略  49-52
    5.3.1 数据分配  49
    5.3.2 并行粗化阶段  49-51
    5.3.3 粗化初始剖分阶段  51
    5.3.4 并行细化阶段  51-52
  5.4 实验与分析  52-57
    5.4.1 实验环境  52-53
    5.4.2 实验数据  53
    5.4.3 重剖分总开销测试  53-55
    5.4.4 通信/迁移开销测试  55-56
    5.4.5 重剖分时间测试  56-57
  5.5 本章小结  57-58
第六章 总结及展望  58-60
  6.1 本文工作总结  58
  6.2 后续工作及展望  58-60
致谢  60-61
参考文献  61-66
作者在学期间取得的学术成果  66

相似论文

  1. 基于多核PC集群的并行绘制系统研究与实现,TP338.6
  2. 冲压成形有限元模拟自适应三角形网格剖分方法的研究与实现,TG381
  3. 分布式系统的故障注入方法研究,TP338.8
  4. 移动计算环境下故障结点检测方法研究,TP338.8
  5. 构建分布式系统的关键技术研究与实现,TP338.8
  6. 基于日志分析的超级计算机错误预测方法研究,TP338
  7. 模型独立框架下高阶π演算及表达能力研究,TP338.6
  8. 分布式文件系统客户端的设计与实现,TP338.8
  9. 多核集群环境下并行地理计算执行时间预测技术研究,TP338.6
  10. 普适计算中动态更新及其形式化研究,TP338
  11. 基于粒子模拟问题的GPU高性能计算系统,TP338
  12. 分布式系统中实体交互行为的可信研究,TP338.8
  13. 分布式远程组件调用技术安全性分析,TP338.8
  14. 并行计算环境中基于检查点的卷回恢复技术研究,TP338.6
  15. 基于案例-任务驱动教学法的高性能计算课程研究,TP338-4
  16. GPU上并行数据操作技术优化,TP338.6
  17. 动态可重构计算中程序热点识别关键技术研究,TP338
  18. 基于BOM的并行离散事件仿真建模技术研究与实现,TP338.6
  19. 基于HDFS的多用户并行文件IO的设计与实现,TP338.6
  20. 面向Cilk的并行递归程序优化技术研究,TP338.6
  21. 基于Linux的集群系统的应用研究,TP338

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 电子数字计算机（不连续作用电子计算机） > 各种电子数字计算机 > 并行计算机
© 2012 www.xueweilunwen.com