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

面向DAG数据依赖型应用系统研究与实现

作　者: 汤善江
导　师: 孙济洲
学　校: 天津大学
专　业: 计算机软件与理论
关键词: EasyPDP DAG数据驱动模型动态规划生物信息学 DAG模式图
分类号: TP311.1
类　型: 硕士论文
年　份: 2010年
下　载: 12次
引　用: 2次
阅　读: 论文下载

内容摘要

动态规划是求解最优化问题的一种高效的途径和方法,在生物信息学和科学计算中有着广泛的应用。然而,由于求解问题的数据规模的急剧膨胀,传统的串行程序实现在运行时间方面已无法让人接受。既而,动态规划的并行化实现便显得十分的必要和重要。另一方面,由于动态规划自身存在的强依赖性使得并行编程复杂且易出错,开发出一套工具来帮助开发人员简化并行编程显得十分的必要和重要。本文针对动态规划问题,本着简化并行编程的理念和目标,从并行编程模型和并行设计模式的角度出发,首先提出了面向DAG数据驱动型应用的模型,然后基于该模型,设计并实现出了一套面向多核共享存储环境的运行时系统--EasyPDP。通过使用该EasyPDP系统,用户只需要将精力关注于具体算法的串行实现,而对于程序并行实现细节方面,用户无需关注,EasyPDP自动地负责着并行程序中整个线程的创建、数据任务的动态调度和分配、数据化分和容错控制等。本文首先提出了面向DAG数据驱动型应用的模型。从模型的意义和目的角度,对其进行了分析和介绍。接着从模型框架组成方面,对用户应用程序模块、DAG模式图模块、DAG运行时系统模块分别进行了详细地说明。然后,针对动态规划在生物信息学中的应用及其在并行化方面的研究现状,进行了系统的分类和阐述。另外,提出了面向动态规划算法的DAG模式图,以便供用户直接使用。最后,本文对EasyPDP运行时系统进行了详细的介绍和性能分析。分别从EasyPDP系统目标、系统模块、系统数据控制流、容错性能控制机制、性能参数分析建模等角度对系统进行了全方位的剖析。接着进行了实验的性能分析。首先提出了参数分析模型,然后从EasyPDP的配置参数(DataSize, BlockSize, ThreadNum)、EasyPDP的overhead和cache失效、与静态并行实现BCW的性能比较、EasyPDP容错性能评估等角度进行实现分析说明。

全文目录

摘要  3-4
ABSTRACT  4-7
第一章绪论  7-10
  1.1 课题背景  7-8
  1.2 研究意义  8
  1.3 研究内容和创新  8-9
  1.4 论文结构  9-10
第二章简化并行编程理论和方法概述  10-20
  2.1 并行计算程序设计概述  10-15
    2.1.1 并行计算硬件平台  11-13
    2.1.2 并行程序开发语言及程序库  13-15
  2.2 简化并行编程理论与方法  15-20
    2.2.1 并行编程模型  15-16
    2.2.2 并行设计模式  16-17
    2.2.3 并行结构骨架  17
    2.2.4 并行可视化建模  17-20
第三章面向DAG数据驱动型应用的模型  20-24
  3.1 模型的提出和意义  20-21
  3.2 模型框架  21-24
    3.2.1 用户应用程序模块  21-22
    3.2.2 DAG模式图模块  22
    3.2.3 DAG运行时系统模块  22-24
第四章动态规划算法及其在生物信息学中的应用  24-31
  4.1 动态规划算法及其分类  24-26
  4.2 动态规划算法在生物信息学中的应用  26-27
  4.3 动态规划算法的并行化  27-28
  4.4 基于动态规划算法的DAG模式图  28-31
第五章 EasyPDP运行时系统  31-54
  5.1 EasyPDP系统目标  31
  5.2 EasyPDP系统模块  31-34
    5.2.1 用户API  31-32
    5.2.2 DAG操作模块  32
    5.2.3 线程池模块  32-33
    5.2.4 容错控制模块  33-34
  5.3 EasyPDP运行时系统  34-45
    5.3.1 EasyPDP系统数据流控制  34-36
    5.3.2 容错控制机制  36-38
    5.3.3 缓冲区操作和管理  38
    5.3.4 性能优化参数  38-39
    5.3.5 参数性能分析讨论  39-45
  5.4 实验性能分析  45-54
    5.4.1 实验环境说明  46
    5.4.2 DataSize对EasyPDP的性能影响  46-47
    5.4.3 BlockSize对EasyPDP的性能影响  47-48
    5.4.4 ThreadNum对EasyPDP的性能影响  48-49
    5.4.5 EasyPDP的Overhead分析  49-50
    5.4.6 EasyPDP的Cache Miss分析  50-52
    5.4.7 EasyPDP与BCW性能比较  52-53
    5.4.8 EasyPDP容错性能评估  53-54
第六章总结与展望  54-56
  6.1 全文总结  54-55
  6.2 研究工作展望  55-56
参考文献  56-61
发表论文和参加科研情况说明  61-63
致谢  63

面向DAG数据依赖型应用系统研究与实现

内容摘要

全文目录

相似论文