Scheduling Divisible Loads in Gaussian, Mesh and Torus Network of Processors

In this paper, we propose a novel analysis method for divisible load scheduling in mesh, torus and Gaussian network, a new type of interconnection network that has the same node degree as the mesh and torus, but shorter network diameter and shorter average hop distances under equal network size. The divisible scheduling in these three networks are uniformly formulated as the Maximum Finish Time Minimization (MFTM) problem. It involves minimizing the makespan of the load distribution and processing. The MTFM problem, a relaxed MFTM problem, a linear programming problem version and a heuristic algorithm are described and solved. The first three of these problems have identical solutions. The heuristic algorithm is close in performance to the optimal solution, significantly outperforms the previously described dimensional algorithm, and has much wider application range than the previously proposed phase algorithm.