【作者】 尚明生；

【导师】 孙世新；

【作者基本信息】 电子科技大学 ， 计算机应用技术， 2007， 博士

【摘要】 网格是近年来信息技术领域的热点研究课题,是支撑未来各类应用的国家信息基础设施。任务调度问题是网格研究和应用必须解决的一个关键问题。本文对网格计算中的任务调度模型和任务调度算法进行了探索和研究,主要工作分为如下四个方面:1.从应用模型、平台模型和调度目标三个方面对现有任务调度模型进行了研究,对模型参数的精确性和简单性之间的折衷进行了分析,探讨了更现实任务调度模型的若干指标。2.研究了可分任务调度问题,得到如下三个方面的结果。第一,提出了带启动开销的非阻塞通信模型,解决了基于此模型的大规模可分应用的优化调度问题;第二,研究了大规模可分应用的周期性任务调度算法,给出了同构平台中各类参数的最优取值表达式;第三,研究了任意网络拓扑中的可分应用调度问题,提出两类启发式任务调度算法。3.研究了独立任务调度问题,得到如下四个方面的结果。第一,针对同构平台,提出一种基于局部搜索的任务调度算法;第二,针对异构平台同构任务,提出一种带记忆功能的任务调度算法;第三,研究了异构平台的异构任务调度问题,提出了任务调度优先级概念,得到一类基于优先级的任务调度算法;第四,提出了一种针对异构平台异构任务的基于局部搜索的任务调度算法。4.研究了依赖任务调度问题,提出了一种基于关键路径的列表调度算法。该算法在构造调度列表时综合考虑了各种任务的影响,在处理机选择时提出了“向前看”的策略,从而使得关键任务能够尽早执行,有效地缩短了调度长度。更多还原

【Abstract】 The Grid is a new national information infrastructure for many future applications. It has been a research focus in the field of information technology in recent years. In a grid computing environment, the problem of task scheduling is very critical. In this thesis, models and algorithms for scheduling tasks in the grid are studied. The main results are as follows:1. Models for task scheduling including application model, platform model and scheduling objective are investigated in detail. The trade-off between model accuracy and model simplicity is discussed. Several parameters of more realistic task scheduling model are induced.2. The problem of divisible task scheduling is studied and the following results are presented. First, optimal algorithms based on a more realistic model, i.e., non-zero start-up cost for non-blocking model of communication, are proposed for scheduling large workload on heterogeneous system. Second, a periodic multi-installment algorithm is proposed and closed-form expressions for optimal parameters on homogeneous systems are derived. Third, two kinds of heuristic scheduling algorithm are proposed for scheduling divisible load on arbitrary topological network.3. The problem of independent task scheduling is studied and the following results are acquired. First, a local search algorithm is proposed to solve the problem of task scheduling in homogeneous environment. Second, a memory based algorithm is proposed for scheduling same-size tasks on heterogeneous platform. Third, a concept of task scheduling priority is proposed and a class of scheduling algorithm can be derived according to the priority. Fourth, a local search algorithm is proposed for task scheduling in heterogeneous system.4. The problem of dependent task scheduling is studied and an efficient list scheduling algorithm based on critical path is presented. By means of a new approach for constructing the task list, and an efficient processor selection procedure using looking ahead strategy, the algorithm shortens the makespan greatly.更多还原