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