集群系统中基于DAG模型的任务调度算法研究
发布时间：2018-08-23 11:06
【摘要】：近年来，，集群系统成为高性能计算的主流平台，在此系统上进行并行计算蕴涵着巨大的计算潜力，调度是挖掘这些计算能力的关键技术。在并行系统中，应用任务被划分为多个子任务，有向无环图（DAG）因能反映并行系统中各子任务以及这些任务间的依赖关系而被广泛采用，本文研究基于DAG图的集群系统任务调度问题，具体如下： （1）对于同构集群下的调度问题，采用表调度技术解决。分析现有表调度算法的不足，在此基础上提出基于动态关键路径的全局调度算法GDCP。该算法在调度任务选择阶段准确地赋予任务优先级，并结合全局搜索策略选择处理机。实验及数据分析表明，该算法有效地提高了调度性能。 （2）对于异构集群下的调度问题，采用遗传调度算法解决。针对传统遗传调度算法在种群初始化方式上的缺陷，提出异构系统中改进的遗传调度算法ISGA。该算法利用任务的属性值来构造染色体，得到优质的初始种群。实验及数据分析表明，该算法可以获得较好的调度质量。 （3）将本文研究成果应用于与国家电网电力科学研究院合作的项目“实时监控系统的并行处理”中，以验证它们在实际计算环境中是有效的。
[Abstract]:In recent years, cluster system has become the mainstream platform of high performance computing. Parallel computing on this system has great computing potential. Scheduling is the key technology to mine these computing capabilities. In parallel systems, application tasks are divided into subtasks, and directed acyclic graphs (DAG) are widely used because they can reflect subtasks and their dependencies in parallel systems. In this paper, the task scheduling problem of cluster system based on DAG graph is studied. The details are as follows: (1) Table scheduling technology is used to solve the scheduling problem in isomorphic cluster. Based on the analysis of the shortcomings of the existing table scheduling algorithms, a global scheduling algorithm based on dynamic critical paths (GDCPs) is proposed. The algorithm accurately assigns priority to the task in the scheduling task selection phase and combines with the global search strategy selection processor. Experimental results and data analysis show that the proposed algorithm can effectively improve the scheduling performance. (2) genetic algorithm is used to solve the scheduling problem in heterogeneous clusters. Aiming at the defects of the traditional genetic scheduling algorithm in population initialization, an improved genetic scheduling algorithm ISGA in heterogeneous systems is proposed. The algorithm uses the attribute value of the task to construct the chromosome, and obtains the high quality initial population. Experiments and data analysis show that the algorithm can achieve better dispatching quality. (3) the research results of this paper are applied to the parallel processing of real-time monitoring system, which is a cooperative project with the State Research Institute of Electric Power Sciences of State Grid. To verify that they are valid in a real computing environment.
【学位授予单位】：南京航空航天大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338
本文编号：2198893
[Abstract]:In recent years, cluster system has become the mainstream platform of high performance computing. Parallel computing on this system has great computing potential. Scheduling is the key technology to mine these computing capabilities. In parallel systems, application tasks are divided into subtasks, and directed acyclic graphs (DAG) are widely used because they can reflect subtasks and their dependencies in parallel systems. In this paper, the task scheduling problem of cluster system based on DAG graph is studied. The details are as follows: (1) Table scheduling technology is used to solve the scheduling problem in isomorphic cluster. Based on the analysis of the shortcomings of the existing table scheduling algorithms, a global scheduling algorithm based on dynamic critical paths (GDCPs) is proposed. The algorithm accurately assigns priority to the task in the scheduling task selection phase and combines with the global search strategy selection processor. Experimental results and data analysis show that the proposed algorithm can effectively improve the scheduling performance. (2) genetic algorithm is used to solve the scheduling problem in heterogeneous clusters. Aiming at the defects of the traditional genetic scheduling algorithm in population initialization, an improved genetic scheduling algorithm ISGA in heterogeneous systems is proposed. The algorithm uses the attribute value of the task to construct the chromosome, and obtains the high quality initial population. Experiments and data analysis show that the algorithm can achieve better dispatching quality. (3) the research results of this paper are applied to the parallel processing of real-time monitoring system, which is a cooperative project with the State Research Institute of Electric Power Sciences of State Grid. To verify that they are valid in a real computing environment.
【学位授予单位】：南京航空航天大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338
【参考文献】
相关期刊论文 前5条
1 舒昌奇,芦伟;电力系统监控的几种类型对比[J];甘肃科技;2004年08期
2 钟求喜,谢涛,陈火旺;任务分配与调度的共同进化方法[J];计算机学报;2001年03期
3 石威,郑纬民;相关任务图的均衡动态关键路径调度算法[J];计算机学报;2001年09期
4 周双娥,袁由光,熊兵周,欧中红;基于任务复制的处理器预分配算法[J];计算机学报;2004年02期
5 陆鑫达,郑飞,陈楚询;异构计算系统的任务调度算法SMT-GA[J];小型微型计算机系统;1999年04期
本文编号：2198893
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2198893.html
