Task assignment in host-satellite systems

Abstract

This paper deals with the problem of assigning task modules of a program over a multiple computer system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone.(13) However, the general n-processor problem (n > 3) in a fully connected system is known to be NP-complete.(14) A host-satellite system considered in this paper is composed of a powerful host processor p(o) and N homogeneous satellite processors p(k)'s, 1 less than or equal to k less than or equal to N, in which each satellite processor p(k) is connected to the host processor p(o) through a communication link. When any two satellite processors are to communicate with each other, the host processor p(o) must participate in the communication. Therefore, the interprocessor communication cost per unit of information transferred between any two satellite processors is twice as much as that between a satellite processor and the host processor p(o). In this paper, we propose an algorithm which finds an optimal assignment on a host-satellite system in polynomial time. A task assignment problem for a host-satellite system is first transformed into a network flow problem, and then solved by applying the well known network flow algorithm in time no worse than O(N M(3)), where N and M are the number of satellites and the number of modules, respectively.