基于任务复制的网格任务调度算法  

A Task Duplication Based Scheduling Algorithm in Grid Computing Systems

作　　者：林剑柠[1] 吴慧中[1] 陈学勤[1] 

机构地区：[1]南京理工大学计算机系,南京210094

出　　处：《计算机科学》2006年第6期89-92,105,共5页Computer Science

基　　金：国防预研课题基金项目(51404020303BQ0220);南京市重点攻关基金。

摘　　要：网格中资源之间存在着通信延迟,通过任务复制的冗余,可以减少任务之间的通信开销,缩短整个计算程序的计算时间。目前网格中的任务调度算法基本上是没有考虑任务复制的;而基于任务复制调度算法往往会产生过多的复制任务,增大系统开销,甚至有可能延迟计算时间。由于基于任务复制的任务调度是一个NP问题,因此本文提出了一种基于任务复制的网格资源调度算法,以减少调度长度为主要目标、减少任务复制量和资源占用量为次要目标。该算法在调度长度和任务复制数量以及占用资源数量方面都等于或优于其它算法。Grid computing is a new computing-framework to meet the growing computational demands. Computational grids provide mechanisms for sharing and accessing large and heterogeneous collections of remote resources. However, task scheduling is one of the key elements in the grid computing environment, and an efficient algorithm can help reduce the communication time between tasks. So far,the task scheduling algorithms in the grid computing environment have not been based on task duplication. But,the scheduling algorithms based on task duplication will generate too many task replications, which will enlarge the system loads and even add the makespan. As optimal scheduling of tasks is a strong NDhard problem,this paper presents a scheduling algorithm based on genetic algorithm and task duplication, whose primary aim is to get the shortest makespan, and secondary aim to utilize less number of resources and duplicate less number of tasks. The chromosome coding method and the operator of genetic algorithm are discussed in detail. The relationship between subtasks can be obtained through the DAG. And the subtasks are ranked according to their depthvalue,which can avoid the emergence of deadlock. The algorithm was compared with other scheduling algorithm based on GAs in terms of makespan,resource number and task replication number. The experimental results show the effectiveness of the proposed algorithm to the scheduling problem.

关 键 词：任务复制 任务调度 冗余任务 DAG图 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]