【作者】 江文；

【导师】 赵欢；

【作者基本信息】 湖南大学 ， 计算机科学与技术， 2010， 硕士

【摘要】 随着计算机技术的发展,计算机应用范围不断扩大,异构计算系统在并行处理中得到了广泛运用。任务调度是并行处理中的关键问题,异构计算环境下的调度问题则更加复杂,是研究中亟待解决的一个难题。调度的目标是在满足一定性能指标和有限约束关系的前提下减少总的执行时间。绝大部分情况下的任务调度问题已经被证明为NP完全问题,这使得启发式方法在调度中得到了普遍运用。本文针对异构计算系统的任务调度展开研究,在经典的任务模型上提出了两个新的算法：针对基于优先驱动的表调度算法常出现优先级相同的问题,提出了一种综合性启发式算法(Heterogeneous Critical Path First Synthetic, HCPFS)。该算法在任务选择阶段按照是否关键路径节点、ranku值递减、后继数递减的优先级顺序选择任务,在任务分配阶段根据任务的最早完成时间进行处理器选择,并采用了任务复制和插入策略,以达到充分利用处理器资源,减少任务通信开销的目的。在采用复制方法的调度算法中,是以当前任务的开始时间、完成时间和执行时间等作为任务分配的依据,往往会产生不必要的任务复制。本文提出了一种基于后继任务最早完成的调度方法(Heterogeneous Successor Finish Earliest, HSFE),根据下一调度任务与当前调度任务的关系来进行任务分配,在当前调度任务与下一调度任务存在前驱后继关系时,以下一任务的最早完成作为当前处理器分配的依据,从而有效抑制了任务的不必要复制,增加了任务调度空间,提高了调度效率。本文从多个角度对算法进行了测试,通过对调度长度下界比、加速比的比较可知,本文提出的多优先级策略和基于后继就绪任务调度的方法有效地缩短了调度长度,通过对任务平均复制比和平均执行时间下界比的比较可知,.算法根据后继调度任务选择处理器分配,有效地抑制了任务的多余复制,节约了处理器资源,复制方法体现了更好的灵活性。更多还原

【Abstract】 With the development of computer technology and the expansion of computer application scope, heterogeneous computing systems have been widely used in the parallel applications. As the key issues of parallel processing,task scheduling is more complex in the heterogeneous computing systems because of different process capability among processors, and it has become a difficult problem that is urgent to be solved.The objective of task scheduling is to reduce the total execution time on the condition that certain performance indicators and given constraints can be satisfied.Task scheduling problem has been proved to be a NP-complete problem in the most of situations,which make heuristic methods to be widely used in the research of scheduling problem.In this paper,we make a research of task scheduling in the heterogeneous computing systems,and two algorithms are proposed in the classic task model.The main research of this paper as below:(1)The list-scheduling algorithm driven by priority selects tasks to schedule on by single attribute.But in the case of that different tasks should have the same priority,it can not work well.Therefore a new synthesized heuristics algorithm called HCPFS was proposed. In the stage of task selection,there are three levels of priority in the algorithm to choose task. First, the tasks in critical path have highest priority, secondly the tasks with longer path to exit task will be selected, and then algorithm will choose tasks with more successors to schedule.In the stage of task assigning,we choose the processor which minimize the earliest finishing time of current task,we also take task duplication method and task insert method to make full use of processor resouces.(2)The start time, completion time and execution time of current task is often the accordance of task allocation,such method always takes unnecessary task duplication in the scheduling algorithm with duplication method. This paper presents an algorithm called HSFE which is based on minimizing the earliest completion time of the successors to be scheduled next time.Current tasks is allocated to one processor according to the relationship between current task and next task.When current task is the predecessor of next task,it will be scheduled to the processor which can minimize. the earliest completion time of next task.This method can suppress unnecessary replication of tasks, increase scheduling space,and improve system efficiency effectively.To validate the effectiveness of the algorithms proposed,we simulate them and other algorithm used for comparison, using a variety of test solutions from multiple angles. Experimental results show that HCPFS algorithms can suppress blindfold task scheduling when there are serveral tasks which one of priorities is same,and that HSFE algorithms can effectively suppress unnecessary replication task.They both achieve relatively better performance in a number of evaluation parameters,such as Schedule Length Ratio,Speedup and Average Task Duplication Ratio, and so on.更多还原