摘要
In this paper we propose a novel scheme for scheduling divisible task onparallel processors connected by system interconnection network with arbitrary topology. Thedivisible task is a computation that can be divided into arbitrary independent subtasks solvedin parallel. Our model takes into consideration communication initial time and communicationdelays between processors. Moreover, by constructing the corresponding Network SpanningTree (NST) for a network, our scheme can be applied to all kinds of network topologies. Wepresent the concept of Balanced Task Distribution Tree and use it to design the Equation SetCreation Algorithm in which the set of linear equations is created by traversing the NST inpost-order. After solving the created equations, we get the optimal task assignment scheme.Experiments confirm the applicability of our scheme in real-life situations.
