The Research And Application Of Self-scheduling Algorithms On Desk Grid Environment

Desk Grid is mainly composed of personal computers and it's more complex and dynamic than others.Using vacant computation abilities in desk grid can provide an inexpensive and convenient solution to solve large scale computational problems,so that how to allocate tasks to these nodes and achieve better load balancing is an issue in that field.Self-scheduling is one of accepted solutions.Self-scheduling is a dynamic,adaptive and distributed scheduling method which works on application layer.It divides a task into a set of subtasks,and then assigns them to computing nodes to execute parallel.This dissertation focuses on how to use and optimize Self-scheduling technology to allocate tasks reasonable and achieve better parallel performance.Firstly,this dissertation analyzes and compares existing Self-scheduling algorithms, and then points out the disadvantages when using these algorithms in desk grid environments.Secondly,it introduces how to use Self-scheduling in desk grid and parallel data transfer and execution by using the Producer-Consumer model.That approach can reduce the waiting time of each execution node rapidly.Thirdly,almost all existing Self-scheduling algorithms do not consider the nodes' performance efficiently and need some manual work to decide the value of each parameter.Unfortunately it is really hard because environment of desk grid is dynamic and heterogeneous.So it proposes a novel Chunk Hybrid Self-Scheduling(CHSS) algorithm which determines the value of chunk artificially and allocates tasks according to node's performance dynamically.Lastly,it introduces the prediction algorithms and proposes a new Chunk-based Task Runtime Prediction(CTRP) algorithm according to the characters of Self-scheduling and the defects of existing algorithms.That algorithm can predict more accurate executing time and achieve better load balancing than that of other ones when most nodes' load is changing frequently and rulelessly.This dissertation takes Chinese Information Processing Grid as testbed.The experimental results show that CHSS algorithm and CTRP algorithm can achieve better performance.