MPP环境中面向动态规划算法的混合并行系统的研究

发布时间：2017-06-08 04:14

  本文关键词：MPP环境中面向动态规划算法的混合并行系统的研究，由笔耕文化传播整理发布。

【摘要】：动态规划是一种将复杂问题分解成若干个子问题进行计算的问题解决方案，在科学计算中有着广泛的应用。然而随着计算中数据量的增大，解决问题的时间代价已经不能满足人们的需求。多核多处理器等硬件技术的发展为科学计算并行化提供了良好的环境和平台，使得降低科学计算的时间代价成为可能。与其他科学计算问题相比，动态规划问题具有很强的数据依赖性。这给并行程序设计带来困难，并使得并行程序设计过程容易出错。 本文针对以上问题，提出了MPP环境下针对动态规划并行化的多层次混合并行系统EasyHPS并对动态规划问题的并行化进行了研究。对于动态规划问题，我们根据其特点总结出动态规划计算方程。基于此方程，我们在EasyHPS系统中建立起DAG数据驱动模型并为动态规划问题进行建模。以DAG数据驱动模型为基础，EasyHPS实现了MPP环境下动态规划问题多层次自动并行化的系统框架。在EasyHPS系统中，DAG数据驱动模型对并行计算过程中的子任务划分，调度及消息通信等功能模块进行了封装，并提供用户接口供用户调用，从而实现了动态规划问题在MPP环境下的自动并行化，降低程序设计人员的并行程序设计难度。动态规划并行化过程中的容错问题进行研究。EasyHPS系统通过超时检查和日志跟踪两种方式对于运行过程进行容错检查，，并实现了断电重启后继续计算的功能。最后通过生物信息学中的基因匹配算法对于系统的可行性及并行效率进行验证。通过基于波阵的Block-Cyclic的静态任务调度算法的实验对比，EasyHPS的多层次动态调度策略有着更高的并行效率。
【关键词】：MPP 动态规划 多层次自动并行化 DAG数据驱动模型
【学位授予单位】：天津大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：O221.3;TP338.6
【目录】：

• 摘要4-5
• ABSTRACT5-9
• 第一章 绪论9-13
• 1.1 研究背景9-10
• 1.2 国内外研究现状及趋势10-11
• 1.3 本文主要工作和贡献11
• 1.4 本文的内容和结构11-13
• 第二章 相关工作介绍13-15
• 2.1 并行计算硬件平台13-14
• 2.1.1 对称多处理器(Symmetric Multi-Processor)13
• 2.1.2 非一致存储访问体系结构(Non-Uniform Memory Access)13
• 2.1.3 大规模并行处理体系结构(Massive Parallel Processing)13-14
• 2.2 大规模并行计算中间件14-15
• 第三章 多层次自动并行化系统 EasyHPS 框架简介15-17
• 第四章 DAG 数据驱动模型17-23
• 4.1 DAG 模式图定义17
• 4.2 动态规划问题与 DAG 模式图的关系17-19
• 4.3 动态规划问题的分类与 DAG 模式图库19-20
• 4.4 DAG 数据驱动模型初始化20-21
• 4.5 运行时系统中 DAG 数据驱动模型的解析21-23
• 第五章 EasyHPS 系统子任务调度机制23-27
• 5.1 EasyHPS 动态线程池组件23-24
• 5.1.1 当前可计算子任务队列23
• 5.1.2 完成计算子任务队列23-24
• 5.2 主模块动态任务线程池的任务调度24-25
• 5.3 从属模块动态任务线程池的任务调度25-27
• 第六章 EasyHPS 系统容错恢复机制简介27-33
• 6.1 常见的容错问题27-28
• 6.2 超时检测的容错机制28-30
• 6.2.1 进程级别的超时检测容错机制28-29
• 6.2.2 线程级别的超时检测容错机制29-30
• 6.3 日志跟踪的容错机制30-33
• 第七章 EasyHPS 系统内存接口扩展33-38
• 7.1 缓存的组相联映射33-34
• 7.2 EasyHPS 系统中内存扩展接口设计34-38
• 第八章 EasyHPS 系统设计38-48
• 8.1 EasyHPS 系统主模块详细设计38-43
• 8.1.1 主模块 DAG 数据驱动模型详细设计38-41
• 8.1.2 主模块调度模块详细设计41-42
• 8.1.3 主模块容错模块详细设计42-43
• 8.2 EasyHPS 从属模块详细设计43-46
• 8.2.1 从属模块 DAG 数据驱动模型详细设计43-45
• 8.2.2 从属模块调度模块详细设计45-46
• 8.2.3 从属模块容错模块详细设计46
• 8.3 EasyHPS 系统内存扩展接口详细设计46-48
• 第九章 EasyHPS 系统在 MPP 环境中的实验设计和结果分析48-57
• 9.1 实验环境与实验设计48-49
• 9.2 小数据规模下基于 EasyHPS 系统实现动态规划算法49-55
• 9.2.1 小数据规模下基于 EasyHPS 系统实现动态规划算法的实验设计49-51
• 9.2.2 小数据规模下基于 EasyHPS 系统实现动态规划算法的结果分析51-52
• 9.2.3 小数据规模下容错模块对于 EasyHPS 系统性能的影响52-55
• 9.3 小数据规模下 EasyHPS 系统的动态调度策略与静态调度策略的比较55
• 9.3.1 小数据规模下 EasyHPS 系统的动态调度策略与静态调度策略的实验设计55
• 9.3.2 小数据规模下 EasyHPS 系统的动态调度策略与静态调度策略的结果分析55
• 9.4 大数据规模下基于 EasyHPS 系统实现动态规划算法55-57
• 9.4.1 大数据规模下基于 EasyHPS 系统实现动态规划算法的实验设计56
• 9.4.2 大数据规模下基于 EasyHPS 系统实现动态规划算法的结果分析56-57
• 第十章 总结和展望57-59
• 10.1 总结57
• 10.2 对未来工作的展望57-59
• 10.2.1 针对 DAG 模式图库进行改良58
• 10.2.2 对于异构计算平台的研究和完善58
• 10.2.3 对于超大规模数据集计算的支持58-59
• 参考文献59-62
• 发表论文和参加科研情况说明62-63
• 致谢63

