Distributing and Scheduling Divisible Task on Parallel Communicating Processors

In this paper we propose a novel scheme forscheduling divisible task on parallel processors connected by systeminterconnection network with arbitrary topology. The divisible task isa computation that can be divided into arbitrary independent subtaskssolved in parallel. Our model takes into consideration communicationinitial time and communication delays between processors. Moreover, byconstructing the corresponding Network Spanning Tree (NST) for anetwork, our scheme can be applied to all kinds of network topologies. Wepresent the concept of Balanced Task Distribution Tree and use it todesign the Equation Set Creation Algorithm in which the set of linearequations is created by traversing the NST in post-order. Aftersolving the created equations, we get the optimal task assignmentscheme. Experiments confirm the applicability of our scheme inreal-life situations.