【作者】 郝宪文；

【导师】 张斌；

【作者基本信息】 东北大学 ， 计算机应用技术， 2008， 博士

【摘要】 网格是一种能够集成地理上分散资源的基础设施。它能将各种信息资源接成一个整体,向每个用户提供包括计算能力、数据存储能力以及各种应用工具等一体化的透明服务。网格资源是分布在Internet环境中的,资源本身具有异构性、动态性和自治性。网格任务在不同的资源上的性能表现不同,因此对于提高由多个任务构成的网格应用的整体性能而言,需要网格任务调度为应用中的每个任务指派合适的资源。在网格任务调度中,依赖任务调度问题已经引起了广泛的关注。网格依赖任务调度问题,由于对某一任务的资源指派将影响对其他任务的资源指派,因此,为了实现网格应用性能优化的调度目标,需要采取全局的调度策略。该调度策略是基于预知的应用和资源信息,在运行前制定全局调度计划。网格应用的各个任务将按照计划中的时间安排在指派资源上执行。由于网格资源是动态变化的且这种变化会随时发生,因此在应用的运行期间资源可能发生变化,这种变化将影响网格应用的最优性。为此,就需要网格依赖任务重调度,以便在资源发生变化时,对全局调度计划进行调整,以实现应用性能优化的目标。以应用性能优化为目标的网格依赖任务重调度,需要采取全局优化的的重调度策略与资源变化触发的重调度触发方式,而这将面临重调度效率低与触发频繁等困难。为解决上述困难,本文从确定重调度任务范围、减少资源数量、提高备选资源稳定性、减少无用重调度四个方面着手,提出了基于资源动态性度量的网格依赖任务重调度机制。该机制以资源动态性度量模型为基础,以基于视图的资源组织、重调度触发机制以及重调度任务波及域计算为支撑,尽量利用动态性较弱的资源,合理缩小重调度任务范围,并在合适的时机触发网格依赖任务重调度过程,解决了网格依赖任务重调度效率低、触发频繁的问题,从而实现了以应用性能优化为目标的网格依赖任务重调度。本文主要完成了如下的工作：(1)针对网格依赖任务重调度面临的效率低和触发频繁两个问题,本文研究基于资源动态性度量的网格依赖任务重调度机制(G-DERM),提出资源动态性度量模型。该模型对个体资源及整体资源环境的性能和性能变化周期进行度量。在资源动态性度量的基础,G-DERM通过在合适的时机触发网格依赖任务重调度过程、尽量利用动态性较弱的资源、合理缩小重调度任务范围,能够有效的提高网格依赖任务重调度的效率,降低重调度的触发频繁。(2)针对如何减少备选资源数量和提高备选资源稳定性问题,本文研究基于视图机制的资源组织模型。该模型是一个资源的三层组织结构,是在以应用的资源需求和资源动态性度量结果对网格资源进行双重过滤的基础上构建起来的。该模型能够过滤性能相近的应用可用资源中的强动态性资源,提高重调度备选资源的稳定性,进而提高网格依赖任务重调度的效率并降低重调度触发频率。(3)针对如何减少无用重调度问题,本文研究重调度触发机制,提出重调度的触发规则,建立触发规则的层次结构。该规则在网格资源动态性度量的基础上,分析资源变化对应用性能的影响,判断是否需要触发重调度,并确定重调度触发时刻,延时触发在任务执行时间估计准确性较低情况下的资源变化引发的重调度过程,减少无用重调度次数,降低网格依赖任务重调度触发频率。(4)针对如何确定重调度任务范围问题,本文研究重调度任务波及域及计算算法。在度量资源环境动态性和估计任务完成时间的基础上,通过判断任务完成时间是否在资源环境的变化周期内,重调度过程中将不考虑完成时间不在该周期内的任务,即不考虑对网格应用性能优化支持较弱的任务；并且通过网格应用中任务间所存在的点波及、依赖波及以及连通波及关系计算重调度任务波及域,以在不影响网格应用优化效果的基础上,缩小任务范围,提高重调度的效率。(5)针对重调度任务波及域内网格依赖任务重调度求解效率与优化效果问题,本文研究基于G-DERM的网格依赖任务重调度模型和算法。提出基于DAG的重调度模型及改进HEFT启发式算法,和基于T-RAG优化选取的重调度模型及免疫遗传算法。在保证效率的同时提高网格应用的优化效果。(6)针对如何验证本文所提出的基于资源动态性度量的网格依赖任务重调度机制有效性问题,本文搭建G-DERM模拟实验环境,并进行一系列实验验证所提出的重调度触发机制、波及域计算、资源组织模型对提高网格依赖任务重调度的效率,降低重调度触发频率的支持作用。更多还原

