Multi-source Divisible Load Scheduling In Arbitrary Networks

Load scheduling is an important task in the efficient and reliable operation of parallel systems.Starting from the special but widely used data type of divisible load,and combining the concept of parallel processing,this paper studies the scheduling problem of multi-source divisible load in arbitrary network.In order to complete the load processing in the shortest possible time,the nodes can communicate with each other and share the computing resources of all nodes in the network.Although the problem of divisible load scheduling has been studied for decades,most of the proposed methods can only obtain the optimal solution in a few specific network topologies.This paper proposes a new analysis method based on the optimality principle of Divisible Load Theory,and constructs a general divisible load model for multi-source divisible load scheduling problem in arbitrary topological network,in which the communication bandwidth,computation speed and load size can be arbitrarily configured.According to the different load processing modes,the optimization algorithm is designed for the multi-source divisible load scheduling problem in the sequential processing mode and the parallel processing mode,and improved in the parallel processing mode according to whether the node is equipped with a front-end processor.Taking the finish time of load processing as the optimization objective of the model,we transform the multi-source divisible load scheduling problem into the maximum finish time minimization problem.It is proved theoretically and experimentally that maximum finish time minimization problems can be transformed into linear programming or convex optimization algorithm to solve effectively.In this paper,lpsolve and CVX optimization toolbox in MATLAB are used to implement experimental simulation on the model proposed in this paper.In the experiment,the performance of divisible load scheduling algorithm with different processing modes in random network topology was observed with different network sizes,processor performance differences and network coupling degree as environment variables.The effectiveness and stability of the proposed optimization algorithm are proved by many comparative experiments.