Research Of A Multi-constrained Grid Scheduling Module Supporting Parallel Task

Grid Computing is one of the hotspots in the research of Internet, and it is adirection in developing parallel and distributing computing. Grid is a compositivecomputing and resource environment, which can contain all kinds of computingresources, and change them to a environment which has reliable, standard andecomonic computing capability.The Computing Grid Prototype System is a kind of Grid Portal,and it also becalled a middle-ware which provides user with web accessing interface, and theuser can use computing resource through browser in anywhere.The system joinsmany computing resources distributed in Campus by inernet or intranet to build ahigh-powered "COW", and provides parallel computing service.Scheduling grid tasks is a kind of distributed task scheduling.It is one ofimportant functions in grid platform. Tasks submitted by user is scheduled byscheduling module to result in a better resource usage,according task type,resources needed by task,usability of resources and so on.It is dynamic anduncertain when the grid tasks arrive or leave,and how many resource the usersrequest. Grid resource scheduler should meet the requests as many as possible tomake a perfect makespan,load balance,QoS requirement,charging for using gridresource.It indicates that the scheduling is a kind of NP-hard problem.First, the thesis focuses on the contents below:Design a multi-restricted scheduling algorithm for grid scheduling, takingload balance and efficiency of grid system into first account.Add a task scheduling sub-system into the existing Computing GridPrototype System.It scheduling tasks in queue including MPI tasks.Provide developers with a uniform interface to different schedulingalgorithm, and make it easier to change algorithm in the sub-system into a newone.The uniform interface makes system easier maintenance.Add the multi-constrained grid scheduling algorithm into the task schedulingsub-system,then evaluate this algorithm in a real grid computing environment.Considering nothing but the load balance about grid nodes,scheduler shoulddistribute a task onto the lightest-load node j,which has a high Pj value.However,based on the Min-Min scheduling algorithm, scheduler should distribute a taskonto the node with minimum ETC(Execute Time to Compute).The thesis definesan extend distributing ratio,which mixes the load balance distributing ratio andinfections resulted from ETC into a weighting expression .The thesis indicates that the extended distributing ratio Pj'results in a newmapping instead of the load balance distributing ratio. In conretely,the schedulerdistributes a task that based on the Pj'to a node with the highest Pj.When thefaster nodes in the grid environment overload, they get more Pj'increasementbecause of the small ETC on them , while the slower nodes get lessPj'increasement.So that the big tasks won't be scheduled until the faster nodes area little more idle,and will be executed using less time.Consequently,makespan ofthe task queue decreases.Please consult on chapter three for more detail about themulti-constrained algorithm.Afterwards, task scheduling sub-system is realized and integrated into theComputing Grid Prototype System.There are six modules,such as module togather resource information placed in node end as client(module 1),moduleplaced in web server node to monitor resource information submitted by module 1as server(module 2),module to gather information of unscheduled tasks submittedby grid users(module 3),module to query information about the system,such ascurrent status of grid nodes, status and result of tasks,etc,(module 4),keymodule to schedule a unscheduled queue into a ready queue(module 5),and thelast one that distribute tasks onto different nodes to be executed(module 6).Thesystem enables grid users to submit tasks on the web,module 3 gather those tasksevery certain intervals to form an unscheduled queue and hand it to module 5;Module 5 adjusts the unscheduled queue into a ready queue according thescheduling strategy placed in the module and hands the ready queue to module6.Module 6 follow the progress of executing tasks,makespan and load afterdistributing them to the target grid nodes.Module 4 read informations fromdatabase and module 2 according to users'requirement.Detail is referring toChapter two and four .Finally, the multi-constrained algorithm in Chapter three is placed andevaluated in the task scheduling sub-system.The experiment data indicates that themulti-constained algorithm is able to balance load between all the nodes in a realgrid environment.The algorithm gets a better makespan than load-balancingalgorithm when the primary load of grid environment is lopsided, especiallywhen the high-powered node represents heavy primary load.Themulti-constrained algorithm is proved in reason.It points out the shortage of the algorithm and system at the last thesis, suchas to refine the weighting factor αand β,to improve ETC-expecting model andheuristic function in algorithm,to makeup and enable the system to work in aheterogeneous ,multi-tasktypes environment, and to enhance security of thesystem.