Load Balancing Algorithm Of Parallel Computing System And Parallel Execution Time Prediction

This paper focus on the research of load balancing algorithm and parallel execution time prediction for parallel computing systems."Equal-division load"balancing algorithm is presented to balance the system's load. Load in every node is divided into smaller tasks based on all power of nodes on internetwork. Then these smaller tasks are sent to corresponding nodes to balance the load among nodes. Analysis results show that the algorithm has lower time complexity, and the algorithm can be used when system is to allocate load initially or when the system's load is extremely unbalanced. But when the system's load is approximately balanced, the amount of the transferred load on the internetwork will be considerable."Two-division network"balancing algorithm is presented to reduce the amount of the transferred load and to balance the load fast. According to this algorithm, the network is divided into two sub-networks with same number of the nodes, then the load is transferred between the sub-networks on the basis of their process power. Repeat this procedure until every sub-network only contains one node, and then the system's load will be balanced. For this algorithm, there is not a large amount of load transferred among nodes and not a large amount of the consumed time. This algorithm is suitable for most of static internetwork."Greedy linear shift"balancing algorithm is presented for ring or linear array to improve balancing time performance and to reduce the amount of the transferred load. According to this algorithm, overloaded task of every node will be transferred into next neighbor-node on the linear array or ring path until the system is balanced. The algorithm can be used for balancing any system in which internetwork contains at least one Hamilton path. For this algorithm, generally, there is not a large amount of load transferred among nodes and not a large amount of the consumed time. In addition, we present two-stage greedy linear shift balancing algorithm to improve the"greedy linear shift"balancing algorithm for mesh etc. Experiments and analysis show that the two-stage linear shift balancing algorithm will improve the execution time performance when the balancing condiction is weaken.To prediting the parallel execution time of the parallel program that is composed of a number of sub-tasks, each of which has identically, independent distributed random execution time, this paper presents the parallel execution time predicting method which is based on the Johnson distribution. Johnson system is used for transforming random variable of execution time of parallel sub-tasks into standard normal variable. Then prediction time is derived by using features of the normal distribution. The method can be used not only for predicting the maximum or minimum parallel execution time, but also for solving any problem about the maximum or minimum of identically, indentical distributed random variables.