【Abstract】 Grid is a kind of infrastructure that could integrate geographically dispersed resources. It could connect all kinds of information resources as a whole, and provide each user transparent integration services, including computing power, data storage capacity as well as various applications. Grid resources are distributed on the dynamic Internet environment, with special natures of heterogeneous, dynamic and self-governing. On different grid resources, the task’s performance is different. Thus, to achieve the overall performance of a grid application composed by a set of tasks, task scheduling is needed to assign the suitable resource for each task. In grid task scheduling problem, dependent tasks scheduling problem has been widely concerned. In dependent tasks scheduling problem, an assignment for one task may affect the other task’s assignment. Therefore, to achieve the overall optimal performance or grid application, global optimization scheduling policy is needed, which relies on the anticipated information of the application and resources, and makes the total schedule before application starts to run according to the time arrangement and resource assignment in the schedule. Because of the dynamic nature of grid resource, resource’s performance and availability will change very often and at any time. So during grid application running-time, the resource will change, and affect the optimum of the application’s performance. Therefore, dependent tasks rescheduling is needed, to adjust the schedule for the application’s optimal performance.To optimize application performance, global-optimization rescheduling policy and resource-change-trigger rescheduling method are needed for grid dependent tasks rescheduling, which lead to two difficulties:low rescheduling efficiency and frequently trigger. To address the above two difficulties, the paper presents a grid dependent tasks rescheduling mechanism based on resource dynamic evaluation, beginning with the rescheduling task scope identification, resources reduction, resources stability promotion and useless rescheduling avoiding problems. With the foundation of resource dynamic evaluation, and supported by the view-based resources organization model, rescheduling trigger mechanism and rescheduling tasks spread domain computing, the mechanism could make full use of resources with weaker dynamic and reasonably narrow the rescheduling task scope and trigger the rescheduling process at the right time to solve the low rescheduling efficiency and frequently trigger. problem. This paper completes the following main tasks:(1) To solve the difficulties of low rescheduling efficiency and frequently triggering faced by current rescheduling approaches, this paper studies grid dependent tasks rescheduling mechanism based on resource dynamic evaluation (G-DERM) and proposes resource dynamic evaluation model. Such model can evaluate the performance and changing cycle of single grid resource and resource environment. Based on resource dynamic evaluation, G-DERM can trigger the rescheduling process at the right time, make full use of dynamic resources with weaker dynamic and reasonably narrow the rescheduling task scope to solve the low rescheduling efficiency and frequently triggering problem.(2) To solve the problems of reducing the number of resources and improving the stability of candidate resources, this paper studies the view-based resources organization model. Such model is a three-layer structure for organizing resources which is established based on application requirement as well as resource dynamic evaluation. Such model can filter out high dynamic resources with similar performance for certain application. Based on such model, the stability of candidate resources for rescheduling can be enhanced. Thus, the rescheduling efficiency can be promoted and triggering frequency can be slowed down.(3) To solve the problem of avoiding useless rescheduling problem, this paper studies rescheduling triggering mechanism and proposes hierarchical rescheduling triggering rules. Through making use of the resource dynamic evaluation results and analyzing the resources changes’impact on application performance, these rules can determine whether to trigger rescheduling process, identify triggering time and delay triggering rescheduling process due to the estimation with low accuracy of task’s execution time on resources. Thus, the number of useless rescheduling processes can be reduced and the triggering frequency of rescheduling processes can be slowed down.(4) To solve the problem of determining the scope of rescheduling tasks, this paper studies the rescheduling tasks spread domain and its computing algorithm. Based on resource environment dynamic evaluation results and task finish time estimation, through judging whether the task finish time is in the resource environment change cycle, the rescheduling process will not consider the tasks whose finish time is beyond the resource environment change cycle. Rescheduling tasks spread domain is computed according to the tasks’ point-relationship, dependence-relationship and connection-relationship. Thus, the tasks scope can be narrowed and the rescheduling efficiency can be promoted with litter affecting the optimization of grid application performance. (5) To solve the problem of improving the rescheduling efficiency and optimization, this paper studies the G-DERM based grid dependent tasks rescheduling model and algorithms. This paper propose a DAG based rescheduling model and improved HEFT algorithm, as well as a T-RAG optimal selection based rescheduling model and immune genetic algorithm. Thus, the rescheduling efficiency and optimization performance can be ensured.(6) To solve the problem of verifying the effectiveness of proposed resource dynamic evaluation based grid dependent tasks rescheduling mechanism, this paper establishes a G-DERM simulation environment and conducts a set of experimentations to verify the better performance of the proposed rescheduling triggering mechanism, rescheduling tasks spread computing algorithm, and resource organization model in improving the efficiency of rescheduling and slowing down the triggering frequency.更多还原