A Novel Analysis Method for Parallel Processing.

摘要

Though the divisible load scheduling problem has been studied for over two decades, the optimal solution for this problem can be obtained only in a few network topologies by the approach proposed in [6], which recursively equates multiple processing nodes in the network to a super processing node. The limitation of this equivalent approach lies in the fact that a node is required to finishing receiving load from its neighboring nodes simultaneously under this approach, such that linear equations can be established for all nodes in the network. However, the requirement is satisfied in very few network topologies. In this thesis, we address the problem of divisible load scheduling in network topologies where the requirement is not satisfied, and propose a novel analysis method, which formulates divisible load scheduling in these network topologies as a Maximum Finish Time Minimization (MFTM) problem. The MFTM problem minimizes the maximum finish time of all nodes in the network, and further analysis reveals that the MFTM problem can be transformed into the Finish Time Minimization (FTM) problem, which resembles the linear optimization problem, indicating an optimal solution by linear programming. With the novel analysis method, we study divisible load scheduling in a variety of network topologies, including mesh, torus, Gaussian network, the ring and multi-root tree, and propose the corresponding optimal algorithms. Besides, considering the high time complexity of the optimal algorithm in the mesh, torus and Gaussian network, we also propose a heuristic algorithm to reduce the time complexity. Extensive comparison results show that the heuristic algorithm achieves performance extremely close to the optimal algorithm algorithm, and both the optimal algorithm and heuristic algorithm significantly outperform previously proposed divisible scheduling algorithms in the studied network topologies.scheduling in network topologies where the requirement is not satisfied, and propose a novel analysis method, which formulates divisible load scheduling in these network topologies as a Maximum Finish Time Minimization (MFTM) problem. The MFTM problem minimizes the maximum finish time of all nodes in the network, and further analysis reveals that the MFTM problem can be transformed into the Finish Time Minimization (FTM) problem, which resembles the linear optimization problem, indicating an optimal solution by linear programming. With the novel analysis method, we study divisible load scheduling in a variety of network topologies, including mesh, torus, Gaussian network, the ring and multi-root tree, and propose the corresponding optimal algorithms. Besides, considering the high time complexity of the optimal algorithm in the mesh, torus and Gaussian network, we also propose a heuristic algorithm to reduce the time complexity. Extensive comparison results show that the heuristic algorithm achieves performance extremely close to the optimal algorithm algorithm, and both the optimal algorithm and heuristic algorithm significantly outperform previously proposed divisible scheduling algorithms in the studied network topologies.