【共引文献】

中国期刊全文数据库 前10条

1 杨泽民;谢数涛;章群;张俊彬;;RNA二级结构预测及其在分子分类研究中的应用[J];安徽农业科学;2012年07期

2 张伟;金萍;侯林;马飞;;海鞘(Ciona intestinalis)新microRNA基因的识别及其靶标预测[J];安徽农业大学学报;2010年04期

3 付昊月;张祥德;薛定宇;;粗糙集算法在预测RNA保守功能二级结构中的应用[J];东北大学学报(自然科学版);2008年10期

4 ;Prediction of miRNA Based on miRNA Biogenesis via One-class SVM[J];Chemical Research in Chinese Universities;2010年05期

5 ;Identification of MicroRNA Precursors with Support Vector Machine and String Kernel[J];Genomics Proteomics & Bioinformatics;2008年02期

6 ;A Method for Identification of Selenoprotein Genes in Archaeal Genomes[J];Genomics Proteomics & Bioinformatics;2009年Z1期

7 ;Characterization of Evolutionarily Conserved MicroRNAs in Amphioxus[J];Genomics Proteomics & Bioinformatics;2010年01期

8 刘文远;刘丽云;王常武;王宝文;;基于二阶马尔科夫模型预测可趋近性靶基因[J];燕山大学学报;2012年04期

9 ;Predicting sRNAs and Their Targets in Bacteria[J];Genomics, Proteomics & Bioinformatics;2012年05期

10 夏飞;朱强华;金国庆;;基于CPU-GPU混合计算平台的RNA二级结构预测算法并行化研究[J];国防科技大学学报;2013年06期

中国重要会议论文全文数据库 前1条

1 苏光龙;黄旭慧;丁凡;蒋晓舟;骆志刚;;基于堆积能量和协变信息的RNA二级结构预测算法[A];中国通信学会第六届学术年会论文集（下）[C];2009年

中国博士学位论文全文数据库 前10条

1 王鑫;Pre-mRNA选择性剪接调控机制研究[D];哈尔滨工程大学;2009年

2 靳宇;RNA带扭结结构的组合研究[D];南开大学;2010年

3 秦晶;核糖核酸结构：三级联接与相互作用[D];南开大学;2010年

4 夏飞;生物序列分析算法硬件加速器关键技术研究[D];国防科学技术大学;2011年

5 贾孟文;mRNA序列、结构、能量和蛋白质二级结构的相关性[D];内蒙古大学;2004年

6 金伟波;基于支持向量机方法的植物miRNA预测及小麦miRNA的克隆[D];西北农林科技大学;2007年

7 刘娜;生物序列/结构的比较及进化树的构建[D];大连理工大学;2007年

8 王师;栉孔扇贝遗传图谱的构建及重复元件的进化分析[D];中国海洋大学;2007年

9 李校;组合多重证据促进真核生物基因结构预测[D];四川大学;2007年

10 舒文杰;RNA二级结构拓扑特征化关键技术及其应用研究[D];国防科学技术大学;2007年

中国硕士学位论文全文数据库 前10条

1 张伟;海鞘MicroRNA基因的识别及其靶标预测[D];辽宁师范大学;2011年

2 王明浩;序列结构二联语法识别miRNA前体[D];南京航空航天大学;2010年

3 白杨;基于随机森林的外显子剪接增强子识别[D];哈尔滨工业大学;2010年

4 米少华;基于机器学习的microRNA基因预测[D];河北工业大学;2011年

5 贾启东;农业昆虫中微RNA基因的生物信息学预测[D];南京农业大学;2010年

6 杨泽民;金藻类部分类群的分子系统学研究[D];暨南大学;2005年

7 娄绍科;反义寡核苷酸的计算机辅助设计[D];中国人民解放军军事医学科学院;2006年

8 李培芳;基因组中核苷酸序列的字频和回文结构[D];内蒙古大学;2006年

9 王义;支持向量机在医学及生物方面的应用[D];华东师范大学;2007年

10 谢福亮;油菜microRNA和靶基因的预测与鉴定[D];南京农业大学;2007年

  本文关键词：MPP环境中面向动态规划算法的混合并行系统的研究，由笔耕文化传播整理发布。

本文编号：431362