【作者】 陆杰；

【导师】 符云清；

【作者基本信息】 重庆大学 ， 计算机系统结构， 2010， 硕士

【摘要】 网格计算系统实现了不同地理分布的异构资源的共享、选择和聚合,以解决在科研、工程、经济学等领域大规模的计算问题。网格任务调度问题是网格领域的关键问题之一,它是以某一评价指标为依据,针对如何将提交的任务分配到相应的网格资源上运行的问题,提出一个合理有效的调度方案。调度策略的优劣决定了是否能够高效合理地分配和利用网格资源,减少网格任务的总体计算时间和花费,使得网格的性能达到最佳。网格环境下的任务调度问题是网格计算的研究热点之一。论文重点研究了以下几方面的内容:①在综述网格计算的研究背景及意义的基础上,较全面地分析了网格任务调度的特点及其常用的调度算法。②提出了一种改进的基于遗传算法的网格任务调度算法,在算法的初始化种群产生时引入Min-Min算法和Max-Min算法以及采用Hamming距离来控制个体之间的差异,从而在提高初始种群质量的同时保证了种群的多样性;在算法的迭代过程中提出了一种新的局部收敛判定标准以及相应的变异操作来防止算法的局部收敛。③在本文的任务调度算法中采用DAG(Directed Acyclic Graph)模型来描述并行任务之间的约束依赖关系,DAG模型更能真实地反映并行任务的实际情况,此外本文中的算法设计还考虑了处理器异构等因素。④构建现实当中的网格环境不仅花销昂贵,而且时间上也不允许,且网格资源还具有多样性和动态性等特性,因此利用实际网格系统来测试网格任务调度算法的性能和效率是不现实的,也是很困难的。一般地,我们借助网格模拟工具来进行相应的仿真试验。作者利用GridSim网格模拟器对本文改进的网格任务调度算法进行了仿真实验,从最优跨度的角度对实验结果进行详细的对比和分析。实验结果表明,本文改进后的种群初始化方法不仅能够提高算法的寻优起点,而且能够加快算法的寻优速度;改进后的局部收敛判定标准及相应的局部收敛变异操作在预防早熟局部收敛的同时能够提高算法的全局寻优能力;改进后的基于遗传算法的网格任务调度算法相比于基于自适应遗传算法的调度算法,能够有效地缩短任务的总体执行时间,并且在大规模的网格任务调度环境下具有良好的性能,能够在实际网格环境中加以应用。更多还原

【Abstract】 Grid computing is becoming a more and more important in the high performance computing due to the fact that it enables the sharing, selection, and aggregation of geographically distributed heterogeneous resources for solving large-scale problems in the field of science, engineering, and commerce. Task scheduling is an important part of grid computing. Grid task scheduling resolves how to reasonably assign grid resources to tasks, and how to schedule every task to the assigned grid resources. A good scheduling policy can improve the rational allocation and efficient use of grid resources and reduces the overall grid task computing time and cost, making the best performance of the grid. So task scheduling under grid environments is one of the key research fields of grid systems.The main research works of this paper are listed as follows:①The features and common scheduling algorithms of grid task scheduling are analyzed through summarizing the research background and significance of grid computing.②An improved grid task scheduling algorithm based on genetic algorithm is proposed. In the process of population initialization, a new method which combines the Min-Min algorithm and the Max-Min algorithm is addressed, and it uses hamming distance to control the difference among the individuals. Therefore, the new method can not only improve the quality of initial population, but also ensure the diversity of population. In the evolution of the population, a new criterion predicting the premature convergence is presented and the corresponding improved mutation is designed to avoid premature convergence.③The DAG (Directed Acycle Graph) model is adopted to describe the relation among parallel tasks in the genetic algorithm. This kind of model has better capacity to illuminate the actual state of parallel job than the other model. The factor of different processing capacity of CPU is also considered in our algorithm.④Building an actual grid environment is not only expensive but also time-consuming, moreover considering the diversity and dynamic of grid resources, it is quite difficult to confirm the performance and validity of grid task scheduling algorithm through actual grid system. Generally, we use grid simulators to handle with the simulation work. The author does a prototype exeriment of the algorithms on the GridSim simulation platform, and analyzes the exerimental results in detail from the point of view about the makespan.The experimental results are analyzed in detail, and the simulation shows that the improved population initialization method can not only improve the starting point of the algorithm optimization, but also accelerate the speed of algorithm optimization. The improved premature convergence judgement criterion and the corresponding improved mutation can predicte the premature convergence and improve the ability of global optimization. In the grid task scheduling, the proposed algorithm is better than the adaptive genetic algorithm, it can effectively reduce the overall execution time of the total tasks, and have good performance in large-scale grid task scheduling environment, so it can be used in the real grid environment.更多还原