面向动态规划计算的并行编程模型和运行时系统研究

Dynamic programming is widely used in science and engineering computing. The increasing scale of problem and development of parallel computing hardware made the parallel programming for dynamic programming get more difficult. We will decrease the difficulty and complexity of such parallel programming by reusable parallel programming model and high efficiency runtime system for dynamic programming. The self-adaptive multilevel task scheduling method is based on the DAG data driven programming model, to ensure the load balance by refining the scale of subtasks and multilevel scheduling. According to the large-scale intermediate result data for different hardware platform and specific applications, we propose the data storage and accessing methods based on shared files. And the on demand data transferring method will reduce the unnecessary communications. The DAG pattern library is based on plug-in architecture to support the reuse of pattern and the expansibility of the system. The research work will cooperate with the specific algorithms and applications from computational bioinformatics and computational finance to get the feed back from real usage. Optimization will be made according to Cluster and MPP architecture and several file systems. The expected result of this proposal will support the dynamic programming based applications with programming model and runtime system, to speed up the research and development of science and application.

动态规划广泛应用于科学和工程计算，问题规模增加以及并行计算硬件技术发展使动态规划计算并行程序研发的难度随之增高，本课题通过面向动态规划的可复用并行编程模型和高效运行时系统来简化此类应用并行编程的难度和复杂度。基于DAG数据驱动编程模型，研究自适应多层次任务调度方法，通过任务粒度二次划分以及多层次任务调度的方法解决负载不平衡问题；研究适用于不同硬件平台以及应用类型的大规模中间结果数据的处理方法，以高效共享文件的方式解决中间结果数据的存储和访问问题，以按需数据传输的方式减少不必要的通信；研发插件式DAG模式库管理方法，支持模式的复用和系统扩展。研发过程结合计算生物信息学和计算实验金融领域的具体算法和应用进行，以实际应用反馈研究方案，并针对集群、MPP体系结构以及具体文件系统进行优化。课题预期成果可为基于动态规划计算的应用研发提供编程模型和运行时系统的支持，缩短科学及应用研发周期。

我国的超级计算机研制已经实现了全国产化，且总体性能已经多年居于世界领先，而并行程序设计方面的研发远落后于超级计算硬件的发展以及应用问题规模的增加，面向具体类型问题的并行编程模型以及运行时环境将是连接应用与超级计算资源的一种有效途径，本项目的方法与成果有借鉴意义和实用价值。.并行编程模型以及运行时系统的关键方法与技术是本项目的研究重点。以动态规划类型的并行计算问题为主要研究对象，在本项目预研期间提出的DAG数据驱动并行编程模型基础上，本项目提出并实现了新的编程框架，在天河一号超级计算机环境中实现了运行时系统，基因序列分析等可抽象为动态规划类型并行计算的应用问题可以基于此系统方便地完成并行应用的开发；在任务调度、通信优化方面的研究工作，与分布式并行计算环境中多主体仿真计算相结合，在股票主场等金融模型仿真问题中得以实际应用；基于本项目所研究的任务调度、数据存储方法等技术所研发的南极AST3望远镜实时数据处理系统在中国南极昆仑站部署成功应用，在无人值守且能源受限的条件下，完成了观测数据在现场的自动实时分析处理；在高效率数据存取方面的研究，结合了天文数据处理、音频数据检索等领域；天文数据处理方面对天文图像子集的高效检索可应用于虚拟天文台环境中大规模多波段天文数据的存储与检索；音频数据检索的成果在音乐检索等领域可直接应用。.在本项目的支持下，共发表学术论文16篇（SCI期刊论文5篇，国际学术会议论文11篇），培养硕士研究生9人，博士研究生2人。